| Цитата(maxim1000 @ 31.10.2011, 22:25) | если расстояние до цели не очень большое, можно просто пустить волну
т.е. на k-м шаге находим, куда мы можем добраться за k шагов
если много мест недоступно, то и волна не будет много занимать
ну и, конечно же, нужно прекращать поиск после достижения целевой вершины, что также уменьшит количество время и используемую память |
волновой алгоритм может пройти S-образный путь ? Т.е. случай когда карта выглядит не так что она вся открыта и на нем отдельные препятствия которые можно обогнуть. А когда препятствия представляю большую часть карты при это оставляя пути для прохода в виде длинных изгибистых туннелей (аля лабиринт, это конечно сильное усложнения, но вполне обычно можно встретить изгибистые пути между двумя большими доступными плоскостями. Я до конца не постиг этот алгоритм,, поэтому ну знаю ответа на свой вопрос. Но везде пишется что алгоритм нее является эффективным.
Добавлено через 1 минуту и 7 секунд
| Цитата(tishaishii @ 31.10.2011, 19:47) | Тебе нужно оптимальное или удовлетворительное решение?
Когда количество вариантов и условий велико и в оптимальном алгоритме решения задействованы все эти условия и варианты, бывает выгоднее использовать не очень точный алгоритм, не учитывающий все случаи, но дающий удовлетворительное решение. |
хорошее замечание, но что понимать под оптимальным решением и как его узнать ?
Добавлено через 2 минуты и 50 секунд
| Цитата(tishaishii @ 31.10.2011, 20:09) | Я моделировал такую схему: станция тех-обслуживания и склад расположен на сети дорог, которая построена из ориентированных и неориентированных рёбер с разными весами-скоростными ограничениями. На той же сети расположены магазины, в которых происходят продажи товара с разной интенсивностью с экспоненциальным распределением вероятностной величины. Если в магазине заканчивается товар, то он закрывается. Грузовик на базе может заправиться и загрузиться товаром за такое-то время. При движении грузовика расходуется горючее, учитывая его загруженность. Грузовик движется по сети, выбирая оптимальный маршрут - такой, чтобы вывезти со склада побольше товара, побольше магазинов остались работать, и не оставить грузовик на трассе без топлива. Цель сего - для данной карты узнать максимальную зону покрытия организации, продающей товар.
Всё работало в разных потоках, на ООП. Корректировки весами и выбор целевой вершины, выбор следующей точки осуществлялся каждое мгновение, скелет - это две последовательно связанные вершины в сети, с кратчайшим путём между ними, от которых есть путь (кратчайший или нет - не считать) к целевой вершине. |
моя задачи сильно отличается. У тебя как раз хороший пример реальной задачи на графе. |
)