Tämän verkkosovelluksen avulla voit tarkastella graafista esitystä erilaisista graafihakualgoritmeista samalla kun ratkaiset valitsemasi 8-puzzle-ongelman.
Aloittaminen
Tämän sovelluksen vasemmalla puolella on ohjauspaneeli. Ohjauspaneelin avulla voit määrittää sovelluksen seuraavat asiat:
- Alkutila ja tavoitetila
- Käyttämäsi hakualgoritmi
- Käyttämäsi heuristinen funktio, jos käytät informoitua hakualgoritmia
- Ja se, haluatko käyttää single-step- vai burst-tilaa
Jokaista näistä vaihtoehdoista kuvataan yksityiskohtaisemmin jäljempänä.
Alku- ja tavoitetilat
Alku- tai tavoitetilojen asettamiseksi voit napsauttaa joko ”Muokkaa tilaa”-painiketta tai tilan graafista esitystä.
Sinulle pitäisi avautua seuraavan kaltainen ponnahdusikkuna:
Muuttaaksesi laattaa napsauta laattaa, jonka haluat korvata, ja syötä sitten näppäimistöllä uusi arvo. Tämä vaihtaa laatan siihen laattaan, jossa kyseinen arvo oli aiemmin.
Hakualgoritmi
N-Puzzle tukee viittä eri graafipohjaista hakualgoritmia. Kolme ensimmäistä ovat tietämättömiä hakualgoritmeja:
- Breadth-first Search
- Depth-first Search
- Iterative Deepening Search
Kaksi muuta ovat tietämättömiä hakualgoritmeja:
- A*-haku
- Greedy-haku
Jos valitset informoidun hakualgoritmin, sinun on myös valittava heuristinen funktio.
Heuristinen funktio
N-Puzzle tukee kolmea erilaista heuristista funktiota:
- Euklidinen etäisyys
- Manhattanin etäisyys (Kaupunki-kortteleiden välinen etäisyys)
- Laatat poissa-paikalta
Yksiaskel- tai purskepelitila
N-Puzzlea voi käyttää kahdessa tilassa. Oletusasetuksena on Single-Step-tila, jossa voit ”kelata” etsintää askel kerrallaan. Tämä on hyödyllistä, kun haluat saada paremman käsityksen siitä, miten hakualgoritmi toimii.
Toinen tila on Burst-tila. Kun Burst Mode on käynnistetty, se jatkaa haun suorittamista, kunnes tavoitetila on löydetty. Burst Mode -haun voi keskeyttää, mutta sitä ei voi ”kelata”.
Hakupuu
Tilan esitys
Haun ollessa aktiivinen voit nähdä hakupuun visuaalisen esityksen. Jokainen solmu tässä hakupuussa edustaa laattojen järjestelyä (tai tilaa), ja se on piirretty laatikkona, joka on jaettu neljään osaan.
Seuraavassa kaaviossa on esitetty solmu, joka on otettu Greedy-hausta:
Suurin osa on palapelin tila. Sen alapuolella on kaksi pienempää osiota.
Palapelitilan alapuolella on kaksi osiota. Vasemmalla oleva osio on solmun syvyys. Oikeanpuoleinen osio on heuristinen pistemäärä. Heuristista pistemäärää käytetään vain informoitujen hakualgoritmien kanssa, joten jos käytät Breadth-first-, Depth-first- tai Iterative Deepening Search -hakua, heuristinen pistemäärä jätetään pois.
Viimeiseen osioon kirjataan järjestys, jossa solmut laajennettiin. Esimerkiksi juurisolmu on aina ’#1’, ja seuraavaksi laajennettu solmu merkitään ’#2’.
Solmujen värit
Hakupuun ’luettavuuden’ parantamiseksi jokaisen solmun reuna on värikoodattu sen hetkisen tilan mukaan.
Seuraavassa kuvassa on esitetty A*-algoritmi (Euklidisen etäisyyden heuristiikalla) sovellettuna ongelmaan, joka voidaan ratkaista vain kahdella siirrolla:
Värit voidaan tulkita seuraavasti:
| Väri | Merkitys |
|---|---|
| Sininen | Jos solmu on avoimessa luettelossa, se korostetaan sinisellä. |
| Punainen | Kunkin hakualgoritmin iteraation jälkeen solmu, joka laajennetaan seuraavaksi, korostetaan punaisella. Tämä pätee silloinkin, kun tavoitesolmu on löydetty. |
| Grey | Jos tila on tutkittu, se harmaantuu. Esimerkiksi yllä olevan kaavion vaiheessa 2) alkutila on värjätty harmaaksi merkiksi siitä, että se on tutkittu. Vaiheessa 3) alkutilaa edustava solmu löydetään uudelleen, mutta sitä ei laajenneta, koska alkutila on laajennettu juurisolmun kautta. |
| Vihreä | Kun tavoitetila on löydetty, se korostetaan vihreällä. |
| Kultainen | Kun tavoitetilaa edustava solmu on löydetty, kaikki solmut polulla takaisin juurisolmuun korostetaan kullanvärisinä. |
| Purppurainen | Käytettäessä iteratiivista syventävää etsintää, maksimisyvyyden ylittäviä tutkimattomia solmuja ei lisätä avoinna olevien solmujen luetteloon. Nämä solmut värjätään violetilla. |
Avaiset ja suljetut luettelot
Hakualgoritmien ollessa käynnissä ylläpidetään kahta luetteloa. Ensimmäinen on Avoin lista – tätä käytetään pitämään kirjaa solmuista, jotka on löydetty, mutta joita ei ole vielä tutkittu.
Toinen on Suljettu lista – tätä käytetään pitämään kirjaa solmuista, jotka on tutkittu, tai solmuista, joita ei tutkita, koska ne edustavat tiloja, jotka on jo tutkittu muiden solmujen kautta.
Kun haku on aktiivinen, avoimen ja suljetun listan solmujen määrä näkyy vasemmassa yläkulmassa:
Credits
.