Iti0210lab2

Esimene katsetus otsinguga

Sissejuhatus

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.

Ettevalmistus

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 (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

Visualiseerimine

Mittekohustuslik, aga väga kasulik lisaülesanne:

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

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