Hlavní navigace

Názor ke článku Sliding puzzle - skládání kostiček od black3r - ja by som take dve drobnosti rad podotkol: -...

  • 19. 1. 2021 9:44

    black3r

    ja by som take dve drobnosti rad podotkol:

    - to co volas Dijkstrovym algoritmom nie je v skutocnosti Dijkstrov algoritmus, ale iba A* s inou (horsou) heuristikou. Dijkstrov algoritmus je zovseobecnenim BFS pre pripady, ze vzdialenosti medzi stavmi mozu byt vacsie ako 1. A* je generalizacia Dijkstrovho algoritmu s pouzitim heuristiky.

    - tvoje BFS je tak vyrazne pomale, lebo robis zakladnu chybu pri BFS: do visited_states vrchol pridavas az ked ho vyberies z fronty.., nie v momente ked ho pridavas do fronty, takze sa ti moze stat, ze vrchol mas vo fronte viackrat (ked donho existuje viacero ciest rovnakej dlzky, co v tomto grafe plati dost casto), navstivis ho teda viackrat, a z linearnej casovej zlozitosti (vrcholy maju max. stupen 4) mas zrazu exponencialnu...