Bypass ló sakktábla
Hogyan lehet megkerülni a ló sakktábla, anélkül, hogy bármilyen területen kétszer, és térjen vissza az eredeti sejt?
Nagyon helyesen, a „ló persze” azt jelenti a magyar nyelv nagyon okos és nem triviális ötlet. Ez a feladat szegélylécek elég kemény dió, amely szakít a fogak még néhány szakember. Nem, persze, meg néhány egy kör nem olyan nehéz. Például, akkor könnyen felhívni a papíron bypass útvonalon ló táblák 4x4, majd szünet 4. Az útvonal közelében a tábla közepén, és ragasszuk őket egy útvonalat. Egy másik ismert eljárás szerint először bypass „fringe” szélessége a tábla két cellában, majd - 16 központi sejtekben.
De én érdekel ez a történet (és mindig is kíváncsi) a megvalósítása egy adott kijátszásának szinte kézzel, és valami teljesen mást. Tegyük fel például, kerülőút már megkezdődött - a ló már járt néhány sejtből. Meg tudjuk befejezni ezt a túrát? Ha igen, hogyan tovább? Nyilvánvaló, hogy itt a probléma nem függ az adott méretű és még az alakja a fórumon. Pontosan ugyanaz a probléma tudunk egy teljesen önkényes grafikonon. Az egyetlen dolog, amit akarunk itt ló és ellátás - az, hogy tudja, melyik sejtek ló „szomszédos”, és mi - nem.
Ez csak ebben a feladatban, a teljes lista az összes rendelkezésre álló lehetőséget, még a mai számítógépek, ezért meg kell keresni más módon. Tény, hogy a jó ötletek már régóta ismertek. Például tudjuk, hogy a szabály: a ló mindig ugrik a cellában, amely a számos lehetséges mozog ez a legkisebb. És ha több cella? Nincs egyetlen recept, mint látható, nincs ...
Itt még vásárolni egy kész megoldás programot Pascal. De még ennél is érdekesebb, hogy foglalkozik az algoritmus is.
Hogyan lehet megoldani a problémát a vak Panov - egy emlékeztető trükk!
Algoritmusok diszkrét matematika erre a problémára - shamiltonov ciklus és azon túl.
A szabály, amely, úgy tűnik, indokolt a gyakorlatban, de elméletileg még nem erősítették meg a következő: minden alkalommal megyünk ló vissza, ahol ez veszélyezteti a legkisebb számú még nem telt el a sejteket.
Egy másik módja az, hogy talál egy útvonalat a félpanzió, szimmetrikus kettős, és a kapcsolat mindkét utat.
Eredeti általában ad lineáris idő algoritmus szegélylécek. Azt javasolták, Varnsdorf (Warnsdorff) 1983-ban.
A szabály megfogalmazása nagyon egyszerű: a következő lépés a ló, hogy nem egy cellában, ahol a lehető legkevesebb mozog. Ha ugyanaz a sejtek száma a mozgást, akkor lehet választani.
A gyakorlatban ez nem valósul meg, például, a következők szerint. Mielőtt minden mozog a ló értékelték értékelés legközelebbi elérhető területeken - mely területeken a ló még nem volt, és tudja mozgatni egy körben. Értékelés mező határozza meg a rendelkezésre álló területek mellette. Minél alacsonyabb a minősítés, annál jobb. Aztán előrelépést tett a helyszínen a legalacsonyabb minősítés (a bármely olyan, ha egynél több), és így tovább, amíg van hová menjen.
A heurisztika mindig dolgoznak a táblák 5x5 legfeljebb 76x76 sejtek nagy tábla mérete ló megtorpant. Ezen túlmenően, a szabályon alapulnak az algoritmus nem ad az összes lehetséges megoldást (azaz ló sávok), akkor mehet a szabályok ellen, és még mindig kielégítő kerek feladat.
Van egy lineáris algoritmus táblák bármilyen méretű, amely elválasztja a tábla kisebb darabokra, de azért, mert a rengeteg különleges esetekben, ez elég bonyolult, és nem olyan érdekes, mint az elegáns heurisztikus.
Egy másik módja a probléma megoldásának, nyilván, a mellszobor visszavonulást. Az alábbi ábra adott megközelíteni a fedélzeten 8x8.
Használata kétdimenziós tömbben sorban [64] és a Col [64] tárolására a sorszámokról, illetve és oszlopok egymás ló áthalad a fedélzeten.
A ló, amely abban a helyzetben (i, j), akkor a következő lépés, hogy a sejtekben koordinátái (i-2, j + 1), (i-1, j + 2), (i + 1, j + 2), ( i + 2 j + 1), (i + 2 j-1), (i + 1, j-2), (i-1, j-2), (i-2, j-1). Vegye figyelembe, hogy ha a ló szélén a tábla, néhány lépést is okozhat a mozgás a ló túl, hogy természetesen elfogadhatatlan. Nyolc lehetséges elmozdulások ló lehet adni formájában két tömb ktmov1 [] és ktmov2 [], amint azt az alábbi program fragmens.
Ennek megfelelően, ló, pozícióban található (i, j) mozogni tud egy olyan helyzetbe, (i + ktmov [k], j + ktmov2 [k]), ahol k - bármilyen értéket a tartományban 0-7 kiválasztott feltételekkel hogy a ló maradjon a táblán. Így a program, amely megvalósítja a mozgás a ló összhangban a fenti feltételek a következők lesznek:
int arr [8] [8], row [64], Col [64];
int ktmov1 [8] = <-2, -1, 1, 2, 2, 1, -1, -2>;
int ktmov2 [8] = <1, 2, 2, 1, -1, -2, -2, -1>;
int i, j, move_num, d;
addknight () regisztrálni int a, b, e;
/ * Mark a cellát egy látogatást, és emlékszik a koordinátákat a cell * /
arr [i] [j] = 1;
sorban [move_num] = i;
Col [move_num] = j;
move_num ++;
/ * Ellenőrizze lehetséges mozgását a ló 8 * /
az (a = 0; <= 7 ; a++ ) /* если все ходы сделаны, печатаем их */
ha (move_num> = 64) writeboard ();
exit (0);
>
/ * Határozza meg a sorok és oszlopok a következő körre * /
b = i + ktmov1 [a];
e = j + ktmov2 [a];
/ * Ellenőrizze, hogy miután császármetszéssel futó ló marad a sakktáblán * /
if (b <0 || b> 7. || e <0 || e> 7)
tovább;
/ * Ellenőrizze, hogy voltunk már a cell * /
ha a (arr [b] [e] == 1)
tovább;
i = b; J = e;
addknight ();
>
/ * Csökkenti az agyvérzés ellen, és próbálja meg, hogy a következő lépés * /
move_num--;
/ * Engedje el a sejt által korábban elfoglalt ló * /
arr [sorban [move_num]] [col [move_num]] = 0;
move_num--; / * Próbáld ki, hogy a következő lépés * /
i = row [move_num]; J = col [move_num];
move_num ++;
>
writeboard () int a;
clrscr ();
gotoxy (1, 10);
printf ( „Hit bármelyik gombot a következő lépés”);
gotoxy (1, 11);
az (a = 0; <= 63 ; a++ ) if ( a % 8 == 0 )
printf ( "\ n");
printf ( "#");
>
az (a = 0; lt; = 63; A ++) gotoxy (col [a] * 3 + 1, 12 + row [a]);
printf ( "% 3d", a + 1);
getch ();
>
>