Grafové algoritmy
Grafové algoritmy pracují se strukturami zvanými grafy – disjunktními množinami tzv. uzlů a hran, kterými jsou dvojice uzlů spojeny. Nejčastěji řešenými úlohami je vyhledávání „nejkratší“ cesty v grafu, kde „vzdálenost“ nemusí mít nutně geometrický význam. Tyto algoritmy se používají i při řešení úloh umělé inteligence.
Prohledávání grafu
Účelem algoritmů pro prohledávání grafu je najít cestu ze zadaných počátečních uzlů do uzlů cílových. Protože lze grafem reprezentovat mnoho problémů, jsou tyto algoritmy velmi užitečné i pro řešení úloh z reálného světa. Prohledáváním grafu lze například strategie v různých hrách.
Neinformované algoritmy
Neinformované algoritmy při procházení grafu nevyužívají žádných znalostí o problému, které by mohly urychlit cestu k cíli. Nezbývá tedy nic jiného, než graf systematicky procházet. Tyto algoritmy jsou jednoduché na implementaci, ale velmi neefektivní. Lze je však použít i tam, kde o problému není nic známo.
Informované algoritmy
Informované algoritmy jsou založeny na neinformovaných algoritmech, ale při procházení grafu navíc využívají nějaké znalosti problému. Tato znalost je ukrytá v heuristické funkcí, která kvantitavitně vyjadřuje cenu, délku či obecně náročnost dané cesty a její výše ovlivňuje průchod algoritmu. Čím kvalitnější heuristická funkce je k dispozici, tím efektivněji najde grafový algoritmus řešení. Jednotlivé algoritmy po odebrání heuristické funkce zdegenerují buď na prohledávání do šířky, nebo do hloubky.
- algoritmus Hill-Climbing
- algoritmus A-Star
Stochastické algoritmy
Zcela bokem stojí speciální rodina algoritmů, které jsou většinou inspirovány nějakými přírodními a tedy nedeterministickými procesy. Mají využití především v umělé inteligenci a při řešení složitých (hlavně NP-úplných) či neznámých problémů.
Hledání nejkratší cesty
- algoritmus Floyd-Warshall
- algoritmus Dijkstra
Hledání minimální kostry
- algoritmus Borůvka-Kruskal
- algoritmus Jarník-Prim
Výpočet chromatického čísla
- algoritmus Welsh-Powell