Poznamenejte si do každého uzlu vzdálenost do cíle (získanou Dijkstrovým algoritmem).
Použijte vypočítané vzdálenosti do cíle jako heuristiku. Je tato heuristika přípustná? Je monotónní?
Je řešení získané hladovým prohledáváním s touto heuristikou optimální? Musíme znovu spustit Dijkstrův algoritmus pro přepočítání heuristiky, pokud dostaneme jinou dvojici uzlů?
Zvolte jako heuristiku h=11-log2(n), kde n je největší číslo v mřížce
Je tato heuristika přípustná? Je monotónní?
Najde hladové prohledávání s touto heuristikou řešení dříve než DFS?
Úloha 5: CNC vrtačka III.
Přidávejte uzly do řešení postupně. Nechť m1 je suma ohodnocení hran minimální kostry dosud nepřidaných uzlů (můžete použít např. Jarníkův algoritmus). Nechť m2 je minimální délka hrany z dosud nepřidaných uzlů do již přidaných uzlů. Nechť m3 je minimální délka hrany z dosud nepřidaných uzlů do prvního přidaného uzlu. Pak h=m1+m2+m3.
Je tato heuristika přípustná? Je monotónní?
Najde hladové prohledávání s touto heuristikou řešení (Hamiltonovskou kružnici) s menším ohodnocením než řešení od DFS?