“Evolyutsion algoritmlar”

Chiqish
0 0 1 0
1 0
0 0 0 0
0 1 0 1 0 0
Vaqt murakkabligi: O(N!) 
Yordamchi fazo: O(N)

N-Queen muammosida barcha yechimlarni chop etish

N qirolicha N × N shaxmat taxtasiga ikkita malika bir-biriga hujum qilmasligi uchun N qirolichani joylashtirish muammosi. Misol uchun, quyida 4 Queen muammosining yechimi keltirilgan.


Oldingi postda biz faqat bitta mumkin bo'lgan yechimni chop etadigan yondashuvni muhokama qildik, shuning uchun endi ushbu postda N-Queen muammosidagi barcha echimlarni chop etish vazifasi turibdi. Har bir yechim N-qirolichalarni joylashtirishning alohida taxtali konfiguratsiyasini o'z ichiga oladi, bu erda yechimlar ortib borayotgan tartibda [1,2,3..n] o'rinbosarlari bo'ladi, bu erda i-o'rindagi raqam i - ustun malikasi ekanligini bildiradi. bu raqam bilan qatorga joylashtiriladi. Yuqoridagi misol uchun yechim [[2 4 1 3 ] [3 1 4 2 ]] shaklida yozilgan. Bu erda muhokama qilingan yechim xuddi shu yondashuvning kengaytmasidir.
Orqaga qaytish algoritmi 
Bu g'oya, eng chap ustundan boshlab, malikalarni birma-bir 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) Eng chap ustundan boshlang
2) Agar barcha qirolichalar joylashtirilsa
rost qaytar
3) Joriy ustundagi barcha qatorlarni sinab ko'ring. Quyidagilarni bajaring
har bir sinab ko'rilgan qator uchun.
a) Agar malikani bu qatorga xavfsiz joylashtirish mumkin bo'lsa
keyin bu [satr, ustun] ning bir qismi sifatida belgilang
yechim va joylashtirish yoki yo'qligini rekursiv tekshiring
malika bu erda yechimga olib keladi.
b) Agar malikani [satr, ustun] ga qo'yish a ga olib kelsa
yechim keyin true ni qaytaradi.
c) Agar qirolichani joylashtirish yechimga olib kelmasa
keyin bu [satr, ustun] belgisini olib tashlang (Orqaga)
va boshqa qatorlarni sinab ko'rish uchun (a) qadamga o'ting.
3) Agar barcha qatorlar sinab ko'rilgan bo'lsa va hech narsa ishlamasa,
orqaga qaytishni boshlash uchun false ni qaytaring.
O'zgartirish shundan iboratki, biz O (1) vaqtida ustunda yoki chap diagonalda yoki o'ng diagonalda oldindan joylashtirilgan malika borligini aniqlashimiz mumkin. Biz buni kuzatishimiz mumkin 

1. 
   Muayyan chap diagonaldagi barcha hujayralar uchun ularning qatori + col = doimiy.
   
2. 
   Muayyan o'ng diagonaldagi barcha hujayralar uchun ularning qatori - col + n - 1 = doimiy.