Hledání nejkratší cesty jezdcem

Hledání nejmenšího počtu tahů/skoků koněm mezi dvěma zadanými políčky.

Vyvoříme si “mapu” vzdáleností.
Výchozí políčko ohodotíme čislem 0.
Okolní políčka do kterých se dostaneme jedním skokem číslem 1.
Pro jednotlivá políčka bude “mapa” obsahovat nejmenší možný počet skoků nutných k cestě do zmíněného políčka.
Dosud nenavštívená políčka označíme číslem -1. (Někdy se používá nějaké “velké” číslo, větší něž nejdelší možná cesta.)
Políčka kam není dovolen přístup označíme -2. (Můžeme zkusit obdelníkovou “ohradu” se zdí širokou jedno nebo dvě políčka.)

Pro zadané výchozí políčko vytvoříme mapu vzdáleností.
Až bude mapa hotová, podíváme se na vzdálenost cílového políčka.
Vlastně vyřešíme úlohu hledající nejkratší cestu ze zdaného políčka do všech možných cílových políček.
Tato úloha je stejně složitá jako hledání nejkratší cesty mezi dvěma zadanými políčky.

Funkce jump (i, k, v) predstavuje skok na souradnici (i,k).
Souradnice jsou od 0 do 7, jako indexy pole v jazyce C.
( i cislo radky, k cislo sloupce - ale to neni v nasem programu dulezite )
Posledni parametr v je pocet skoku od zacatku cesty.

Pole p predstavuje mapu vzdalenosti.

Fukce jump nejprve overi zda souradnice (i,k) lezi na sachovnici.
Pokud skocime mimo sachovnici nebudeme nic delat.

    if (i >= 0 && i < N && k >= 0 && k < N)

Podivame se na dosavadni hodnotu v poli p[i][k].
Pokud je to dosud nenavstivene policko, jdeme tam.
Pokud jsem tam jiz byli, ale hodnota v mape je vetsi nez nase v, take tam pujdeme.
Zbyvaji policka oznacena 0, 1, … v. Tam uz zname jinou lepsi cestu.
A take policka oznacena -2 (zakazana policka / prekazky). Ty take vynechame.

        if (p[i][k] == -1 || p[i][k] > v)

Pokud na policko pujdeme, nastavime p[i][k] = v.
Tj. na mape oznacime, ze zname cestu z vychoziho policka do policka (i,k) dlouhou v tahu.

Potom zkusime osm skoku do okoli. \ Ctyri skoky na souradnice i+-2, k+-1.
Ctyri skoky na souradnice i+-1, k+-2.
Vzdy to bude cesta o jeden tah delsi v+1.

Skaceme ponekud bez rozmyslu.
Mozna mimo sachovnici.
Mozna na policka, kam jiz zname lepsi cestu.
Ale o to se postara volana fukce jump.

const int N = 8;
 
int p[N][N];
 
void jump (int i, int k, int v)
{
    if (i >= 0 && i < N && k >= 0 && k < N)
    {
        if (p[i][k] == -1 || p[i][k] > v)
        {
            p[i][k] = v; // ulozit vzdalenost
 
            jump (i+2, k+1, v+1);
            jump (i+2, k-1, v+1);
            jump (i-2, k+1, v+1);
            jump (i-2, k-1, v+1);
 
            jump (i+1, k+2, v+1);
            jump (i+1, k-2, v+1);
            jump (i-1, k+2, v+1);
            jump (i-1, k-2, v+1);
 
            // jump ( cislo radky, cislo sloupce, soucasna delka cesty )
        }
    }
}

Mapu vzdalenosti inicializujeme na hodnoty -1 (nenavstivena policka).
Zvolime vychozi souradnici x0, y0 a provedeme jump (x0, y0, 0) .
Posledni nula oznacuje hodnotu, kterou ulozime do mapy na pozici startovniho policka.

int main()
{
    for (int i = 0; i < N; i++)
        for (int k = 0; k < N; k++)
            p[i][k] = -1; // -1 ... nenavstivena policka
 
    int x0 = 0; // vychozi souradnice
    int y0 = 0;
    jump (x0, y0, 0);
}

    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < N; k++)
        {
            if (p[i][k] == -1)
                cout << "."; // nenavstivene policko 
            else
                cout << p[i][k]; // pocet skoku od vychoziho dopicka
            cout << " ";
        }
        cout << endl; // konec radky
    }

0 3 2 3 2 3 4 5
3 4 1 2 3 4 3 4
2 1 4 3 2 3 4 5
3 2 3 2 3 4 3 4
2 3 2 3 4 3 4 5
3 4 3 4 3 4 5 4
4 3 4 3 4 5 4 5
5 4 5 4 5 4 5 6

Funkce jump rekurzive vola mnoho dalsi funkci jump. \ To se spatne krokuje v debuggeru.
Mnohdy pomuze omezit hloubku rekurze.

Napr. Funce jump pro v=0, zavola osm funkci jump (v=1) a ty zavolaji dalsi jump (v=2).
A dalsi volani jiz neprovedeme a podivame se na mapu.

Vlastne resime ulohu pro cesty dlouhe nejvyse dva skoky.
Policka na ktera se nelze dostat dvema skoky zustanou oznacena jako nenavstivena (nedostupna).

const int limit = 2;

    if (i >= 0 && i < N && k >= 0 && k < N && v <= limit)

0 . 2 . 2 . . .
. . 1 2 . . . .
2 1 . . 2 . . .
. 2 . 2 . . . .
2 . 2 . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

Predchozi program uklada do mapy delku cesty.
Pokud je v mape kladne cislo vime, ze cesta existuje.
Ale nemame nikde cestu ulozenu.

Vytvorime dve pole zx, zy skladujici souradnice odkud jsme prisli.
Pokud navstivime policko (i,k) a do tohoto policka jsme prisli z policka (i0,k0), nastavime

    zx[i][k] = i0;
    zy[i][k] = k0;

Tedy zx[i][k] obsahuje “i souradnici”,
zy[i][k] obsahuje “k souradnici”,
ze ktere jsme se na policko (i,k) prisli.

( Pole zx a zy obsahuji informaci o jedne z moznych cest. )
( Cest stejne delky muze byt vice. )
( Pole zx[i,k] a zy[i,k] obsahuji informaci prave o te ceste, jejiz delka je ulozena do p[i][k] ).

Pro startovaci policko a pro nevstivena policka do zx a zy ulozime -1.

Upravy naseho programu:
- Pridame pole zx, zy.
- Funkci jump pridame parametry i0 a k0 oznacujici policko odkud jsme prisli.
- Do pole zx a zy ulozime i0 a k0.
- Nasledujici skokum predame i a k jako adresu jejich predchudcu.

int zx[N][N];
int zy[N][N];
 
void jump(int i, int k, int v, int i0, int k0)
// skoc na (i,k) a je to v-ty skok, skaceme z (i0, k0)
{
    if (i >= 0 && i < N && k >= 0 && k < N)
    {
        if (p[i][k] == -1 || p[i][k] >= v)
        {
            p[i][k] = v;
            zx[i][k] = i0; // ulozit zpatecni cestu
            zy[i][k] = k0;
 
            jump (i+2, k+1, v+1, i, k);
            jump (i+2, k-1, v+1, i, k);
            jump (i-2, k+1, v+1, i, k);
            jump (i-2, k-1, v+1, i, k);
 
            jump (i+1, k+2, v+1, i, k);
            jump (i+1, k-2, v+1, i, k);
            jump (i-1, k+2, v+1, i, k);
            jump (i-1, k-2, v+1, i, k);
 
            // jump ( cilove souradnice, soucasna delka cesty, souradnice odkud skaceme )
        }
    }
}

Pole zx a zy inicializujeme na -1 ( = neni zadne predchozi policko ).
Skok na pocatecni policko x0, y0, vzdalenost 0 a predchazejici souradnice -1, -1.

int main()
{
    for (int i = 0; i < N; i++)
        for (int k = 0; k < N; k++)
        {
            p[i][k] = -1;
            zx[i][k] = -1;
            zy[i][k] = -1;
        }
 
    jump(x0, y0, 0, -1, -1); 
    /* -1, -1 ... zacatek cesty ... neni zadny skok zpet */
}

Funkci zadame souradnici i, k a chceme vytisknout cestu na toto policko.

Podivame se do poli zx a zy, tam nalezneme souradnici predchoziho policka.
Pokud tam nalezneme -1, -1 jsme na konci (cesty).

void bad_search (int i, int k)
{
    while (i >= 0 && k >= 0)
    {
        cout << i << "," << k << endl;
        i = zx[i][k];
        k = zy[i][k];
    }
}

    bad_search (N-1, N-1);

Zkusime vytisknout cestu do praveho dolniho rohu.
Cesta konci polickem 7,7.
Na toto policko jsme prisli z policka 6,5.

7,7
6,5
4,3
3,1
1,3
2,2
3,0
4,1
3,2

4,1
3,2

4,1
3,2

4,1
3,2

... atd

Uz to vidime, zmenili jsem promennou i a potom jsme se podivali na jine policko zy[i][k].
Obvykla chyba, nejak ji opravime.

void correct_search (int i, int k)
{
    while (i >= 0 && k >= 0)
    {
        cout << i << "," << k << endl;
        int t = zx[i][k]; // promennou i jeste budeme potrebovat
        k = zy[i][k];
        i = t;
    }
}

    correct_search (N-1, N-1);

7,7
6,5
4,4
6,3
4,2
2,1
0,0

Stejna funkce, ale rekurzivne.

void recursive_search (int i, int k)
{
    if (i >= 0 && k >= 0)
    {
        cout << i << "," << k << endl;
        recursive_search (zx[i][k], zy[i][k]); // zde si promennou i neznicime
    }
}

Nejprve vytiskneme predchozi casti cesty.
Az potom pridame nase policko.

void search (int i, int k)
{
    if (i >= 0 && k >= 0)
    {
        search (zx[i][k], zy[i][k]);
        cout << i << "," << k << endl;
    }
}

Vystup by mel byt jiz v uzitecnem tvaru.

0,0
2,1
4,2
6,3
4,4
6,5
7,7

#include <iostream>
using namespace std;
 
const int N = 8;
const int limit = 100;
 
int p[N][N];
int zx[N][N];
int zy[N][N];
 
void jump(int i, int k, int v, int i0, int k0)
// skoc na (i,k) a je to v-ty skok, skaceme z (i0, k0)
{
    if (i >= 0 && i < N && k >= 0 && k < N && v <= limit)
    {
        if (p[i][k] == -1 || p[i][k] > v)
        {
            p[i][k] = v;
            zx[i][k] = i0;
            zy[i][k] = k0;
 
            jump (i+2, k+1, v+1, i, k);
            jump (i+2, k-1, v+1, i, k);
            jump (i-2, k+1, v+1, i, k);
            jump (i-2, k-1, v+1, i, k);
 
            jump (i+1, k+2, v+1, i, k);
            jump (i+1, k-2, v+1, i, k);
            jump (i-1, k+2, v+1, i, k);
            jump (i-1, k-2, v+1, i, k);
        }
    }
}
 
void search (int i, int k)
{
    if (i >= 0 && k >= 0)
    {
        search (zx[i][k], zy[i][k]);
        cout << i << "," << k << endl;
    }
}
 
int main()
{
    for (int i = 0; i < N; i++)
        for (int k = 0; k < N; k++)
        {
            p[i][k] = -1;
            zx[i][k] = -1;
            zy[i][k] = -1;
        }
 
    jump (0, 0, 0, -1, -1);
 
    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < N; k++)
        {
            if (p[i][k] == -1)
                cout << ".";
            else
                cout << p[i][k];
            cout << " ";
        }
        cout << endl;
    }
 
    cout << "--------" << endl;
 
    search (N-1, N-1);
 
    cout << "O.K." << endl;
}

Jen pro ilustraci.

Zdrojové texty v GITu http://gitlab.fjfi.cvut.cz/culikzde/zalg/-/tree/master/jezdec-qt

Nebo jako .ZIP soubor http://kmlinux.fjfi.cvut.cz/~culikzde/zalg/2020/jezdec-qt.zip

Na posuvniku nastavime limit pro delku cesty.
Ve dvou mensich editacnich prvcich nastavime vychozi policko.
Stiskneme tlacitko “Run”.

Na leve schovnici se zobrazi mapa vzdalenosti.
Prostredni strom zobrazuje jednotlive volani funce jump.
Pokud ve stromu vybereme polozku, na prave strane se zobrazi mapa vzdalenosti pri vstupu do funkce jump.

void Jezdec::jump (int i, int k, int v, int i0, int k0)
{
    if (i >= 0 && i < N && k >= 0 && k < N && v <= limit)
    {
        if (p[i][k] == -1 || p[i][k] > v && ! udelej_chybu)
        {
            QTreeWidgetItem * save = top; // uloz soucasnou pozici ve stromu
            MyItem * q = zobrazStav (i, k, v, i0, k0); // vytvor ve stromu novy uzel
 
            top = q; // nyni k zobrazovani pouzivej novy uzel
 
            p[i][k] = v; // zapamatuj si cestu zpet
 
            jump (i+2, k+1, v+1, i, k);
            jump (i-2, k+1, v+1, i, k);
            jump (i+2, k-1, v+1, i, k);
            jump (i-2, k-1, v+1, i, k);
 
            jump (i+1, k+2, v+1, i, k);
            jump (i-1, k+2, v+1, i, k);
            jump (i+1, k-2, v+1, i, k);
            jump (i-1, k-2, v+1, i, k);
 
            top = save; // navrat na puvodni pozici ve stromu
        }
    }
}

Pokud budeme skákat jen na dosud nenavšívená políčka.

        if (p[i][k] == -1)

Podivejte se na zelene oznacene policko obsahujici 3.

Navic pokud je vychozi policko na hlavni diagonale, mela by mapa byt symetricka podle teto diagonaly.

Pri vetsim poctu skoku vzniknnou izolovana mista, kam se jezdec jiz nedostane.

 if (p[i][k] == -1 || p[i][k] > v)

Poznámka: podobné podmínky se vyskytují i v obecnějších algoritmech.

Dijkstrův algoritmus https://cs.wikipedia.org/wiki/Dijkstr%C5%AFv_algoritmus#Pseudok%C3%B3d_%E2%80%93_Pascal

             alt = d[u] + l(u, v);
             if (alt < d[v])              
             {
                 d[v] = alt;
             }

Floydův–Warshallův algoritmus http://cs.wikipedia.org/wiki/Floyd%C5%AFv%E2%80%93Warshall%C5%AFv_algoritmus

Ve vysledne mape na leve strane je v zelene oznacenem policku jiz spravna hodnota 1.
Na prave strane vidime, ze tam chviku byla honota 3 a potom jsme nasli lepsi cestu.

Kompletni vysledek bez omezeni poctu skoku.