Алгоритм поиска пути

[GAGArin]

Сразу не пинайте только. И в гугле искал, и сам думал. Просто хочу кроме всего услышать мнение постояльцев. Задача почти стандартная есть массив локаций (где-то 5000), каждая связанна с 0-10 локациями. Половина переходов односторонние, про 70% локаций вообще нет информации. Что сделанно сейчас: просто разбегаюсь рекурсией с проверкой на пересечение только с текущей веткой. Если зашел в тупик/дошел до цели/дошел до предела пути (20 переходов или меньший из достигнутых) то затыкаемся. Потом выбираем лучший результат. Естественно в половине случаев получается ОЧЕНЬ медленно.

Варианты который буду делать - отсечения по достигнотому. т.е. на каждую локацию прошлое время достижения. И если какая-то из поздних веток приходит туда позже она "отмирает"

Хотел бы услышать может быть под эту задачу можно придумать что-то более шустрое. Есть идея пустить навстречу вторую волну (из точки достижения) но во-первых только половина переходов двусторонние (хотя можно пойти навстречу только по ним), а во -вторых (и это более существенно) как реализовать одновременность распространения волн? Пихать их в одну функцию? Но тогда на каждом шаге мы будем запускать до 100 новых веток, а это по-моему много.

[Хакер]

Используй "потенциал посещённости".

[Faust]

Насколько я знаю, обычно пускать две волны навстречу эффективней. А что касается односторонних проходов, то волной, идущей со старта, они проходятся только в "прямом" направлении, а волной, распространяющейся от финиша, только в "обратном". Ну и отсечение по достигнутому - святая вещь в волновом алгоритме, без неё никак.

[GAGArin]

Собственно вопросик был как именно реализовать две волны. Я вобщем и сам понимаю что будет гораздо быстрее. Пока как что мне пришло в голову, прикручивать к каждой вершине не только длинну пути для отсечений, а собственно весь "хвост" который был за ней, и в цикле запускать поиск из всех вершин которые могут его генерировать. Ну и ещё один байт на предмет: в какую сторону пускать пути и пускать ли вообще. Другого способа нет?

Используй "потенциал посещённости"

Насколько я понимаю это понятие "посещаемости" пути. Где короче путь там и натопчут. Но у меня очень редкие перемещения. Это раз, а во вторых насколько я знаю это скорее алгоритм обхода препятствий. Как его прикрутить к путешествию по графу не особо врубаюсь.

[Хакер]

Извеняюсь за тупость. Просто была ночь, болела бошка и мне было больше нечем заняться как отвлечь себя созданием думающего АИ. Думающий в смысле он решает как ему пройти куда-то. Например в большенстве игр сейчас используется рекурсивный поиск. Но ведь это не интеллект. Откуда скажем бот стоит в лабиринте. Я с хохотом наблюдаю как он, словно смотря через стены, с первого раза находит путь, причём кратчайший. Понятное дело что тут рекурсией составили PATH, по которому он и идёт. Но ведь вы когда находитесь в лаб. не знаете, что будет за поворотом - вы свернули, а там тупик - вы идёте назад, до развилки и теперь идёте уже в другой ход... и тд. Вот такой АИ я и сделал. Идея в следующем:
Всё пространство делится на блоки
У каждого блока есть такой показатель как потенциал посещаемости.
"Бот" идёт "от точки более высокого потенциала в точку с более низким". При каждом однократном посещении блока, его потенциал увеличивается. Это как-бы сказать "алгоритм поиска грибов в лесу" вы идёте смотреть только туда, где ещё не смотрели. Когда посмотрели всё идёте туда, где смотрели меньше всего..

Пойду наверное в треп выложу...

[Faust]

Заводишь массив по количеству локаций, в который заносишь ход, на котором она достигнута. К примеру, если какая-то локация достигается на 3 ходу из старта, то в соответствующую ячейку заносится "3", если на 5-м ходу из финиша, то "-5". Когда произойдет встреча фронтов двух волн, из точки встречи пробегаем по массиву назад, к старту и финишу, по уменьшению модуля чисел в соответствующих ячейках. Таким образом и определяется путь, хранить же его где-то в процессе распространения волн не приходится.
ЗЫ. Ну, это ты скорее всего и сам реализовал: активные вершины неплохо было бы запоминать, а не искать каждый ход. Структура данных получается сложнее, но она все равно работает быстрее перебора (просто я в своей первой реализации волнового алгоритма так не сделал и не понимал, откуда взялись такие тормоза...)

[GAGArin]

назад, к старту и финишу, по уменьшению модуля чисел в соответствующих ячейках

До этого я сам почему-то не дошел... Спасибо за советы. Пойду реализовывать.