Mohó útvonalválasztás számításigényének csökkentése heurisztikus módszerekkel

Szerző: 
Sebők Tamás
Év: 
2013
Szekció: 
Hálózattervezés
Helyezés: 
1. helyezés
Különdíj: 
Trón Tibor Emlékdíj
OTDK éve: 
2015
OTDK szekció: 
Algoritmusok
OTDK helyezés: 
OTDK különdíj

A mohó továbbítás a földrajzi útvonalválasztás alapját képező módszer, amit metrikus térbe ágyazott hálózatoknál használnak. Az élet számos területén fordulnak elő ilyen metrikus hálózatok, a legelterjedtebben a vezeték nélküli hálózatok körében használt a földrajzi útvonalválasztás.

A mohó útvonalválasztás egy egyszerű ötletre épít: a hálózatban lokális döntések segítségével próbáljunk egy globálisan is jó útvonalat találni. A mohó útvonalválasztást nem csak az egyszerűsége (csak lokális információk kellenek a döntéshez) teszi népszerűvé, hanem az elosztott működése is. Nincs szükség a teljes hálózat ismeretére az útvonalválasztáshoz, nem kell az útvonalat előre meghatározni, az útvonal a továbbítás közben, lokális döntések következtében alakul ki.

Azonban a mohó továbbítással kapcsolatban vannak megoldandó problémák. A legnagyobb probléma a számításigénye, ugyanis a mohó algoritmus mindig a lokális optimumot keresi. Ehhez meg kell vizsgálni minden szomszédot, ezért meghatározása sok szomszéddal rendelkező csomópontok esetén költséges lehet. A dolgozatban azt mutatom meg, hogyha a továbbításnál lemondunk a lokális optimum megkereséséről, és heurisztika segítségével próbálunk egy lokálisan jó (de nem feltétlenül a legjobb) döntést hozni, akkor közel olyan jó megoldáshoz jutunk lényegesen kevesebb számítással, ezáltal sokkal gyorsabban.