Алгоритм прохождения по территории.

[Губин Игорь]

Не совсем сюда, но уж кидаю куда можно.

Задача стоит так: есть некая территория на которой стоят здания. Требуется определить кратчайший (ну или разумный) маршрут от одной точки до другой в обход зданий. Территория может быть задана графическим файлом (пустое белым, занятое жёлтым), схемой или любым другим удобным способом. Как захотим - так и будет. Требуется алгоритм.

Вроде можно использовать граф, но хочется услышать ответы тех, кто с этим сталкивался или точно знает как.

[Yufil]

Погугли "Задача коммивояжера"

[Губин Игорь]

Насколько я помню вузовский курс, там несколько иная задача (обход всех вершин).

[Yufil]

Ага, именно так. Речь именно о программном описании структуре графа и задачи обхода, чтобы велосипедов не изобретать.

[Губин Игорь]

тут нужен проход от одной вершины до другой. Но дело даже не в этом. Проблема в том, как правильно построить этот граф по схеме территории. И как потом это всё правильно показать. Идеи кое-какие есть.

[Yufil]

Я бы использовал для отображения Bennet-Tec Metadraw, там сочетание графического редактора с хранилищем метаданных.

[Губин Игорь]

Спасибо за совет. Но там посмотрим, пока надо решить текущую задачу.

[Алексей- Софт-Центр]

Добрый день!
Вроде алгоритмы описаны (Алгоритм Дейкстры):
1. http://ru.wikipedia.org/wiki/%C0%EB%E3% ... 1%F2%F0%FB
2. http://abviz.ru/?p=400

Вот этот пример - тоже похож на Вашу задачу
http://www.opita.net/node/681


Алексей

[Губин Игорь]

Спасибо. буду читать

[AlexK_60]

А волновой алгоритм не подойдёт? Прост в реализации и достаточно эффективен - активно применяется в программах трассировки печатных плат.
Вкратце: от исходной точки и от целевой точки распространяются радиальные волны (как от камня на воде), на каждом этапе - с единичным шагом. Итерация проводится до момента пересечения этих встречных волн. Результат - кратчайший путь.

[AlexK_60]

Писание волнового алгоритма - http://ru.wikipedia.org/wiki/%D0%92%D0% ... 1%82%D0%BC

[Губин Игорь]

Писание волнового алгоритма - http://ru.wikipedia.org/wiki/%D0%92%D0% ... 1%82%D0%BC

Спасибо, гляну