Front	Választás	Segéd

Branch and Bound, leírás, értelmezés

Készítette: Debreceni Bálint, 3. éves programtervező informatikus hallgató

Mesterséges intelligencia tárgybeadandó

A program egy felhasználó által felépített irányított gráfban, ahol az élek súlyértékekkel rendelkeznek, alkalmas az egy csúcsból egy másik csúcsba vezető összes út megtalálásához, és először a legrövidebb utat (költségek értelmében) találj meg. A használt algoritmusok Branch and Bound módszer, és a program minden lépését mutatja az algoritmusnak.
Program felépítése:
Bal oldal: kezelő felület
Középső rész: animálás és építés rész
Jobb oldal: segédtáblázat

1.lépés:

A "Csomópont létrehozása" gombbal elkezdünk létrehozni csúcsokat. (Ha többször nyomjuk meg, és közbe a keletkezett csúcsokat nem mozgatjuk, akkor egymásra rakja őket, ilyenkor is fogjuk tudni mozgatni őket). Ha egy csúcsba belekattintunk, akkor az egérrel együtt követni fogja mozgásunkat, tehát tetszőleges helyre rakhatjuk. Ha a kívánt helyre vittük, akkor kattintunk (bele) megint egyszer, és elengedi. A létrehozott csomópontokat számozza a program, ezzel azonosítjuk őket, név megadására nincs lehetőség.

2. lépés:

Élek létrehozása. Tetszőleges két csúcs között él hozható létre / törölhető a program által és az irányítása is megadható. Válasszunk ki, vagy ha még nincs hozzunk létre két csúcsot. Ez úgy lehetséges, hogy duplán kattintun egy csúcsba. Ha még egyik csúcsba se kattintottun duplán, akkor az első ilyen csúcs (világos) sárga színű lesz. Természetesen még ekkor nem hozhatunk létre még élet, mert kell még egy végpont. Kattintsunk bele duplán másik csúcsba is.Ekkor ennek zöld színe lesz. Így már csak ki kell választani az irányítást. Ezt egy jelölőcsoporttal tehetjük meg. Ha a zöldből sárgába szeretnénk az irányítást, akkor "Zöldből sárgába" opciót válasszuk a bal oldalt az irányítás megadása alatt. Ellenkező esetben a másik opciót. Ha az opció bejelölése megtörtént, kattintsunk az "él létrehozása" gombra. Két csúcs között ha létezik él, akkor az előbb ismertetett módon kijelölünk dupla kattintásokkal két csúcsot, és rámegyünk az "él törlése" gombra (törléskor nem szükséges az irányítást megadni, azt akkor már felismeri a program)
Dupla kattintás esetek:

Egy csúcs sincs megjelölve: először duplán kattintott csúcs sárga
Egy csúcs már megvan sárgával jelölve: amennyiben ebbe kattintottunk megint, eltűnik a kiválasztás. Ha nem zöld lesz
Egy csúcs már megvan sárgával jelölve és egy másik is zölddel: amennyiben a zöldbe kattintottunk megint, eltűnik a zöld kiválasztás,a sárga megmarad. Ha a sárgába, akkor a sárga jelölés eltűnik, és másik zöld lesz sárga színű. Ha nem színezettbe kattintottunk duplán, akkor a zöld lesz sárga színű, és az üres színű lesz zöld.

VIGYÁZAT: néha kicsit többször kattintunk, mint duplán és elkezd a színezett csúcs mozogni. Ekkora kattinstunk egyszer bele (ne duplán) és akkor a mozgás megszűnik, a kijelölés megmarad.

3. lépés:

Súlyok adása az éleknek. Duplakattintással kijelölt, éllel rendelkező csúcsoknak érték adható. Ez úgy történik meg, hogy kiválasztunk dupla kattintásokkal két olyan csúcsot ami között él fut (irányítása súly megadása szempontjából mindegy mert a programba két csúcs között csak egyféle irányítású él vezethet, tehát oda vissza egy csúcsból másikba nem mehetünk). Ha ez megtörtént, akkor a "Kijelölt él súlyának megadása:" szövegmezőbe adjuk meg a kívánt súlyt (pozitív szám, nem nulla), majd a módosítás gombra kattintva az él felett (néha kicsit az élbe) megjelenik az érték. A PROGRAM SIKERES FUTÁSÁHOZ MINDEN ÉLNEK KELL ÉRTÉKET ADNI!

4. lépés

Az útkeresés indítása, ábrák értelmezése Miután, minden lépést és szabályt betartva, felépítettük a gráfunkat, elkezdhetünk utakat keresni. Jelöjük ki duplakattintássl az induló csúcsnak szánt csúcsunkat (ez sárga színű lesz), majd egy másikat, ahova elszeretnénk jutni (ez zöld lesz). Majd ha ez megtörtént, kattintsunk "Branch and Bound" nyomógombra. A gomb lenyomása után egy animációba csöppenünk. Az animáció 3 féle színt használ (világos zöld, világos kék, piros). Először eltűnnek a dupla kattintáskor keletkezett színeink. Majd egy idő után (kb. 2 másodperc), a kezdő csúcs zöld színű lesz. Majd jelezve, hogy a front csúcsai innen indulnak, 2 másodperc múlva kék színű lesz. Ekkora a front-on lévő csúcsok piros színnel lesznek jelölve, majd az algoritmus szerint kiválasztódik egy, ez zöld színnel lesz jelölve. Következő lépésben már kék színnel ez is jelölve lesz, meg azok a csúcsok is, amik az induló csúcstól az ide (a front csúcsig) vezető utat alkotják. Innentől szokásosan a front csúcsok pirosak lesznek, majd az algoritmus szerint kiválasztódik egy (amelyikkel a költség a legkisebb), és folytatódik tovább a kék, piros, zöld színezés. Mindeközben azonban a színezés mellett látunk egy "segédtáblázatot" is, amelyben a színezési döntések jobban látszódnak. Minden sora (az elsőt leszámítva), tartalmaz 3 oszlopot : front, választás segéd. Világos kékkel mindig azokat a csúcsokat látjuk, amelyek alkotta útban a következő csúcs a front lenne. Tehát ezek azután színeződnek be pirossal, miután kirajzoltuk a kék csúcsokat. A választás az azt a csúcsot írja le, amit a front-ba kiválasztunk. A segéd oszlopból az látható, hogy a front csúcsok melyik útvonalakhoz kapcsolódnak, és azon útvonalaknak a frontot hozzávéve mennyi a költségük (K:). Ezek közül választja a minimálisat,és azok utolsó csúcsja az a front csúcs, amit a választás során látunk. A kiválasztott front csúcs zölddel jelölődik. Egy segéd bejegyzés szerkezete: [ csúcsok (fronttal együtt) ] K: költség Onnan tudjuk, hogy elértük a célt, hogy útvonal van kékkel jelölve, és hozzá egy zöld lesz. A táblázatban ilyenkor a front csúcs egyelemű, megegyezik a kiválasztott csúccsal, és a célként megjelölt csomópont. Az algoritmus minden utat megtalál, de először a legrövidebbet fogja megtalálni. Ha az algoritmus lefutása során kiszeretnénk próbálni megint ugyanezen a gráfon, akkor megint válasszuk ki a start (sárga) és cél (vigyázat, sötétebb zöld) csúcsot. Az algoritmusból maradtak színek a lefutás során az utolsó lépésből, de ezekbe is nyugodtan kattinthatunk simán (mozgatáshoz) vagy duplán (start, cél, élmódosítás kijelöléséhez). Esetleg újbóli lefutás előtt adhatunk csúcsot hozzá, törölhetünk élt, avagy módosíthatunk él értéket).

AZ ALGORITMUS FUTÁSA/ANIMÁLÁSA ALATT NE VÁLTOZTASSUNK SEMMIT A GRÁFON, ÉS NE NYOMJUNK LE SEMMIT A KEZELŐFELÜLETRŐL! AZ ALGORITMUS VÉGE UTÁN (nem tapasztalunk változást + a tábla 2 másodpercig nem változik) ÚJRA MÓDOSÍTHATUNK / FUTTATHATUNK. PÉLDA: (LSD PDF)