Iti0210lab23

Allikas: Lambda

Tee leidmine kaardil

Sissejuhatus

Lahendame ülesannet, kus tuleb leida teekond kaardil alguspunktist soovitud sihtkohta. Ülesanne koosneb järgmistest osadest:

  • laiutiotsing (väike kaart)
  • otsing suuremal kaardil
  • heuristiline otsing

Esimene katsetus otsinguga

Antud on kaks kaarti. Kaardi formaat on ASCII-art - ebakonventsionaalne, aga harjutusülesandeks kõlbab küll. Tuleb leida tee kaardil alguspunktist "s" teemandini "D". Seejuures ei tohi tee läbida kohti, kus on laava (tähistus "*"). Liikuda tohib ainult neljas suunas: üles, alla, vasakule ja paremale (mitte diagonaalis).

Kaart 1:

lava_map1 = [
    "      **               **      ",
    "     ***     D        ***      ",
    "     ***                       ",
    "                      *****    ",
    "           ****      ********  ",
    "           ***          *******",
    " **                      ******",
    "*****             ****     *** ",
    "*****              **          ",
    "***                            ",
    "              **         ******",
    "**            ***       *******",
    "***                      ***** ",
    "                               ",
    "                s              ",
]
start_row=14
start_col=16

Kaart 2:

lava_map2 = [
    "     **********************    ",
    "   *******   D    **********   ",
    "   *******                     ",
    " ****************    **********",
    "***********          ********  ",
    "            *******************",
    " ********    ******************",
    "********                   ****",
    "*****       ************       ",
    "***               *********    ",
    "*      ******      ************",
    "*****************       *******",
    "***      ****            ***** ",
    "                               ",
    "                s              ",
]
start_row=14
start_col=16

Seda kaarti võib vaadata kui ruudustikku, kus iga ruutu tähistab tema x ja y koordinaat. Tee leidmiseks kasutame laiutiotsingut (breadth first search, BFS). Laiutiotsingu tööpõhimõtte animatsioone vaata siit lehelt. Sel viisil otsides laava vältimine on tegelikult lihtne - tuleb lihtsalt laavaga ruute käsitleda, nagu läbimatut seina. Kui algoritm on tee leidnud, siis uurime ka, kuidas tema leitud tulemust tõlgendada ja visualiseerida.

Enne, kui otsingut saab alustada, tuleb kindlaks määrata alguspunkt. Seega otsusta, mida tähistad x ja y koordinaatidena (üks peaks olema read, teine veerud). Mõlemal kaardil on alguspunkt 14. reas, 16. veerus, kusjuures Pythoni indeksite nummerdamine hakkab 0-st.

Samuti tee kindlaks kaardi suurus x ja y suunas. Otsingu implementeerimisel tuleb paratamatult kontrollida, kas mingi koordinaadipaar on kaardil või sellest väljas.

Laiutiotsing

Kasutame kooditükki siit.

frontier = Queue()
frontier.put(start)
came_from = {}
came_from[start] = None

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in came_from:
         frontier.put(next)
         came_from[next] = current

Antud kood alustab otsimist start punktist ning leiab tegelikult teed kõikidesse punktidesse graafil graph. Seejuures saab leitud teid rekonstrueerida selle alusel, et kui came_from[A] == B siis tee punktist A alguspunkti läheb läbi B - see tähendab, et tee tuleb rekonstrueerida tagurpidi sihtpunktist alguspunkti.

Kuna meie ülesanne on pisut erinev, siis peame koodi pisut kohandama. Lisaks realiseerime selle funktsioonina, nii et oleks mugav erinevaid kaarte ette anda.

from queue import Queue

def minu_otsing(kaart, start):
    # start (algolek) on näiteks tuple kujul (x, y)

    frontier = Queue()
    frontier.put(start)
    came_from = {}
    came_from[start] = None

    while not frontier.empty():
        current = frontier.get()

        # meid ei huvita kõik teed, seega peaks kontrollima, kas current on teemant.
        # Kui on, siis katkestame otsingu
        # (ja loomulikult jätame teemandi koordinaadid meelde)

        for next in graph.neighbors(current):  # see osa tuleb suht palju ümber teha.
                                               # tuleb leida sobivad naaberruudud kaardilt
                                               # nagu ta meile ette on antud (ülal, all,
                                               # paremal ja vasakul olev ruut)
            if next not in came_from:
                frontier.put(next)
                came_from[next] = current


    # Kui teemant on leitud, tuleb ka teekond rekonstrueerida
    # mis andmestruktuurina teekonda esitada, pole oluline,
    # aga loomulik viis oleks list
    return path

Suuremad kaardid

Proovi nüüd otsingut kaartidel suuruses 300x300 kuni 900x900 (paremklõps ja Save as vms):

Enne kaardi kasutamist tuleb see failist laadida. Et saada samas formaadis kaart, nagu eelmises ülesandes, võib järgmist koodi kasutada:

with open("cave300x300") as f:
    map_data = [l.strip() for l in f.readlines() if len(l)>1]

Alguspunktide ja teemandi asukohtade koordinaadid:

kaart rida veerg
300x300 start 2 2
goal 295 257
600x600 start 2 2
goal 598 595
900x900 start 2 2
goal 898 895

Ahne otsing

Lisame nüüd heuristilise otsingu - see tähendab, et kasutame mingit meetodit et umbkaudu hinnata, mis tee kiiremini lahenduseni viib.

Inspiratsiooni heuristilise otsingu tegemiseks saame jälle siit tutorialist. Samast leiad ka animatsioone ja selgitusi nende algoritmide käitumise kohta.

Ahne otsingu ja laiutiotsingu peamine erinevus on, et ahne otsing üritab liikuda eelistatult eesmärgi suunas. Selleks valitakse alati selline järgmine punkt, mis on eesmärgile kõige lähemal. Leitud punktide automaatseks järjestamiseks kasutame PriorityQueue-t.

from queue import Queue, PriorityQueue

Tee uus greedy funktsioon, mis on koopia laiutiotsingust ja millel on lisaks parameeter goal (seda on vaja heuristiku jaoks). Muuda seda järgmiselt:

frontier on alati sorteeritud elemendi väärtuse järgi (mitte lisamise järjekorras)

    frontier = PriorityQueue()
    frontier.put((0, start))

Uued ruudud lisatakse koos heuristilise väärtusega, mis aitab õigesti sorteerida.

             priority = h(next, goal)
             frontier.put((priority, next))

Kuna järjekorra formaat muutus, siis tuleb ka sealt asju teistmoodi välja võtta:

        _, current = frontier.get()

Lõpuks on meil vaja ka heuristilist funktsiooni ennast. Kuna meil on tegu ruudustikul nelja ilmakaare suunas liikumisega, siis Manhattan distance on selleks väga sobiv.

def h(node, goal):
    # implementeeri ise

A*

Ahne otsingu ja A* vahel on ainult üks erinevus: esimesel juhul leitakse heuristiline väärtus f(n) = h(n), teisel juhul f(n) = g(n) + h(n). See tähendab, et ka senini läbitud teepikkus mängib järgmise punkti valimisel rolli. Sel viisil välditakse olukordi, kus konstrueeritud teekond suundub otse eesmärgi suunas, kuni kohtab takistust ning peab siis tagasi pöörduma.

Tee uus funktsioon astar, mis on ahne otsingu koopia.

Kõigepealt on vaja g(n) väärtusi meelde jätta.

    cost_so_far = {}
    cost_so_far[start] = 0

Heuristilise väärtuse arvutamisel tuleb senine teekond sisse arvestada. Järgmisse ruutu liikumise maksumus on alati 1. Lisaks tuleb muuta kohta, kus kontrollitakse, kas next on juba nähtud. Nimelt on võimalik, et me saabume uuesti samasse kohta lühemat teed mööda ning meid huvitab eelkõige see uus, lühem tee.

          new_cost = cost_so_far[current] + 1
          if next not in cost_so_far or new_cost < cost_so_far[next]:
             cost_so_far[next] = new_cost
             priority = new_cost + h(next, goal)    # g(n) + h(n)
             frontier.put((priority, next))
             came_from[next] = current

Tulemused aruande jaoks

Katseta laiutiotsingut, A*-i ja ahnet otsingut kõikidel kaartidel alates 300x300 suurusest.

Aruandesse pane:

  • lahenduse leidmiseks kulunud aeg (piisab kui on iteratsioonide arv, aga võib lisada ka aja sekundites)
  • lahenduse pikkus sammudes

Optimaalsed tulemused

Erinevate strateegiate käitumine 300x300 kaardil. Roheline tähistab otsingu läbitud ala, punane leitud teed.

laiutiotsing
ahne otsing
A*

Optimaalsed teepikkused

300x300 554
600x600 1247
900x900 1843

Lisaülesanded

Järgmised tegevused pole kohustuslikud, aga aitavad otsingust ja heuristikutest paremini aru saada.

Visualiseerimine

Kirjuta kood, mis leitud teekonna väljastab sellisel ASCII-art kujul (kujutatud tee on suvaline näide):

      **               **      
     ***     D....    ***      
     ***         .             
                 .    *****    
           ****  .   ********  
           ***   .      *******
 **              .       ******
*****            .****     *** 
*****            . **          
***              .             
              ** .       ******
**            ***.      *******
***             ..       ***** 
                .              
                s              

Heuristikute käitumine

Implementeeri teine heuristiline funktsioon:

 def h2(node, goal):
     return max(abs(node[0]-goal[0]), abs(node[1]-goal[1]))  # suurim koordinaadi nihe

Võrdle A* ja ahne otsingu käitumist mõlema heuristikuga kõigil kaartidel.

Seejärel muuda otsingut nii, et lubataks diagonaalis liikumisi. Mis mõju on sellel heuristikute efektiivsusele, eriti A* puhul?