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...
pracuje na pozici IT architekta. Poslední roky se zaměřuje na integrační a komunikační projekty ve zdravotnictví. Mezi jeho koníčky patří také paragliding a jízda na horském kole.
Přečteno 19 099×
Přečteno 17 561×
Přečteno 15 380×
Přečteno 15 167×
Přečteno 14 660×