Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2011-2012‎ > ‎

5. óra

2011.10.17.

Néhány szakkörön útkeresési algoritmusokkal fogunk foglalkozni. Először a súlyozatlan gráfok kerülnek terítékre.

Feladat

Legrövidebb út négyzetrács alapú labirintusban


A legrövidebb utakat meghatározó algoritmusok tárgyalását egy speciális esettel kezdjük: egy négyzetrácson mozoghatunk, mindig élszomszédos mezőkre léphetünk, és bizonyos mezők tiltottak ("fal"). Keressük két megadott mező közötti távolságot, lépésekben számolva. Például kérdés lehet, hogy milyen messze van a piros mező a zöld mezőtől:

A választ a szélességi keresés adja, ami ilyen "térképen" nagyon egyszerűen programozható: a kiinduló mezőre 0-t írunk, a szomszédaira (ahova lehet lépni) 1-et, majd általában ha minden K-t beírtunk, akkor az összes K még be nem járt szomszédaira K+1 kerül. Ha elértük a piros mezőt, akkor az oda írt szám pontosan a keresett távolságot mutatja.


Az algoritmus helyességének belátásához csak azt kell észrevenni, hogy pontosan azok a mezők vannak N távolságra a kiinduló mezőtől (N>1), amelyeknek van olyan szomszédja, amely N-1 távolságra van a starttól. A megvalósításnál arra kell vigyázni, hogy csak akkor kezdjünk K értékeket beírni, amikor már az összes K-1 távolságra lévő mezőt megjelöltük. Ezt legegyszerűbben a sor adatszerkezet használatával tehetjük meg:

d[START] := 0
Sorba(Start)
Ciklus amíg a Sor nem üres
    x := Sorból
    Ciklus x jelöletlen y szomszédain
        d[y] := d[x]+1
        Sorba(y)
    Ciklus vége
Ciklus vége

Rekurzív megoldás

Ha nem akarunk Sor-ral dolgozni, egy rekurzív megközelítés is működhet. Azonban az órai elemzések azt mutatták, hogy ez a megoldás nagyon nem hatékony, ha a labirintusban nagy üres termek vannak.

A rekurzív eljárás:

Eljárás bejár(x)
    Ciklus x négy lehetséges y szomszédjára
        Ha y nem fal és d[y] > d[x]+1 akkor
            d[y] := d[x]+1
            bejár(y)
        Elágazás vége
    Ciklus vége
Eljárás vége


A keresés indítása:

d[] := végtelen; d[START] := 0
bejár(START)