|
я взял реализацию на двумерных массивах, поскольку нужно было высчитывать дорогу до многих мест одновременно располагающихся динамично...
|
приведи пример когда это нужно?
|
на списках как я думаю было бы намного дольше.
|
не знаю что такое "на списках", думаю ты имел в виду поиск в глубину, только рекурсия заменена на стек посещенных клеток, так?
у тебя сложность алгоритма O(N^2), т.е. в примере когда ты считаешь для N=400 (20x20 клеток) это уже долговато получается, если брать "боевые" условия, например походовую стратегию с размером карты 512х512 (N=262144) в несколько проходов - это абзац.
Оптимизации:
двухсторонний поиск - т.е. ищем поочередно с точки отправления и точки назначения
иерархический поиск - бьем карту на взаимно недостижимые части (типа районы города или области страны) и находим глобальный путь на большой карте, и пути к "выходам" на "мальеньких".
ЗЫ: "заступы и вилы";-)