Úvod do algoritmov umelej inteligencie #5 - Dijkstrov algoritmus

A ako lepšie začať sériu o vyhľadávacích algoritmoch ako algoritmami, ktoré hľadajú najkratšiu cestu?

Hľadanie najkratšej cesty - Dijkstra

Dijkstra je najjednoduchším z algoritmov pre hľadanie najkratšej cesty grafom. Asi nás neprekvapí, že najjednoduchší algoritmus nemusí byť nevyhnutne najlepší. Skúsme sa teda zamyslieť, ako nájsť najkratšiu cestu v takomto grafe (z bodu A do bodu G):

Samozrejme rátame s tým, že čísla na hranách znamenajú dĺžku (náročnosť) cesty. Na pohľad vieme určiť cestu okamžite, ale ako túto cestu nájde počítač? Dijkstra funguje zjednodušene tak, že vyhodnocuje cestu, ktorá je v danom momente najkratšia. Teda ak sa práve nachádzame v bode A, najkratším pokračovaním cesty je navštívenie bodu B. Dĺžka A-B = 3 < dĺžka A-C = 5.

Prvý krok algoritmu teda vieme vyjadriť nasledovnou animáciou:

Prvá iterácia Dijskry (tmavo modrou sú označené už vybavené body, zelenou a bledo modrou body v prioritnom zozname)

Ak by sme chceli takto pokračovať druhou iteráciou, najkratšia doteraz známa cesta má dĺžku 3, preto budeme pokračovať bodom B a druhá iterácia bude vyzerať nasledovne:

Následne by sme si vybrali bod C alebo E (keďže ich dĺžka je rovnaká) a pokračovali by sme v podobnom duchu. Celú prezentáciu k nájdeniu najkratšej cesty môžete nájsť tu.

Implementácia

Vytvorme si teda zoradený zoznam vrcholov (zoradený podľa dĺžky cesty). Každá položka tohto zoznamu bude reprezentovať vrchol, dĺžku najkratšej známej cesty k tomuto vrcholu a tvar tejto cesty. Dĺžka najkratšej cesty je prednastavená na ∞, pretože žiadnu cestu zatiaľ nemáme vyrátanú:

data class Item(
    val id: String,
    var length: Int = ∞,
    var bestPath: List = emptyList()
)

Nezabudnime ale, že najkratšia cesta z bodu A do bodu A má dĺžku 0. Teda tento bod bude v našom prioritnom zozname na prvom mieste. Náš prioritný zoznam môže teda vyzerať nasledovne:

val queue = mutableListOf(
    Item("A", 0),
    Item("B", ∞),
    Item("C", ∞),
    Item("D", ∞),
    Item("E", ∞),
    Item("F", ∞),
    Item("G", ∞)
)

A postup bude nasledovný:

1. vyberieme položku z prioritného zoznamu (položku s najkratšou cestou)

queue.sortBy { it.length }
val item = queue.removeAt(0)

2. vyberieme všetky hrany z grafu spojené s týmto vrcholom

val edges = graph[item.id]

3. Pre každú z týchto hrán:

a. vypočítame novú dĺžku od našej položky do nového bodu:

val alt = edge.length + item.length

b. Ak je táto dĺžka menšia ako doteraz nájdená, aktualizujeme položky v prioritnom zozname:

val neighbor = queue.first { it.id == edge.id }
if (neighbor.length > alt) {
    neighbor.length = alt
    neighbor.bestPath = item.bestPath + edge.id
}

4. Cyklus budeme opakovať, kým sa náš cieľový bod nenachádza navrchu nášho prioritného zoznamu. Tak budeme mať istotu, že najkratšiu cestu do cieľa s určitosťou poznáme.

Celú implementáciu v jazyku Kotlin môžete nájsť na tomto Gist-e.

Implementačné detaily

Samozrejme sa tento algoritmus bude mierne líšiť, ak budeme napríklad chcieť získať všetky trojice štart-cieľ-najkratšia_cesta, alebo ak budeme potrebovať zistiť iba dĺžku cesty (trasa nás nezaujíma). Tieto a ďalšie modifikácie Dijkstru sú však len implementačné detaily a ich vyriešenie je už na vás 🙂

Klasickým problémom/ukážkou tohto algoritmu je aj putovanie mriežkou (labyrintom). Čo tak skúsiť vyriešiť konkrétny problém? Pozrite si napríklad túto úlohu na platforme Codingame.

Problémy

Hlavný problém s týmto algoritmom je jasný. Nijakým spôsobom nezohľadňujeme existenciu cieľového bodu. Teda ak vidíme mapu Slovenska a chceme sa dostať z Banskej Bystrice do Košíc, naše oči skôr sledujú cesty smerujúce na východ od Bystrice, akoby sa mali pozerať na Nitru alebo Bratislavu.

To ako nasmerovať pohľad algoritmu smerom cieľu si ukážeme pri algoritme A*

Materiály

Tu uvádzam vynikajúce materiály k problematike Dijkstra Algoritmu:

Najlepšie vysvetlenie tohto algoritmu vieme nájsť vo videu od Computerphile. (S drobnou chybičkou a to, že cyklus ukončuje predčasne - pozri bod 4. nášho algoritmu)

Pseudokód je postačujúci ten na wikipédii.

A obľúbeným zdrojom sú aj prednášky od MIT.

Ďalšie časti série o algoritmoch umelej inteligencie:

• HillClimbing
• TabuSearch
• Simulované žíhanie
• Genetické algoritmy