Výroba bludiště

Pospojujte všechny vrcholy hranou. Dostáváte jeden parametr:

Pro spojení dvou vrcholů použijte funkci spoj(a, b). Vzdálenost dvou vrcholů si můžete nechat spočítat funkcí vzdalenost(a, b).

Jako dárek dostáváte funkce Array.heappush(prvek, cmp) a Array.heappop(cmp). Jsou stejné jako minule, ale místo obyčejného porovnání < můžete zadat funkci cmp(a, b), která vrací, jestli a < b. Hodí se to, protože si o každém prvku v haldě budeme chtít pamatovat ještě nějaké poznámky.

Počet vrcholů:
Výroba bludiště

function pospojuj(vrcholy) {

}
Problém obchodního cestujícího

Dostáváme mapu měst pospojovaných cestami. Chceme je projít každé jenom jednou a ujít přitom co nejkratší vzdálenost. Napište funkci, která vrátí pole vrcholů v takovém pořadí, aby délka cesty byla co nejkratší.

délka:
function obchodni_cestujici(vrcholy) {

}

Backtracking (procházení do hloubky)

Nejjednodušší způsob, jak vyzkoušet všechna řešení, je použít rekurzi:

  1. Zavedeme si proměnnou na "zatím nejlepší řešení". Na začátku poslouží třeba vrcholy v původním pořadí.
  2. Postupně zkusíme začít v každém vrcholu, a spustíme z něj rekurzivní prohledávání:
    1. Pokud jsme prohledali už všechny vrcholy, spočítáme hodnocení cesty. Když je dobré, zapamatujeme si řešení.
    2. Jinak postupně zkusíme na konec cesty přidat všechny sousedy, kteří zatím v cestě nejsou, a s tak doplněnou cestou spustíme prohledávání.
  3. Až celý strom rekurze skončí, vypíšeme nejlepší nalezené řešení.

Branch and Bound (chytré procházení do hloubky)

Stejný program jako předchozí, ale vůbec nezkoušíme cesty, které jsou delší než zatím nejlepší řešení. Na začátku poběží stejně rychle, ale jakmile najde první hezké řešení, ušetří si spoustu práce.

Dijkstrův algoritmus (chytré procházení do šířky)

  1. Zavedeme si haldu cest, které stojí za to vyzkoušet. Vložíme do ní jednotlivě každý vrchol, jako možné začátky.
  2. Vytáhneme z haldy cestu s nejmenší délkou.
  3. Pokud cesta už obsahuje všechny vrcholy, je to nejlepší řešení a jsme hotovi.
  4. Podobně jako v předchozím případě prodloužíme cestu o všechny zatím nepoužité sousedy, a takhle upravené cesty přihodíme do haldy.
  5. Pokud halda není prázdná a nejkratší cesta v haldě je kratší než zatím nejlepší, vrátíme se na bod 2.

A* (Dijkstra s dolním odhadem)

Dolní odhad říká, že nejlepší řešení nemůže zaručeně být lepší než nějaká hodnota. V případě hledání cesty ze startu do cíle takhle dobře slouží vzdušná vzdálenost. Pro řešení problému obchodního cestujícího si

IDA* (Iterative Deepening A*, procházení do čím dál větší hloubky)

Počítače mívají o hodně víc výpočetního výkonu než paměti, a udržovat si řešení v haldě potom nejde. Použijeme proto radši prohledání do hloubky. Maximální délku cesty (tj. hloubku prohledávání) ale omezíme, aby se program hned na začátku neztratil v malichernostech. Když vyzkoušíme všechny cesty délky 1, postoupíme na cesty délky 2 atd. (V případě problému obchodního cestujícího to nemá smysl, protože řešení bude mít vždycky délku n). Každé rozpracované cestě počítáme ohodnocení a dolní odhad, což rovnou použijeme pro Branch and Bound; tím se ušetří ještě víc času. Pro drobné zlepšení ještě budeme na každém rozcestí zkoušet hrany od nejkratší po nejdelší.