tur cavaler lui Softcraft
De aici puteți descărca întregul articol în format PDF (215 kb)
De aici - un program folosit în experimente (5 kb)
Articolul se ocupă cu tur cavaler clasic, pentru care soluțiile sunt dezvoltate iterativ, automaton și programe recursiv. Rezultatele studiului acestor programe. program de tăiere încorporat vă permite să obțineți aceleași rezultate ca și iterativ, dar este mai ușor de înțeles.
Soluție de o întrebare curios,
care pare să nu fie supuse
nici o cercetare.
Euler
Pentru una dintre cele mai interesante secțiuni includ sarcini de programare din domeniul inteligenței artificiale, în care soluția este găsită de „încercare și eroare“ [1,2]. În acest caz, există un bust în găsirea de soluții, durata care poate fi redusă prin utilizarea diferitelor metode euristice - de optimizare.
Clasa de algoritmi care permite de a rezolva astfel de probleme, în literatura engleză numită „algoritmi backtracking“ ( „algoritmi cu întoarcere“). Acești algoritmi sunt folosite în cazurile în care nu există mai potrivite „direcționate“ metode [3].
Noi examinăm una dintre cele mai importante probleme din această clasă - tur de cavaler [3-5]. Este de a găsi un ocol pe dimensiunea de bord M N calul se deplasează în conformitate cu regulile de șah. Dacă există un bypass, fiecare câmp este vizitat doar o singură dată (efectuat N * M-1 pași). Să analizăm tehnicile de optimizare și de a explora activitatea unui automaton iterativ, recursiv și programe.
metode de optimizare
Luați în considerare următoarele tehnici de optimizare:
- determinarea celulei din care este imposibil de by-pass (optimizare 1);
- identificarea celulelor blocate (optimizare 2);
- Normele de aplicare Varnsdorf (optimizare 3);
- utilizarea diferitelor mișcări matrice de cai (optimizare 4).
1. Definirea celulelor scurtcircuitarea care nu poate fi
În cazul în care numărul de plăci de celule este impar (numărul de celule albe și negre diferă de unul), bypass-ul unor celule nu există. Rețineți că modul în care calul trece prin celule, alternativ în culori. În cazul în care numărul total de celule de bord este ciudat, atunci prima și ultima celulă calea parcursă de cal, va fi de aceeași culoare. Astfel, bypass-ul va exista numai atunci când începe o culoare de celule care au cel mai mare număr de celule.
Această condiție este verificată prin următoarea funcție:
Cu toate acestea, regula de mai sus nu acoperă toate celulele pentru care nu există nici un by-pass. Astfel, pentru o perioadă de 3 * 7 plăci, în plus față de acele celule pentru care regula dat, de asemenea, by-pass imposibil de celule (2,4).
2. Identificarea celulelor blocate
Dacă în timpul celula următoare este format, care pot fi introduse, dar în cazul în care nu se poate ieși, atunci o astfel de mișcare nu este permisă, cu excepția penultima rundă. Această metodă de optimizare poate reduce semnificativ numărul de returnări, inclusiv atunci când este utilizat în asociere cu regula Varnsdorf.
Dezvoltarea acestei metode este de a defini grupuri de celule blocate legate între ele, dar rupți de restul bord. Î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 mari (de exemplu, dimensiunea 100 * 100 celule).
3. Aplicarea regulilor de Varnsdorf
Printre multele metode euristice [5] utilizate pentru a căuta regula de reducere Varnsdorf este cel mai simplu. În conformitate cu calul, atunci când plăcile crawling trebuie să fie de fiecare dată pentru a pune pe teren la care se poate face cel mai mic număr de lovituri pe câmpurile nu au fost încă trecut. Dacă există mai multe câmpuri, puteți alege oricare dintre ele, care ar putea totuși, face, un cal într-un impas, și cere restituirea [5]. Rețineți că cea mai bună regulă Varnsdorf lucrează pentru câmpurile unghiulare.
4. Utilizarea diferitelor matrici mișcări de cai
se mută de cai pot fi specificate, de exemplu, ca următoarea matrice:
Fiecare element definește un posibil cal curs și cuprinde o schimbare a coordonatelor sale pe bord atunci când se face progrese. Prin utilizarea matrice diferite pentru mișcările de cai se întoarcă scorul poate varia. Programul utilizează cinci matrice euristic selectate care conțin posibile mișcări de cal într-o ordine diferită. De asemenea, specificați numărul maxim de randamente (GOOD_RET), iar atunci când este atins, cale de căutare începe din nou folosind o matrice diferite. Atunci când căutați by-pass cu ultima matrice este limitat la numărul de MAX_RET se întoarce. Î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. Bypass fără întoarcere de la fiecare dintre celulele nu pot primi panourile „alungite“ (de exemplu, 14 * 3) și pentru panouri mari, cum ar fi placi de 100 x 100 celule.
software iterativ
căutare exhaustivă
Ideea unui algoritm iterativ pentru program este după cum urmează:
- la fiecare fragment pas a căutat căi pornind de la celula curentă sau cuprinde deja finalizate;
- atunci când se face progrese din gama de posibile mișcări elementul următor este recuperat, ceea ce duce la o cușcă neocupat situată în interiorul bord;
- În cazul în care cursul nu este posibil, atunci există o revenire la o celulă anterioară (eliminarea de deplasare);
- calea de căutare este considerat de succes atunci când numărul de progresul actual va fi egal cu numărul de celule de pe bord. În cazul în care celulele de la primar prin toate mutarile posibile, calea nu există.
Mai jos este structura funcției pe care iterează:
Numărul utilizat pentru fiecare variantă de accident vascular cerebral accident vascular cerebral este stocată în matrice, a cărui dimensiune este aleasă în funcție de mărimea consiliului.
Cele descrise iterează algoritm prin opțiunile și de a găsi o soluție în cazul în care există unul. Nici o decizie conduce la o enumerare completă a tuturor opțiunilor.
Pentru a ilustra declarațiile de execuție în tabel. 1 prezintă protocolul parcurgeri dimensiunea placii de 3 pana la 4 celule cu coordonate (2,4). La finalul protocolului arată calea rezultantă a traversal.
Tabelul 1. Protocol bord dimensiune parcurgeri 3 în 4 celulei (2,4)
Pentru dimensiunea tablă de șah clasic 8 de 8, cu următoarele rezultate:
- pentru optimizări 1 și 2 în majoritatea celulelor care depășesc numărul maxim de rentabilitate (MAX_RET). Numărul minim de întoarce în celula (5,5) - 2502;
- optimizări pentru 1 și 3 în toate celulele, cu excepția (4,1) și (6,4), se întoarce la zero. In aceste celule 9 și 79 se întoarce, respectiv;
- Pentru a optimiza 1-3 din celula (6,4) Trei întoarcere. Celulele rămase returnează zero;
- 1-4 optimizări pentru toate celulele returnează zero. Astfel, în celula (6,4) din a doua matrice de posibile mișcări este utilizat.
Pentru plăcile de măsurare 9 cu 9 celule din care nu de by-pass, aceasta se realizează fără o întoarcere înapoi la optimizări 1-3 (1-4, desigur, de asemenea).
Pentru dimensiunea placii de 50-50 cu următoarele rezultate:
- 1-3 pentru optimizări în majoritatea celulelor, un zero, și numărul de întoarce în restul celulelor variază de la unitate la valori care depășesc valoarea limită;
- 1-4 optimizări pentru toate celulele returnează zero.
Pentru dimensiunea placa de 77-77, pentru celulele din care ocolesc se obțin următoarele rezultate:
- 1-3 pentru optimizări în majoritatea celulelor, un zero, și numărul de întoarce în restul celulelor variază de la unitate la valori care depășesc valoarea limită;
- 1-4 optimizări pentru toate celulele returnează zero.
Pentru mărimea consiliului 100-100 cu următoarele rezultate:
- 1-3 pentru optimizări în majoritatea celulelor, un zero, și numărul de întoarce în restul celulelor variază de la unitate la valori care depășesc valoarea limită;
- 1-4 optimizări pentru toate celulele, cu excepția celulelor (94.24) și (94.79), se întoarce la zero.
După cum sa menționat mai sus, metodele de optimizare avute în vedere pentru plăci de bază non-pătrat nu sunt la fel de eficiente. Rezultatele obținute pentru dimensiunea bord de 14 până la 3 sunt arătate în tabelul. 4.
Tabelul 4. Rezultatele pentru placa de program 14 3
programul recursiv
Soluția cea mai bine cunoscută pentru a eluda problema de cal - recursive [2]. Iterațiile structura funcții are următoarea formă:
În acest program toate tipurile de optimizări pot fi utilizate așa cum este descris mai sus.
Program gratuit de decupare
În cazul în care primele două programe pentru a aborda această problemă sunt destul de tradiționale [2] Automatul pentru cei care nu sunt relevante.
Rețineți că programul de automate pot fi construite în mod formal așa cum este descris mai sus programul iterativ folosind metoda descrisă în [7]. Program de tăiere liberă poate fi construit în mod formal și având în vedere un program recursiv folosind metoda propusă în [8].
În plus, aveți posibilitatea să creați un program de mașină-gun prin construcție directă a mașinii pe condițiile problemei. Fig. 1 și 2 pentru acest automaton arată conexiunile circuitelor corespunzătoare și graficul de tranziție Mealy automatului.
Fig. 1. Schema de link-uri pentru mașini tur cavaler
Această mașină utilizează funcțiile și variabilele definite într-un program iterativ. Prin urmare, programul automaton aplică toate metodele de mai sus de optimizare, obținute cu ajutorul rezultatelor coincid cu rezultatele programului iterativ.
Fig. 2. tranziție grafic mașină pentru tur cavaler
Funcția de text simplificat care pune în aplicare această mașină, este după cum urmează:
concluzie
După cum sa menționat mai sus, iterativ, automaton și programe recursiv pot obține aceleași rezultate, dar mai defrișărilor în detrimentul separării explicite a statelor.
Această lucrare a fost sustinuta de Fundatia Romana pentru Cercetare de baza in conformitate cu acordarea №02-07-90114 „Dezvoltarea tehnologiei de programare automate.“
literatură
Structuri de date N. Wirth Algoritmi + = programe. Mir: Mir, 1985.
roman M. Gardner matematică. Mir 1974.
Geek E. Șah și matematică. M. Nauka, 1983.
Shamgunov Nikita Nazimovich - campion de trei ori din Urali de programare, de doua ori finalist campionat mondial pentru programarea ACM, un student absolvent SPbGITMO (TU).