Sarcina progresului calului, lumea PC-urilor, editura "sisteme deschise"

ARUBA INSTANT WI-FI: SIMPLĂ, PUTERNICĂ, DISPONIBILĂ

În articol este examinată problema clasică a progresului cavalerului, pentru soluționarea căreia se dezvoltă programele iterative, recursive și automate, precum și rezultatele investigației lor. Programul automat încorporat generează aceleași rezultate ca și cele iterative, dar este mai evident.

Metode de optimizare

Una dintre cele mai interesante secțiuni ale programării include probleme din domeniul inteligenței artificiale, în care soluția este căutată prin încercări și erori [1,2]. În acest caz, există o căutare în căutarea unei soluții, iar durata acesteia poate fi scurtă prin aplicarea anumitor reguli euristice (metode de optimizare).

Clasa de algoritmi care permit rezolvarea unor probleme similare în literatura de limbă engleză este numită "algoritmi backtracking" ("algoritmi cu returnare"). Astfel de algoritmi sunt utilizați atunci când metode mai "direcționate" nu se potrivesc [3].

Să explorăm una dintre cele mai faimoase sarcini ale acestei clase - progresul calului [3-5]. Se compune în găsirea unei mese de mărimea unui cavaler NxM, care se mișcă în conformitate cu regulile jocului de șah. Dacă există un astfel de bypass, fiecare câmp este vizitat o singură dată (se fac pași NxM-1). Aici vom analiza metodele de optimizare (reducerea căutării) și vom examina activitatea programelor iterative, recursive și automate. Considerăm mai întâi metodele de optimizare utilizate pentru a reduce căutarea în programul iterativ:

identificarea celulelor care nu pot fi evitate (optimizarea 1);
detectarea celulelor blocate (optimizarea 2);
aplicarea regulii Warnsdorf (optimizarea 3);
Utilizarea diferitelor tablouri pentru mișcări de cai (optimizarea 4).

Identificarea celulelor care nu pot fi ocolite

Dacă numărul de celule ale plăcii este ciudat (numărul de celule albe și negre este diferit de unul), atunci ocolirea există numai din celulele culorii care vor fi mai mari. Nu este greu de observat că calea calului trece prin celule alternante în culoare. Dacă numărul total de celule de bord este ciudat, atunci prima și ultima celulă a căii traversate de cavaler va avea aceeași culoare. Prin urmare, bypassul va exista numai atunci când începe cu o celulă a culorii care are cel mai mare număr de celule.

Următoarea funcție verifică această condiție:

Cu toate acestea, regula de mai sus nu acoperă toate celulele pentru care nu există nici un fel de soluție. Deci, pentru o placă de celule 3x7, pe lângă cele pentru care regula de mai sus este îndeplinită, un circuit este de asemenea imposibil din celulă (2,4).

Detectarea celulelor blocate

Dacă în timpul următoarei mișcări se formează o cușcă, unde puteți intra, dar unde nu puteți pleca, atunci această mișcare este inacceptabilă, cu excepția celei penultimate în bypass. Așa cum se va arăta mai jos, această metodă de optimizare vă permite să reduceți în mod semnificativ numărul de returnări, inclusiv atunci când este utilizat împreună cu regula Warnsdorff.

Dezvoltarea sa a fost identificarea grupurilor de celule blocate, conectate între ele, dar întrerupte de restul plăcii. În considerate aplicații definite grupuri de două celule blocate, ceea ce reduce foarte mult numărul de informații pentru plăci mici, iar atunci când este utilizat împreună cu regula Varnsdorf - și pentru mari (de exemplu, dimensiunea celulei 100x100).

Aplicarea regulii Warnsdorff

Printre numeroasele metode euristice utilizate pentru a reduce bustul [5], regula Warnsdorff este cea mai simplă. În concordanță cu aceasta, atunci când traversează tabla de șah, de fiecare dată când trebuie să fie pusă pe acel câmp, de unde poate face cel mai mic număr de mișcări în câmpuri care nu au fost încă transmise. Dacă există mai multe astfel de câmpuri, atunci puteți alege oricare dintre ele, care poate, totuși, să conducă un cal la un sfârșit și să solicite o întoarcere. Observăm că regula Warnsdorff funcționează cel mai bine pentru câmpurile unghiulare.

Folosind diferite tablouri pentru mișcări de cai

Mută de cai pot fi specificate, de exemplu, ca o matrice:

Fiecare dintre elementele sale determină o posibilă mișcare a calului și conține modificări ale coordonatelor acestuia pe placă atunci când se face rândul. Atunci când se utilizează machete diferite pentru mișcări de cai, numărul de returnări poate varia. Programul utilizează cinci matrice, care conțin mișcări posibile ale calului într-o ordine diferită. Specifică numărul maxim de returnări (GOOD_RET), iar atunci când este atins, căutarea căii începe din nou folosind un alt tablou. Când căutați un traversal utilizând ultima matrice, numărul de returnări este limitat la MAX_RET. În cazul în care schimbul de toate metodele de optimizare propuse GOOD_RET setați valoarea egală cu una, atunci plăcile aproape de piața, puteți construi runde fără o singură întoarcere pentru toate celulele din care există un ocol. Un bypass fără o singură întoarcere din fiecare celulă nu poate fi obținut pentru plăcile "alungite" (de exemplu, celulele 14x3) și pentru cele mari (de exemplu, 100x100 celule).

Programul iterator

Bust total

Ideea unui algoritm pentru un program iterativ este după cum urmează:

la fiecare pas se caută un fragment al căii, plecând de la celula curentă și fără a include deja traversat;
atunci când facem o mișcare din matricea posibilelor mișcări, se extrage următorul element, ceea ce duce la o celulă neocupată situată în interiorul plăcii;
dacă mișcarea este imposibilă, atunci există o întoarcere la celula anterioară (anularea mutării);
căutarea căii este considerată reușită atunci când numărul curent de mutare devine egal cu numărul de celule de pe tablă. Dacă toate mișcările posibile sunt mutate din celula inițială, atunci calea nu există.

Structura funcției forței brute este prezentată în Lista 2.

Numărul variantei folosite pentru fiecare mișcare este stocat într-o matrice a cărei mărime este selectată în funcție de dimensiunea plăcii. Algoritmul descris face o căutare a variantelor și găsește o soluție, dacă există. Absența unei soluții duce la o căutare completă a tuturor opțiunilor. În tabel. 1 pentru a ilustra implementarea returnărilor este protocolul de eludare a celulelor 3x4 de dimensiune a celulei din celula (2,4).

Tabelul 1. Mărimea plăcii de circumscripție a protocolului 3 x 4 celule din celulă (2,4)

Pentru unele celule, programul rulează extrem de încet deja cu o dimensiune mică a plăcii. Deci, pentru o placă de celule de 6x6 la începutul celulei (5.2), căutarea căii necesită 291.077.505 returnări.

Rezultatele programului cu optimizare

Se știe din [5] că pentru plăcile de dimensiuni NxM și MxN:

nu există ocolire pentru N, M 7; N> 4, M> 5.

Referindu-ne la prezentarea rezultatelor obținute, observăm că acestea se referă la metodele de optimizare de mai sus și la matricea selectată heuristic de opțiuni pentru mutarea calului. Atunci când se folosesc alte metode de optimizare [5] și alte rețele, rezultatele obținute pot fi diferite.

De exemplu, luați în considerare rezultatele traversării unor panouri. Pentru o placă de celule de 5x5, se dă un tabel unde este indicat numărul de returnări efectuate atunci când se găsește un ocol din celula corespunzătoare (Tabelul 2). In absenta by-pass într-o celulă este plasat simbolul N, iar în cazul în care suma depășește randamentul dat de valoarea programului (MAX_RET = 400 000), calea de căutare este terminată, iar caseta corespunzătoare este afișată reducerea LIM. În tabelele construite pentru metode de optimizare, în cazul în care diferite matrici sunt utilizate unul pentru cursa de cai, celula suplimentară dă denumirea de matrice (de la A la E), a cărei aplicare a fost realizată fără ocolind întoarce (GOOD_RET = 1). Și dacă rezultatul a fost obținut pentru prima matrice, atunci caracterul A corespunzător nu este afișat.

Tabelul 2. Rezultatele programului pentru o placă de celule 5 x 5

Pentru o tablă de șah clasică care măsoară celule 8x8, s-au obținut următoarele rezultate:

Pentru optimizările 1 și 2, valoarea maximă a numărului de randamente este depășită în majoritatea celulelor. Numărul minim de returnări din celulă (5.5) - 2502;
pentru optimizările 1 și 3, în toate celulele s-au obținut returnări zero, cu excepția celulelor (4.1) și (6.4), unde 9 și 79 revin, respectiv;
pentru optimizările 1-3 în celulă (6.4) s-au efectuat trei returnări, iar în rest - zero rambursări;
pentru optimizările 1-4, returnările zero au revenit în toate celulele și a fost utilizată o a doua serie de mișcări posibile în celulă (6.4).

Pentru placa cu dimensiunea de 100x100 celule s-au obținut următoarele rezultate:

pentru optimizările 1-3, în majoritatea celulelor se obțin nivele zero și numărul de returnări în celulele rămase variază de la unu la valori care depășesc o limită dată;
pentru optimizările 1-4 în toate celulele, cu excepția celulelor (94,24) și (94,79), au apărut returnări zero.

Program recursiv

Cea mai faimoasă soluție pentru problema ocolului cavalerului este recursivă [2]. În acest caz, structura funcției care efectuează căutarea este după cum urmează:

Toate tipurile de optimizări descrise mai sus pot fi utilizate în acest program.

Program automat

Dacă primele două programe pentru rezolvarea acestei probleme sunt destul de tradiționale [2], atunci automatele nu se aplică acestor probleme. Rețineți că programul automat poate fi construit în mod formal din iterativul descris mai sus utilizând metoda descrisă în [7]. Un program de automatizare poate fi, de asemenea, construit în mod formal în conformitate cu programul recursiv dat folosind metoda propusă în [8].

Fig. 1. Circuitul racordurilor automate

În plus, este posibil să se creeze un program automat prin construirea automată a unui automat în funcție de condițiile problemei. În Fig. Figurile 1 și 2 prezintă schema de conectare corespunzătoare și graficul de tranziție al automatului Mile.

Fig. 2. Graficul grafic al tranzițiilor automatelor

Această mașină utilizează funcțiile și variabilele definite într-un program iterativ, astfel încât se aplică toate metoda de optimizare de mai sus, și obținute cu ajutorul rezultatelor coincid cu rezultatele programului iterativ.

Textul simplificat al funcției care implementează acest automat este prezentat în Lista 4.

Ce este mai bine?

După cum sa menționat mai sus, programele iterative și automate produc aceleași rezultate, însă programul automatizat, care se distinge prin selectarea explicită a stărilor, este mai ușor de înțeles.

Rezultatele altor experimente și textul integral al programului cu care au fost implementate vor fi afișate pe site-urile is.ifmo.ru și www.softcraft.ru în secțiunea "Mașini automate".