COIN-OR::LEMON - Graph Library

Changes between Version 1 and Version 2 of Heurisztikus útvonalkeresés


Ignore:
Timestamp:
07/02/10 20:12:55 (9 years ago)
Author:
Peter Kovacs
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Heurisztikus útvonalkeresés

    v1 v2  
    99A legegyszerűbb javítási ötlet a [http://en.wikipedia.org/wiki/Bidirectional_search kétirányú keresés]: a megadott két pontból "párhuzamosan" indítunk el egy-egy keresést, és ha a két keresés "összeér", akkor a megkapott eredményekből előállítjuk a legrövidebb utat. A gyakorlati megvalósítás nehézsége a részletek körültekintő kidolgozása és implementálása.
    1010
    11 Az ún. [http://en.wikipedia.org/wiki/A*_search_algorithm A* algoritmus] pedig egy heurisztikus módszer, amely egy alkalmas távolságbecslést felhasználva a Dijkstra-algoritmusnál "ügyesebben" irányítja az útvonalkeresést, ezáltal sokszor lényegesen gyorsabban találja meg a célcsúcsba vezető legrövidebb utat.
     11Az ún. [http://en.wikipedia.org/wiki/A*_search_algorithm A* algoritmus] pedig egy heurisztikus módszer, amely egy alkalmas távolságbecslést felhasználva a Dijkstra-algoritmusnál "ügyesebben" irányítja az útvonalkeresést, ezáltal sokszor lényegesen gyorsabban találja meg a célcsúcsba vezető legrövidebb utat. Ennek a módszernek is létezik kétirányú változata.
    1212
    1313Ezeken kívül számos bonyolultabb módszert is kidolgoztak, főleg olyan esetekre, amikor sok pontpár között keresünk legrövidebb utat, így érdemes lehet valamilyen előfeldolgozást végezni, és a kiszámított adatokat felhasználni a lekérdezések megválaszolásához. Ehhez a témakörhöz rengeteg anyag található ezen az oldalon: [http://algo2.iti.uka.de/schultes/hwy/].