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

XCodeR · Отправлено: **19:08, 13-09-2005** | #2

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

SergeCpp · Отправлено: **08:09, 14-09-2005** | #3

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

XCodeR · Отправлено: **18:53, 14-09-2005** | #4

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

Vlad Drakula · Конфигурация компьютера

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

XCodeR · Отправлено: **08:55, 17-09-2005** | #6

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

aESThete · Отправлено: **14:02, 17-09-2005** | #7

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

)

Цитата:

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

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

Цитата:

а делать большой массив 640х480 для поля 640px - 480px - имхо не рационально....

Достаточно по 2 бита на точку (4 состояния: пусто, преграда, волна четная, волна нечетная). Если жалко памяти

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

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

pva · Отправлено: **12:48, 03-10-2005** | #8

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