*Теория* | Алгоритм(ы) движения(наикротчайшего пути) [Версия для КПК]

Показать полную графическую версию : *Теория* | Алгоритм(ы) движения(наикротчайшего пути)

XCodeR

11-09-2005, 10:07

Алгоритм стар как мир(IT)... скорее всего.
Есть 1 объект и одно поле.
на поле постоянно перемещающиеся преграды.
Объект должен перейти из одной точки в другую по наикротчайшему пути, обходя преграды и повозможности прогназирую, где они окажутся.

Как я знаю, решается это путем 2-мерной матрицы.

*******x
*
*
*
y

на которой отмечаются все материальные объекты поля.

Интересно есть ли бругие алгоритмы?... Желательно в реальных координатах(ну т.е. практическое применение не только по двигающемуся "0" в матрице).

уравнение прямой? и прасчет каждой последующей пары (X,Y), с проверкой на существование преграды?

XCodeR

13-09-2005, 19:08

:(
никто не знает?.....

SergeCpp

14-09-2005, 08:09

http://www.kamlit.ru/docs/aloritms/algolist.manual.ru/

XCodeR

14-09-2005, 18:53

SergeCpp
ок, пороюсь
но если все таки кто-то встречался с подобной "проблеммой" - поделитесь опытом

Vlad Drakula

15-09-2005, 23:24

Xcode
я занимался отлько алгоритмом с двух мерным массивом

XCodeR

17-09-2005, 08:55

Vlad Drakula
томеж волновым?...
дело в том, что хотелось бы узнать есть ли бругие алгоритмы, преспособленные для реальных координат?
конечно же, переделать волновой в реальные координаты несложно, но будет бооольшая погрешность.
а делать большой массив 640х480 для поля 640px - 480px - имхо не рационально....

aESThete

17-09-2005, 14:02

Xcode
Не знаю, насколько полезна информация в плане задачи для перемещающихся препятствий, но в бытность свою изучения САПР/ТАПР, наряду с волновыми учили т.н. лучевой алгоритм трассировки печатных плат. (Может название метода поможет?)
Если учебник или конспекты найду... (хотя 15 лет уже прошло :()

уравнение прямой? и прасчет каждой последующей пары (X,Y), с проверкой на существование преграды?
Наверное, да. А зачем пробегать(перебирать) всю прямую? Это у вас имхо и получится а-ля волновой.
Примерный алгоритм (к сожалению, без мат. аппарата):
1) Строим уравнение прямой (отрезка) от начального пункта (А) до конечного (В)
2) проверяем преграды(учитывая их размеры?) на предмет попадания на эту прямую.
3) Если преграда на прямой, разбиваем отрезок на 2 - до преграды (А-С), и после (С-В).
4) Пытаемся преграду обойти следующим способом: сдвигаем точку С в сторону по перпендикуляру к изначальному отрезку (А-В) на расстояние примерно равное размеру преграды. (пробуем оба варианта, и "вправо" и "влево").
5) Далее каждый отрезок обрабатываем отдельно. см. п. 1. (рекурсией, наверное удобно).

а делать большой массив 640х480 для поля 640px - 480px - имхо не рационально....
Достаточно по 2 бита на точку (4 состояния: пусто, преграда, волна четная, волна нечетная). Если жалко памяти ;), создаете битовое поле (массив будет в 4 раза меньше).
В свое время при реализации волнового алгоритма на БК0010 решили проблему недостатка памяти, храня как саму матрицу с преградами, так и волны в момент прохождения, в экранной памяти цветами точек.

Насчет прогнозирования преград - в руки ко мне попадал учебник по что-то типа "военной теории вероятности": поиск/преследование подвижных/неподвижных целей с помощью подвижных/неподвижных наблюдателей/преследователей, проходов в минных полях, уход от поиска и т.п.

pva

03-10-2005, 12:48

Можно подойти к вопросу чисто математически:
1. Тот, кто ставит преграды, пытается вам навредить.
Это называется антогонистической игрой (полный пессимизм).
Решается так: перебираете все стратегии соперника и ваши ответы и ставится им оценка.
Всё собирается в матрицу оценок, затем выбирается "седловая точка" задачи. (Вроде по вашим стратегиям минимум по сопернику максимум) Как точно не помню,
если нужно, посмотрю в конспекте. Если такая точка есть, вы - победитель (у вас есть оптимальная стратегия). Если нет (значит нет решения) - нужно решать другим методом.
2. Тот, кто ставит преграды, либо пофигист, либо пытается вас запутать (статистическая модель)
Это называется неантогонистической игрой. Каждому варианту соперника ставите вероятность,
оцениваете свои стратегии. Дальше - несколько вариантов.
2.1. критерий риска. Методом 1 решается задача минимизации риска проигрыша (используется на бирже)
2.2. критерий выигрыша. Небольшая вариация метода 1.
Любая задача имеет решение методом 2. Если нужно, я посмотрю, в какой книге это всё написано.
3. Смешанный способ - самый привлекательный. Задаётся коэффициент оптимизма и решается способом 2.