Teorija

A*: pastatytas ir pralaimėjęs

Dijkstra plečiasi į visas puses vienodai. Ieškant kelio iš Šeškinės į Naujininkus, ji su tokiu pat uolumu tiria Fabijoniškes — nes nežino, kur yra tikslas.

A* prideda vieną dalyką: įvertį, kiek dar liko. Vietoj d mazgai rikiuojami pagal d + h(v), kur h(v) yra spėjimas apie likusią kainą.

Jei h niekada nepervertina likusios kainos, atsakymas lieka teisingas — tokia h vadinama leistina (admissible). Ir tada paieška krypsta į tikslą, o šoninės šakos atkrenta anksčiau.

Skamba kaip nemokamas pagerinimas. transit jį pastatė.

Jis teisingas

TestAStarMatchesDijkstra   A* matches Dijkstra's optimum on all 120 queries

Visos 120 užklausų, tas pats optimalus atsakymas. Realizacija gera, euristika leistina, algoritmas veikia kaip parašyta vadovėlyje.

Ir jis pralaimi

                                          mūsų matavimas   prieš ranka rašytą krūvą
Dijkstra, ranka rašyta krūva                     53.4 ms   1.0
A*, container/heap + euristika                   77.2 ms   1.45x lėčiau

BenchmarkRouter duoda 1.75 karto. transit README teigia 1.05–1.09 karto lėčiau; mūsų mašinoje pralaimėjimas didesnis, ne mažesnis.

Mes jį pastatėme, ir jis pralaimėjo.

Kodėl — ir tai svarbiausia šio žingsnio dalis

A* nukerta šakas proporcingai tam, ką jo euristika mato. Tad kiek ji mato?

TestHeuristicTightness   over 187 queries — h(origin) as a fraction of true optimal cost:
                           mean 4.1%, min 0.5%, max 22.1%

4.1 %. Euristika mato dvidešimt penktąją dalį tos kainos, kurią turėtų apriboti. Blogiausiu atveju — 0.5 %.

Priežastis pamatuota atskirai:

TestHeuristicBlindToWaiting   over 186 journeys: mean elapsed time 99.7 min,
                              mean generalised cost 145.0 equivalent-min,
                              mean transfers 3.57
                              generalised cost exceeds elapsed time by 45%

Euristika yra geometrinė: atstumas iki tikslo, padalytas iš didžiausio stebėto greičio. Geometrija gali modeliuoti važiavimą. Ji negali modeliuoti laukimo kito reiso ir persėdimo bausmės — o tai yra 45 % kainos.

Kelionės kaina viešuoju transportu priklauso ne nuo to, KUR tu esi, o nuo to, KADA. Euristika mato tik „kur".

Ir rezultatas matomas mazgų skaičiuje:

TestAStarSpread
  short_hop            dijkstra settled  1974 | A* settled  1760 | reduction 10.8%
  cross_city           dijkstra settled 15154 | A* settled 12829 | reduction 15.3%
  late_night           dijkstra settled  9923 | A* settled  9923 | reduction  0.0%
  exhaustive_no_route  dijkstra settled   147 | A* settled   147 | reduction  0.0%

Dviem užklausoms iš keturių — lygiai nulis. O ten, kur nukerta 10–15 %, sutaupytas darbas nepadengia to, ko euristikos skaičiavimas kainuoja kiekviename mazge.

Kainos svoriai nėra išgalvoti

Verta sustoti: gal A* pralaimi todėl, kad kainos modelis dirbtinai sudėtingas — įpainiotas tik tam, kad geometrija atrodytų bejėgė?

Ne. Svoriai paimti iš transporto planavimo literatūros:

laukimo svoris 2.0 — Wardman apžvalgos pateikia laukimo ir važiavimo santykį 2:1; Metropolitan Transportation Commission (Travel Model One) ir San Francisco County TA (CHAMP 5.0) abu naudoja lygiai 2.0;
persėdimo bausmė 5 min — literatūra siūlo 5–15; MTC ima 5/10/30 minutes už pirmą, antrą ir trečią persėdimą, SFCTA — vienodai 6. Paimta žemutinė riba.

Ir modelis pamatuotas prieš gryną laiką:

TestGeneralisedCostPrefersFewerTransfers
  over 200 queries: 10 chose a later arrival, 149 used fewer transfers

149 maršrutai iš 200 gavo mažiau persėdimų, ir tik 10 atvyko vėliau. Tai modelio pataisa, ne gudrybė, kad krūva atrodytų reikalinga.

Ir vis dėlto keliuose A* laimi

Čia lengva padaryti neteisingą išvadą: „A* neveikia". Neteisinga.

Automobilių maršrutų paieškoje A* ir jo įpėdiniai — contraction hierarchies — yra standartas. Ten euristika veikia puikiai, nes kelionės automobiliu kaina tikrai yra beveik atstumas: nėra tvarkaraščio, nėra laukimo, greitis svyruoja siaurose ribose.

Viešojo transporto maršrutų paieška nuėjo kitu keliu — į CSA ir RAPTOR algoritmus, kurie euristikų neturi visai.

Tas pats trumpiausio kelio uždavinys. Priešingi laimėtojai.

Bast ir kt. („Route Planning in Transportation Networks", MSR-TR-2014-4) šitą skirtumą aptaria kaip pagrindinį; Geisberger, contraction hierarchies autorius, dokumentuoja, kad metodas „completely fails for timetable networks".

Algoritmą renkasi ne uždavinys, o uždavinio STRUKTŪRA.

Kodėl A* nėra tavo bibliotekoje

Pabandyk parašyti h(v) savo tinklui: kiek dienų liko nuo knygos v iki tikslo?

Negali. Knygos neturi koordinačių. Nėra nieko, ką būtų galima išmatuoti neatlikus pačios paieškos, o įvertis, kurį reikia apskaičiuoti paiešką atlikus, nėra įvertis.

A* reikalauja žinių apie uždavinį, kurių tavo grafas neturi. Todėl šioje pamokoje jo ir nestatai — ne dėl to, kad jis sunkus, o dėl to, kad jam nėra iš ko atsispirti.

Tai irgi atsakymas, ir sąžiningas.