Vlákno názorů ke článku Sliding puzzle - skládání kostiček od ebik - Hodnotící funkce pro dijkstru je špatně. Správná hodnotící...

Hodnotící funkce pro dijkstru je špatně. Správná hodnotící funkce pro dijkstru je rovná ceně stavu - tedy minimálnímu počtu tahů od počátečního stavu. V tomto jednoduchém případě, kdy cena přechodu do dalšího stavu je rovná jedné, je dijkstra prakticky totožný s DFS.

To co uvádíte není dijkstra, dokonce to může dávat "horší" výsledek než dijkstra, protože hodnotí nízkým score stav: (0<-5<-6), tedy:
5 1 2
3 4 6
0 7 8
Ten ale rozhodně není blízko cílovému stavu.

V podstatě dijkstra je "vážený" DFS, kde "hloubka" není rovná počtu přechodů ale ceně stavu, tedy nejkratší cestě do daného stavu. To je zajímavé pokud různé tahy mají různou cenu (například kdyby horizontální přesun stál 1 a vertikální přesun stál 100 - potom by se snažil najít cestu s minimálním počtem vertikálních přesunů a teprve mezi řešeními se stejným počtem vertikálních přesunů by hledal to s nejmenším počtem horizontálních).