“Evolyutsion algoritmlar”

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI QARSHI FILIALI

“ KOMPYUTER INJINERINGI ” FAKULTETI
4 – BOSQICH DI-13-19 GURUH TALABASINING

“Evolyutsion algoritmlar”

FANIDAN TAYYORLAGAN
3-mustaqil ishi

Bajardi: RAJABOV A.
Qabul qildi: Abdullayev R.

QARSHI 2023
Ryukzak masalasini yechish N qirolichalar haqidagi masalani yechish
Biz mos ravishda 1-to'plam va 2- to'plamda Knightning sayohati va Rat in a Maze muammosini muhokama qildik . Keling, N Queen-ni orqaga qaytish yordamida hal qilinishi mumkin bo'lgan boshqa misol sifatida muhokama qilaylik. 
N qirolicha N × N shaxmat taxtasiga ikkita malika bir-biriga hujum qilmasligi uchun N qirolichani joylashtirish muammosi. Masalan, quyida 4-qirolicha muammosining yechimi keltirilgan.
Kutilayotgan natija matritsa shaklida bo'lib, unda qirolichalar joylashtirilgan bloklar uchun "Q" va bo'sh joylar "." bilan ifodalanadi. Masalan, quyida yuqoridagi 4 ta qirolicha yechimining chiqish matritsasi keltirilgan.
. . Q . 
Q . . . 
. . . Q 
. Q . . 
Naive algoritmi 
Bortda malikalarning barcha mumkin bo'lgan konfiguratsiyalarini yarating va berilgan cheklovlarni qondiradigan konfiguratsiyani chop eting.
while there are untried configurations
{
generate the next configuration
if queens don't attack in this configuration then
{
print this configuration;
}
}
Orqaga qaytish algoritmi  1-usul:
Maqsad, eng chap ustundan boshlab, malikalarni birin-ketin turli ustunlarga joylashtirishdir. Qirolichani ustunga qo'yganimizda, biz allaqachon joylashtirilgan malika bilan to'qnashuvlarni tekshiramiz. Joriy ustunda, agar biz to'qnashuv bo'lmagan qatorni topsak, biz ushbu qator va ustunni yechimning bir qismi sifatida belgilaymiz. Agar biz to'qnashuvlar tufayli bunday qatorni topmasak, biz orqaga qaytamiz va yolg'onni qaytaramiz.
1-usul:
1) Eng chap ustundan boshlang
2) Agar barcha qirolichalar joylashtirilgan bo'lsa,
true qiymatini qaytaring
3) Joriy ustundagi barcha qatorlarni sinab ko'ring.
Har bir sinab ko'rilgan qator uchun quyidagi amallarni bajaring.
a) Agar malikani ushbu qatorga xavfsiz joylashtirish mumkin bo'lsa,
uni [qator, ustun] yechimning bir qismi sifatida belgilang
va
malikani bu erga joylashtirish yechimga olib keladimi yoki yo'qligini rekursiv tekshiring.
b) Agar qirolichani [satr, ustun] ga joylashtirish
yechimga olib kelsa, true qiymatini qaytaring.
c) Agar qirolichani joylashtirish yechimga olib kelmasa,
bu [satr, ustun] belgisini olib tashlang (Orqaga) va
boshqa qatorlarni sinab ko'rish uchun (a) qadamga o'ting.
4) Agar barcha qatorlar sinab ko'rilgan bo'lsa va hech narsa ishlamasa,
orqaga qaytishni boshlash uchun false ni qaytaring.