Hledání nejkratší cesty s omezeními – technická case study
Hlavní náplň mé práce tvoří vývoj aplikace Registr telekomunikační sítě pro Telefóniku O2. Navzdory svému názvu aplikace neslouží pouze pro statickou evidenci hardwaru a síťových prvků, ale evidovaná data využívá pro potřeby procesů konstrukce sítě u zákazníka. V první polovině letošního roku jsem pracoval na zakázce, jejíž výstupem byl uživatelský formulář pro plánování tras optických kabelů. Z hlediska funkcionality se jednalo o grafovou úlohu. Byl to poměrně atypický problém, o to raději se chci podělit o popis řešení. Přijde mi totiž zajímavé především tím, že po stránce teoretické není úplně triviální (musel jsem oprášit skripta Teoretická informatika a jim podobné), ale současně si zachovává napojení na praxi a mohu tak na vlastní oči vidět jeho reálnou hodnotu pro uživatele (proto o něm bloguji až s časovým odstupem).
Je zřejmé, že dnes už nikdo aspoň trochu soudný nepíše vlastní algoritmus na řazení nebo binární půlení. Základní algoritmy se dostaly do standardní knihovny Javy i ostatních jazyků. Čím dále půjdeme od základních algoritmů ke specifickým, tím více se budou standardní knihovny vzdalovat, ale při troše štěstí lze pořád nalézt dobrou externí knihovnu a znovu neobjevovat kolo. Příkladem je např. JUNG pro grafové algoritmy, hashovací funkce a BloomFilter v Guavě nebo Levenshteinova vzdálenost v Apache commons-lang. Jsem však přesvědčen, že problém, o kterém budeme hovořit v tomto článku, má řešení za hranicemi běžného portfolia nabízeného světem opensource. Budu se snažit, aby čtenář neměl dojem, že "zas ten internet vyprodukoval bůhvíkolikátý tutoriál Dijkstrova algoritmu" (DA) a zaměřím se nikoli na DA, ale spíše na cestu od učebnicového DA k finálnímu řešení.
Zadání
(Ve skutečnosti zadání v takto ucelené podobě na začátku neexistovalo, jde spíš o souhrn všech znalostí o problému):Je dán neorientovaný graf, kde uzly představují body telekomunikační sítě a hrany dílčí úseky optických kabelů, které body sítě propojují.
- U každého úseku je evidována kladná délka v metrech.
- U většiny bodů sítě jsou evidovány GPS souřadnice budov, v nichž je umístěno zařízení.
- Úseky jsou uloženy v relační databázi jako řádky tabulky obsahující mj. id krajních bodů (z historických důvodů je tato tabulka snapshot ostrých dat aktualizovaný jobem 1x/24 hod).
- Graf nemusí být souvislý (např. v praxi je již mezi dvěma body optika, ale na zbytek optické sítě ještě není kabel napojen, spojení je např. metalické a z hlediska databáze optických kabelů je to nespojitost).
- Každý úsek patří k právě jednomu kabelu, kabel se skládá z mnoha úseků. (Kabel reprezentuje svazek optických vláken, jak je fyzicky položen mezi několika uzly sítě; výsledná cesta ale může jít přes úseky více kabelů, které jsou v uzlech spojeny provařením.)
- Kritériem je minimální délka v metrech; při shodě délek vítězí cesta s menším počtem hran.
- Jisté uzly, úseky nebo kabely mohou být vyloučeny z hledání (blacklist).
- Jisté uzly, úseky nebo kabely mohou být naopak požadovány v nalezené cestě (whitelist). Není tím ale určeno jejich pořadí. Počet omezení na požadované části je omezen na max. 4. Požadavky na vyloučení nebo zahrnutí vycházejí z konstruktérské praxe a jsou důsledkem snahy o využití volných kapacit.
Reprezentace grafu
Lze vytušit, že ať bude algoritmus jakýkoli, bude potřeba hodně dotazů na sousedící uzly či hrany a s SQL dotazem přímo do tabulky bychom asi po výkonové stránce uživatele moc neoslnili. Je tedy nutné pracovat s grafem v paměti. Naštěstí graf není tak rozsáhlý, aby se na slušném stroji do paměti nevešel – počet hran je cca 13000. Je zřejmé, že prostým načtením tabulky do seznamu POJO objektů bychom si oproti SQL dotazu taky moc nepomohli, navíc většina sloupců db tabulky vůbec není potřeba (případně je potřeba až nakonec a to řeší dodatečný hromadný dotaz).Graf je proto za účelem efektivního hledání předzpracován, základní strukturu tvoří guavácká Multimap<Node,Edge>. Samotné třídy Node, Edge mají rovněž velmi skromný tvar – obsahují pouze id uzlu, resp. id úseku, délku úseku a id kabelu. Serializovaná podoba má cca 7MB, struktura je cachována na úrovni aplikačního serveru a dle timestampu obnovována ze snapshot tabulky v databázi (ze zadání plyne, že tabulka se mění pouze jednou denně).
Uvedené řešení je jednoduché, kompaktní, má dobrou časovou složitost všech potřebných lookupů a v případě potřeby může být kdykoli upgradováno na in-memory nebo NoSQL databázi.
Nesouvislost grafu
Pokud mezi dvěma uzly neexistuje cesta z důvodu nesouvislosti grafu, klasický DA nedokáže zabránit projití celé komponenty souvislosti, v níž leží výchozí uzel. Abychom se těmto zbytečným výpočtům vyhnuli, provedeme během předzpracování grafu detekci souvislých komponent algoritmem "šíření vlny": vybere se náhodný uzel, přiřadí se mu číslo komponenty 1, pomocí fronty se prohledá graf na všechny uzly z něj dosažitelné a tyto uzly obdrží shodné číslo komponenty. Ze zbylých uzlů se vybere další náhodný uzel a vše se opakuje pro komponentu číslo 2. To se celé opakuje, dokud zbývají uzly s nepřiřazeným číslem komponenty.Při požadavku na nalezení nejkratší cesty lze ihned prohlásit, že uzly jsou nedosažitelné tehdy a jen tehdy, když se nerovnají odpovídající čísla komponent. Tato kontrola se použije i pro uzly na whitelistu.
Složené kritérium pro ohodnocení cesty
class Score implements Comparable<Score> {
private final int length;
private final int numberOfEdges;
...
public int compareTo(Score that) {
int result = ComparisonChain.start()
.compare(this.length,that.length)
.compare(this.numberOfEdges, that.numberOfEdges)
.result();
return result;
}
}
Tato třída se pak může použít všude tam, kde se v původním algoritmu pracuje s délkou. Vhodně zvolené názvy jako např. operace Score.plus(Score), statická factory metoda Score.fromLength(int), konstanta Score.ZERO a immutabilita zajišťují téměř neznatelný rozdíl oproti původní podobě algoritmu s ohodnocením typu číslo.GPS souřadnice – pomoc nebo past?
Zdánlivě jasná odpověď – když hledám nejkratší cestu z Písku do Brna, je zřejmé, že si vyberu spíš Tábor než Plzeň. Praktická úvaha nás ale vrací k teorii: GPS je typickým příkladem heuristiky snažící se omezit stavový prostor hledání, naproti tomu DA patří mezi neinformované metody hledání a žádnou heuristiku nepotřebuje. Vypadá to, že bude potřeba zrevidovat, zda vůbec úlohu řešit Dijkstrovým algoritmem (kdy bychom GPS nevyužili) nebo zda použít alternativní možnost – algoritmus A*, který se dá považovat za zobecnění DA.Díky kompaktní reprezentaci není problém s větším množstvím prohledávaných uzlů způsobeném absencí heuristiky palčivý. Nicméně jestliže tento argument pouze oslabuje důvod pro použití A*, následující zcela vyšachovává A* ze hry.
Jedním z podmínek nalezení optimálního řešení je totiž přípustnost heuristiky. Jak tento pojem pochopit selským rozumem? Představme si, že algoritmus je nevidomý cestovatel a heuristika jeho průvodkyně, která ho po cestě doprovází a je pro cestovatele jediným zdrojem informací. Představme si dva cestovatele na cestě z Prahy do Českých Budějovic, jeden si najme průvodkyni Hedviku, druhý průvodkyni Helenu. Hedvika je drzá, neustále balancuje na hranici, jak velkou lež může na cestovatele zkusit. Proto mu u Příbrami řekne, že už jsou v Písku, v Písku řekne, že už jsou před Českými Budějovicemi, a od Vodňan už jen opakuje netrpělivému cestovateli, že už tam každou chvíli budou. Ten je sice nervózní, ale po celou dobu žije v jakési iluzi lepšího a nic jiného mu v podstatě nezbývá. Naproti tomu Helena je hodná, snaživá a chce cestovatele v cíli "mile překvapit". Proto v Písku ohlásí teprve Příbram a těsně před Budějovicemi Písek. Cestovatel sice v lepším případě bude mile překvapen, v horším případě ho ale dlouhá cesta přestane bavit, takže v domnělém Písku nařídí změnit směr a v realitě skončí někde na Hluboké nebo na Temelíně.
Nevím, kterou z těchto průvodkyň byste si vybrali vy, ale algoritmus A* má určitě radši prolhanou Hedviku. Hedvika totiž představuje přípustnou heuristiku. Algoritmus je postaven tak, že s přehnaným optimismem si poradí, ale s pesimismem ne. Jak to souvisí se zadáním naší úlohy? GPS souřadnice jsou souřadnice budov, v nichž se někde uvnitř nacházejí konce jednotlivých kabelů. GPS je mnohem přesnější než rozloha půdorysu jednotlivých budov, pro evidenci se musí zvolit zástupný bod, obvykle souřadnice hlavního vchodu budovy, závory areálu apod. Může pak nastat situace, kdy dva areály mají hlavní vchody daleko od sebe, ale mnohem blíž jsou k sobě optické rozvaděče, na kterých končí kabel. Je tedy zřejmé, že v situaci, kdy vzdušná vzdálenost GPS souřadnic zástupných bodů je větší než reálná délka kabelového úseku, heuristická funkce založená na GPS "přehání" a není tudíž přípustná a tím použitelná pro naše potřeby.
Uvedená situace byla prokázána analýzou dat a stejně jako případ, kdy GPS souřadnice nejsou evidovány, vedla k zamítnutí algoritmu A* pro řešení úlohy.
Ověření bezespornosti omezení
Design by contract je samozřejmá praxe, která se v našem případě prakticky projeví především v kontrole omezení na požadované nebo vyloučené prvky grafu. Musí být splněny tyto podmínky:- výchozí ani cílový uzel nesmí být na blacklistu
- žádný prvek nesmí být současně na whitelistu i blacklistu
- úsek nesmí být na whitelistu a současně jeho kabel na blacklistu (pozn. obráceně je to však legitimní – můžeme chtít jít přes kabel, ale ne přes nějaký jeho konkrétní úsek)
- úsek nesmí být na whitelistu a současně nějaký jeho krajní bod na blacklistu
- cílový uzel i prvky na whitelistu musí být z výchozího uzlu dosažitelné
- na whitelistu nesmí být dva paralelní úseky (mající shodné krajní body), neboť dle definice cesty by nebylo možné se do krajního bodu vrátit
Detekce těchto situací je jednoduchá a rychlá – pár množinových operací. Provést ji před zahájením hledání považuji za lepší alternativu, než doplňovat kontroly do vyhledávacího algoritmu (které by odváděly pozornost od podstaty) nebo ji zcela vynechat (a získat výsledek, popř. informaci o neexistenci výsledku, po delší době a větším prozkoumaném prostoru).
Blacklist
Vyloučení bodů nebo úseků z hledání se uskutečňuje v místě, kde se zkoumají sousedé uzlu vyjmutého z fronty. Do pseudokódu DA z wikipedie by se přidaly řádky 8 u := extract_min(N)
9 for each neighbor v of u:
if blacklist.rejectsEdge(u,v) continue;
if blacklist.rejectsNode(v) continue;
10 alt = d[u] + l(u, v)
Whitelist
Nalezení nejkratší cesty s omezující podmínkou na požadované prvky je nejobtížnější částí celého úkolu. Obtížnost je způsobena faktem, že není určeno pořadí požadovaných prvků. Pokud na mapy.cz zadáte trasu Aš-Ostrava přes Brno a Prahu (v tomto pořadí!), zajistíte si pěknou trojnásobnou projížďku po D1, protože služba požadavek převede na posloupnost nejkratších cest mezi po sobě jdoucími body. V případě bodů sítě ale uživatel toto pořadí nezná a ani ho určovat nechce – nemá to vůbec smysl.Přímočaré řešení založené na prozkoumání všech kombinací je nereálné, nicméně pomůže k lepší představě o obtížnosti úlohy: Uvažujme nyní na chvíli jiný graf, který je úplný, jeho množinu uzlů tvoří pouze uzel A, B a uzly na whitelistu původního grafu a hrany jsou ohodnoceny délkou nejkratší cesty mezi uzly v původním grafu. Může se zdát, že potřebujeme nalézt nejkratší Hamiltonovu cestu mezi uzly A a B a její jednotlivé hrany pak zpátky "rozbalit" na nejkratší cesty v původním grafu. Proč je to nesmysl? Z mnoha důvodů: Především tento algoritmus je špatně – mohou existovat dvě dílčí nejkratší cesty sdílející tutéž hranu, převodem na náhradní graf se tato nežádoucí situace zamaskuje. Nicméně i kdyby se tento problém překonal, algoritmus bude pomalý (nejen kvadratický počet volání DA, ale především hledání Hamiltonovy cesty, což je známý NP-těžký problém). A nakonec: algoritmus uvažuje pouze uzly, podle zadání ale mohou být na whitelistu i úseky (to by šlo ještě vyřešit půlením a zařazením vzniklého pomocného uzlu na whitelist) nebo kabely (zde mne žádný jednoduchý způsob transformace nenapadá).
Poslední důvod naráží na fakt, že v zadání jsou omezení stanovena velmi volně. Mohou znít nejen "jdi přes uzel 123", ale i "jdi přes úsek 456" nebo dokonce "jdi přes nějaký úsek, který patří do kabelu 789". Je tedy přirozené, aby algoritmus pracoval nikoli s kombinacemi projitých uzlů, ale s kombinacemi již splněných omezení. Kombinace jsou vyjádřeny jako prvky potenční množiny. Zahájení algoritmu hledání je spjato s prázdnou množinou splněných omezení, dosažení cíle s množinou všech splněných omezení.
Zbývá vyřešit problém nalezení cesty a k tomu mne inspirovalo řešení problému obchodního cestujícího pomocí dynamického programování. Řešení sice neodstraňuje exponenciální složitost, ale snižuje její řád a jak to u dynamického programování bývá, kompenzuje čas pamětí. Funguje na principu funkce g(u,set), která udává, jaká je nejkratší Hamiltonova cesta mezi počátečním uzlem a uzlem u, která jde přes uzly množiny set. Se zvětšující se množinou set se dosahuje znovupoužití dřívějších hodnot funkce. Poměrně srozumitelný příklad (vejde se na jedinou stránku a není v něm ani jedno řecké písmenko) je uveden zde (PDF). V našem algoritmu bude množinou set nikoli množina prošlých uzlů, ale množina splněných omezení. Při maximálně 4 splněných omezeních (viz zadání) je horní odhad počtu stavů 24=16.
Algoritmus
Výsledný algoritmus je tedy Dijkstrův algoritmus upravený v následujících rysech:| klasický DA | modifikovaný algoritmus | |
| prvek prioritní fronty | uzel grafu | dvojice (uzel,množina_splněných_omezení), která představuje nejlepší dosaženou cestu z výchozího uzlu do uzlu uzel, která splňuje příslušná omezení. |
|---|---|---|
| rekonstrukce nalezené cesty | pro každý uzel se eviduje pouze předcházející uzel resp. vstupující hrana | eviduje se uspořádaná množina všech uzlů na dosud nalezené cestě (tuto informaci potřebuje pro kontrolu, že se cesta prodlužuje o nový uzel) |
| inicializace | vložení počátečního uzlu do fronty | vložení dvojice (počáteční uzel,prázdná množina omezení) do fronty |
| dosažení cíle | vyjmutí cílového uzlu z fronty | vyjmutí dvojice (cílový uzel,množina všech omezení) z fronty |
| tvorba prvků fronty | ze sousedů právě vyjmutého uzlu | ze sousedů uzlu z právě vyjmuté dvojice; k původní množině splněných omezení se přidají ta omezení, která se splní průchodem příslušnou hranou resp. dosažením příslušného souseda |
| zacházení s prvkem fronty | relaxace hrany může zlepšit dosavadní nejlepší cestu do uzlu, není-li již uzavřen | kontrola, že cesta se prodlužuje o nový uzel, jinak totéž jako u DA |
| kritérium řazení prvků prioritní fronty | podle délky dosud známé nejlepší nejkratší cesty | podle skóre (délka, pak počet hran), při shodném skóre navíc sestupně podle počtu splněných omezení (pouze heuristika bez vlivu na správnost) |
Pseudokód
List modifiedDijkstra(A, B, blacklist, whitelist) {
queue = new Queue;
queue.offer(A, {}, // vlozi do fronty dvojici (A,{})
Score.ZERO, null, {}); // u dvojice se eviduje skore, predchudce a cesta
while (!queue.isEmpty()) {
min,constraints = queue.poll();
queue.close(min, constraints);
if (min == B && constraints == whitelist.allConstraints) break; // jsme v cili
for (neighbor,edge : min.neighbors) { // soused a hrana, ktera k nemu vede
if (blacklist.rejectsEdge(edge)) continue;
if (blacklist.rejectsNode(neighbor)) continue;
if (min.getPath().contains(neighbor)) continue;
neighborConstraints = constraints ∪ whitelist.getConstraints(neighbor,edge);
if (queue.isClosed(neighbor,neighborConstraints)) continue;
Score score = min.getScore() + edge.getLength();
if (queue.isNew(neighbor,neighborConstraints) || score < neighbor.getScore()) {
queue.offer(neighbor, neighborSet, score, min, min.getPath() ∪ min);
}
}
}
path = new List; // rekonstrukce stejná jako u DA
for (node = B; node != null; node = node.getPredecessor()) {
path.insertAtBeginning(node);
}
return path;
}
Ve skutečném kódu je několik rozdílů na úrovni implementace, které jsou způsobeny použitím objektového paradigmatu. Samostatné třídy, které jsou immutable a mají přesně vymezenou zodpovědnost, existují pro samotný uzel grafu (Node), dvojici (uzel,omezení) (ConstrainedNode) a stav dvojice ve frontě (TrackedNode). Díky tomu je např. skóre nebo předchůdce uzlu vlastností objektu TrackedNode, což je v pseudokódu trochu zamaskováno. Podobně i obohacení množiny omezení je implementováno pomocí bitových operací a guavácké Sets.powerSet. Prioritní frontu bylo výhodné implementovat pomocí TreeSet, ve které uzavřené uzly stále zůstávají, ale jsou posunuty na konec. Značná část logiky mohla být díky tomuto přístupu přesunuta do pomocných tříd.
Příklad
Činnost algoritmu si ukážeme na následujícím grafu, kde úkolem je najít nejkratší cestu mezi body A a B, která musí jít přes uzel F a hranu DE:
Zápis prvku má tvar $<délka>,<počet_hran> <path>, kde <délka> a <počet_hran> představují dosažené skóre a <path> je uspořádaná množina uzlů tvořících cestu z uzlu A do příslušného uzlu (nevčetně). Pro názornost je modře zvýrazněn nejmenší prvek, který bude v příští iteraci vybrán z fronty, tučně zvýrazněny prvky, které od minulé iterace nově vznikly resp. byly aktualizovány relaxací hrany, a naopak šedě ztlumeny prvky, které už jsou uzavřené.
ITERACE 1:
+---+-------+
| | {} |
+---+-------+
| A | $0,0 | inicializace s výchozím uzlem
+---+-------+
ITERACE 2:
+---+--------+--------+
| | {} | {F} |
+---+--------+--------+
| A | $0,0 | | výchozí uzel uzavřen
| F | | $1,1 A | uzel F je dosažen a už je tím splněno jedno omezení
| C | $5,1 A | |
| D | $6,1 A | |
+---+--------+--------+
ITERACE 3:
+---+--------+----------+
| | {} | {F} |
+---+--------+----------+
| A | $0,0 | |
| F | | $1,1 A |
| C | $5,1 A | $5,2 A,F | dosažitelnost C přímo z A a nepřímo přes F jsou dvě různé věci
| D | $6,1 A | |
| E | | $6,2 A,F | nový uzel dosažitelný přes F
| B | | $2,2 A,F | nový uzel dosažitelný přes F
+---+--------+----------+
ITERACE 4:
+---+--------+-------------+
| | {} | {F} |
+---+--------+-------------+
| A | $0,0 | |
| F | | $1,1 A |
| C | $5,1 A | $5,2 A,F |
| D | $6,1 A | $11,3 A,F,B | D nově dosažen pro omezení {F}
| E | | $6,2 A,F | toto dosažení se nezlepšilo, přes A,F,B by mělo skóre $7,3
| B | | $2,2 A,F |
+---+--------+-------------+
ITERACE 5:
+---+-----------+-------------+
| | {} | {F} |
+---+-----------+-------------+
| A | $0,0 | |
| F | | $1,1 A |
| C | $5,1 A | $5,2 A,F |
| D | $6,1 A | $11,3 A,F,B |
| E | $11,2 A,C | $6,2 A,F | E nově dosažen také bez splněných omezení
| B | | $2,2 A,F |
+---+-----------+-------------+
ITERACE 6:
+---+-----------+------------+
| | {} | {F} |
+---+-----------+------------+
| A | $0,0 | |
| F | | $1,1 A |
| C | $5,1 A | $5,2 A,F |
| D | $6,1 A | $7,3 A,F,C | relaxace hrany CD - hrana zlepšila cestu do D pro omezení {F}
| E | $11,2 A,C | $6,2 A,F |
| B | | $2,2 A,F |
+---+-----------+------------+
ITERACE 7:
+---+-----------+------------+-----------+
| | {} | {F} | {DE} |
+---+-----------+------------+-----------+
| A | $0,0 | | |
| F | | $1,1 A | |
| C | $5,1 A | $5,2 A,F | |
| D | $6,1 A | $7,3 A,F,C | |
| E | $11,2 A,C | $6,2 A,F | $10,2 A,D | E nově dosažen pouze přes hranu DE
| B | $15,2 A,D | $2,2 A,F | |
+---+-----------+------------+-----------+
ITERACE 8:
+---+-----------+------------+-----------+-------------+
| | {} | {F} | {DE} | {F,DE} |
+---+-----------+------------+-----------+-------------+
| A | $0,0 | | | |
| F | | $1,1 A | | |
| C | $5,1 A | $5,2 A,F | | |
| D | $6,1 A | $7,3 A,F,C | | $10,3 A,F,E | D dosažen z E již se všemi omezeními
| E | $11,2 A,C | $6,2 A,F | $10,2 A,D | |
| B | $15,2 A,D | $2,2 A,F | | |
+---+-----------+------------+-----------+-------------+
Situace všech "načatých" cest nyní vypadá podle následujícího obrázku. Poprvé bylo dosaženo splnění všech omezení (fialová cesta), ale na nalezení nejkratší cesty si budeme muset ještě počkat.
ITERACE 9:
+---+-----------+------------+-----------+---------------+
| | {} | {F} | {DE} | {F,DE} |
+---+-----------+------------+-----------+---------------+
| A | $0,0 | | | |
| F | | $1,1 A | | |
| C | $5,1 A | $5,2 A,F | | |
| D | $6,1 A | $7,3 A,F,C | | $10,3 A,F,E |
| E | $11,2 A,C | $6,2 A,F | $10,2 A,D | $11,4 A,F,C,D | další dosažení všech omezení
| B | $15,2 A,D | $2,2 A,F | | |
+---+-----------+------------+-----------+---------------+
ITERACE 10:
+---+-----------+------------+-------------+---------------+
| | {} | {F} | {DE} | {F,DE} |
+---+-----------+------------+-------------+---------------+
| A | $0,0 | | | |
| F | | $1,1 A | | $15,3 A,D,E | další dosažení všech omezení
| C | $5,1 A | $5,2 A,F | $16,3 A,D,E | | nově dosažen C pouze přes DE
| D | $6,1 A | $7,3 A,F,C | | $10,3 A,F,E |
| E | $11,2 A,C | $6,2 A,F | $10,2 A,D | $11,4 A,F,C,D |
| B | $15,2 A,D | $2,2 A,F | $15,3 A,D,E | | cíl dosažen, ale bohužel bez [F]
+---+-----------+------------+-------------+---------------+
ITERACE 11:
+---+-----------+------------+-------------+---------------+
| | {} | {F} | {DE} | {F,DE} |
+---+-----------+------------+-------------+---------------+
| A | $0,0 | | | |
| F | | $1,1 A | | $15,3 A,D,E |
| C | $5,1 A | $5,2 A,F | $16,3 A,D,E | $12,4 A,F,E,D |
| D | $6,1 A | $7,3 A,F,C | | $10,3 A,F,E |
| E | $11,2 A,C | $6,2 A,F | $10,2 A,D | $11,4 A,F,C,D |
| B | $15,2 A,D | $2,2 A,F | $15,3 A,D,E | $19,4 A,F,E,D | nález prvního řešení
+---+-----------+------------+-------------+---------------+
Po 11. iteraci byl konečně dosažen cílový uzel za současného splnění všech omezení. Máme tedy první řešení délky 19,
ale zatím nemáme jistotu, že nalezená cesta je nejkratší. Musíme ještě dokončit dílčí načaté cesty, které jsou zatím kratší než nalezená cesta.
ITERACE 12:
+---+-----------+------------+-------------+---------------+
| | {} | {F} | {DE} | {F,DE} |
+---+-----------+------------+-------------+---------------+
| A | $0,0 | | | |
| F | | $1,1 A | | $15,3 A,D,E |
| C | $5,1 A | $5,2 A,F | $16,3 A,D,E | $12,4 A,F,E,D |
| D | $6,1 A | $7,3 A,F,C | $15,3 A,C,E | $10,3 A,F,E |
| E | $11,2 A,C | $6,2 A,F | $10,2 A,D | $11,4 A,F,C,D |
| B | $15,2 A,D | $2,2 A,F | $15,3 A,D,E | $19,4 A,F,E,D |
+---+-----------+------------+-------------+---------------+
ITERACE 13:
+---+-----------+------------+-------------+-----------------+
| | {} | {F} | {DE} | {F,DE} |
+---+-----------+------------+-------------+-----------------+
| A | $0,0 | | | |
| F | | $1,1 A | | $15,3 A,D,E |
| C | $5,1 A | $5,2 A,F | $16,3 A,D,E | $12,4 A,F,E,D |
| D | $6,1 A | $7,3 A,F,C | $15,3 A,C,E | $10,3 A,F,E |
| E | $11,2 A,C | $6,2 A,F | $10,2 A,D | $11,4 A,F,C,D |
| B | $15,2 A,D | $2,2 A,F | $15,3 A,D,E | $16,5 A,F,C,D,E | zlepšení řešení přes hranu EB
+---+-----------+------------+-------------+-----------------+
Další zlepšení vypadá takto:
ITERACE 14: nezajímavá - A,F,E,D,C je slepá cesta, žádné zlepšení ani nový nález se nekoná
+---+-----------+------------+-------------+-----------------+
| | {} | {F} | {DE} | {F,DE} |
+---+-----------+------------+-------------+-----------------+
| A | $0,0 | | | |
| F | | $1,1 A | | $15,3 A,D,E |
| C | $5,1 A | $5,2 A,F | $16,3 A,D,E | $12,4 A,F,E,D |
| D | $6,1 A | $7,3 A,F,C | $15,3 A,C,E | $10,3 A,F,E |
| E | $11,2 A,C | $6,2 A,F | $10,2 A,D | $11,4 A,F,C,D |
| B | $15,2 A,D | $2,2 A,F | $15,3 A,D,E | $16,5 A,F,C,D,E |
+---+-----------+------------+-------------+-----------------+
ITERACE 15: nezajímavá - A,D,B je zkratka obcházející omezení, navíc drahá
+---+-----------+------------+-------------+-----------------+
| | {} | {F} | {DE} | {F,DE} |
+---+-----------+------------+-------------+-----------------+
| A | $0,0 | | | |
| F | | $1,1 A | | $15,3 A,D,E | minimální prvek fronty díky více splněným omezením
| C | $5,1 A | $5,2 A,F | $16,3 A,D,E | $12,4 A,F,E,D |
| D | $6,1 A | $7,3 A,F,C | $15,3 A,C,E | $10,3 A,F,E |
| E | $11,2 A,C | $6,2 A,F | $10,2 A,D | $11,4 A,F,C,D |
| B | $15,2 A,D | $2,2 A,F | $15,3 A,D,E | $16,5 A,F,C,D,E |
+---+-----------+------------+-------------+-----------------+
ITERACE 16:
+---+-----------+------------+-------------+---------------+
| | {} | {F} | {DE} | {F,DE} |
+---+-----------+------------+-------------+---------------+
| A | $0,0 | | | |
| F | | $1,1 A | | $15,3 A,D,E |
| C | $5,1 A | $5,2 A,F | $16,3 A,D,E | $12,4 A,F,E,D |
| D | $6,1 A | $7,3 A,F,C | $15,3 A,C,E | $10,3 A,F,E | minimální prvek fronty libovolný z D{DE} a B{DE}
| E | $11,2 A,C | $6,2 A,F | $10,2 A,D | $11,4 A,F,C,D |
| B | $15,2 A,D | $2,2 A,F | $15,3 A,D,E | $16,4 A,D,E,F | zlepšení řešení
+---+-----------+------------+-------------+---------------+
Další zlepšení, tentokrát se sice nesnižuje délka, ale počet hran cesty:
ITERACE 17:
+---+-----------+------------+-------------+---------------+
| | {} | {F} | {DE} | {F,DE} |
+---+-----------+------------+-------------+---------------+
| A | $0,0 | | | |
| F | | $1,1 A | | $15,3 A,D,E |
| C | $5,1 A | $5,2 A,F | $16,3 A,D,E | $12,4 A,F,E,D |
| D | $6,1 A | $7,3 A,F,C | $15,3 A,C,E | $10,3 A,F,E |
| E | $11,2 A,C | $6,2 A,F | $10,2 A,D | $11,4 A,F,C,D |
| B | $15,2 A,D | $2,2 A,F | $15,3 A,D,E | $16,4 A,D,E,F |
+---+-----------+------------+-------------+---------------+
ITERACE 18:
+---+-----------+------------+-------------+---------------+
| | {} | {F} | {DE} | {F,DE} |
+---+-----------+------------+-------------+---------------+
| A | $0,0 | | | |
| F | | $1,1 A | | $15,3 A,D,E |
| C | $5,1 A | $5,2 A,F | $16,3 A,D,E | $12,4 A,F,E,D |
| D | $6,1 A | $7,3 A,F,C | $15,3 A,C,E | $10,3 A,F,E |
| E | $11,2 A,C | $6,2 A,F | $10,2 A,D | $11,4 A,F,C,D |
| B | $15,2 A,D | $2,2 A,F | $15,3 A,D,E | $16,4 A,D,E,F |
+---+-----------+------------+-------------+---------------+
ITERACE 19:
+---+-----------+------------+-------------+---------------+
| | {} | {F} | {DE} | {F,DE} |
+---+-----------+------------+-------------+---------------+
| A | $0,0 | | | |
| F | | $1,1 A | | $15,3 A,D,E |
| C | $5,1 A | $5,2 A,F | $16,3 A,D,E | $12,4 A,F,E,D |
| D | $6,1 A | $7,3 A,F,C | $15,3 A,C,E | $10,3 A,F,E |
| E | $11,2 A,C | $6,2 A,F | $10,2 A,D | $11,4 A,F,C,D |
| B | $15,2 A,D | $2,2 A,F | $15,3 A,D,E | $16,4 A,D,E,F |
+---+-----------+------------+-------------+---------------+
takže po vybrání B{F,DE} z fronty je již garantováno, že řešení je optimální.
Závěr
Popisovaný problém byl řešen se současným důrazem jak na efektivitu, tak na srozumitelnost při maintainování kódu a z toho plynoucí zastupitelnost v konkrétních podmínkách zákazníka. I když nebylo možné se vyhnout tomu, aby se někde projevila exponenciální složitost, popisovaná praktická opatření předcházejí všem negativním mimořádným situacím a řešení se za cca 9 měsíců provozu osvědčilo.V reálné aplikaci jsou uzly tvořeny hierarchií různých typů uzlu a složitější je i způsob aktualizace grafu přes db job, ale tyto fenomény nemají vliv na hlavní algoritmus.
Hluboce smekam.
OdpovědětVymazathmm, to je prostě symfonie, pokud to tak mohu nazvat.
OdpovědětVymazatDobře ty :-)
OdpovědětVymazatA* byl vyřazen poměrně zbrkle. Ten problém popsaný ohledně přípustnosti heuristiky se dá vyřešit prostě tím, že se od heuristiky odečte nějaká konstanta (např. velikost největšího areálu). Výsledek bude násobně rychlejší než ten modifikovaný Dijkstra.
OdpovědětVymazat@michalillich Díky za reakci. Taky jsem myslel, že to nějak obejdu, ale zavrhl jsem to i kvůli jednodušší správě kódu. Modifikovaný A* by byl rychlejší, ale taky komplikovanější než modifikovaný DA. Nechtěl jsem, aby např. já nebo někdo jiný přišel za rok k chybě a musel zjišťovat, zda se od té doby zvětšila velikost největšího areálu a upravovat nějakou Pišvejcovu konstantu. Kromě toho data jsou někdy špatně o tolik, že by konstanta byla nesmyslně velká, někde data chybí. Navíc bych se nezbavil nutnosti řešit whitespace. Každopádně díky za velmi konstruktivní podnět. Určitě nevylučuji, že pokud se data někdy nafouknou tak, že DA nepostačí, bude nutné udělat A*, který přes všechny nedokonalosti dat GPS nějak probruslí k optimálnímu řešení.
OdpovědětVymazat