|
Алгоритм нахождения оптимального пути
|
|
| aSanN | Дата: Пятница, 28 Ноября 2008, 09:28 | Сообщение # 1 |
Поднаторевший
Группа: Проверенные
Сообщений: 91
Репутация: 2
Награды: 0
Статус: Offline
| Возникла потребность в написании программы, где используется такой алгоритм. Это будет игрушка. Те, кто играл в героев, дисайплс или варлордов, поймут, о чем я.
В общем, есть матрица [m,n], которая содержит только булевы значения (0 и 1). Всегда есть такой элемент Po{xo,yo}=0, координаты которого совпадают с координатами начальной точки пути. И при возникновении второй точки Pe{xe,ye}=0, координаты которой совпадают с концом пути, алгоритм должен найти ряд точек, по которым потом можно будет построит траектории оптимального пути материальной точки из Ро в Ре, с учетом того что элементы равные 0 - это пустое пространство, а отличные от 0 - это, допустим, стены или другие непроходимые участки. Знающих подобный алгоритм (необязательно кодом программы), прошу написать. Буду очень благодарен!
|
| |
| |
| toizy | Дата: Пятница, 28 Ноября 2008, 12:46 | Сообщение # 2 |
Студийная субстанция
Группа: Администраторы
Сообщений: 2309
Репутация: 29
Награды: 12
Статус: Offline
| "Я не начитанный - я нагугленный!"
Поиск в Яндексе по строке "Поиск кратчайшего маршрута delphi" ЗЫ. Юра! Не вставляется ссылка на страницу с поиском в яндексе... обрезает
Жизнь оказалась не такой уж и забавной, как поначалу...
|
| |
| |
| aSanN | Дата: Пятница, 28 Ноября 2008, 15:57 | Сообщение # 3 |
|
Поднаторевший
Группа: Проверенные
Сообщений: 91
Репутация: 2
Награды: 0
Статус: Offline
| Ничо не догоняю..
Где ошибка?
Матрица отображается не правильно..
|
| |
| |
| toizy | Дата: Пятница, 28 Ноября 2008, 17:38 | Сообщение # 4 |
|
Студийная субстанция
Группа: Администраторы
Сообщений: 2309
Репутация: 29
Награды: 12
Статус: Offline
| ой-йо! M[0.01] - это ты где такое взял? В ММВ нет многомерных массивов... Слава Богу, что хоть одномерные есть Добавлено (28 Ноябрь 2008, 17:38)
---------------------------------------------
Да и вообще... это нечто странное. Индекс должен быть целым числом. Исправляй 
Жизнь оказалась не такой уж и забавной, как поначалу...
|
| |
| |
| aSanN | Дата: Пятница, 28 Ноября 2008, 17:58 | Сообщение # 5 |
|
Поднаторевший
Группа: Проверенные
Сообщений: 91
Репутация: 2
Награды: 0
Статус: Offline
| да как-то я когда-то додумался создать 2мерный массив, определяя индексы, как целая и дробная часть..:)
но я уже исправил - записал индексы как числа меньше 100 и больше ста) все работает слава богу..
сейчас разбираю теорию графов..
эх...
|
| |
| |
| toizy | Дата: Пятница, 28 Ноября 2008, 18:05 | Сообщение # 6 |
|
Студийная субстанция
Группа: Администраторы
Сообщений: 2309
Репутация: 29
Награды: 12
Статус: Offline
| Давай-давай.. ученье - свет... хотя не вижу смысла меньше-больше ста делать.
Жизнь оказалась не такой уж и забавной, как поначалу...
|
| |
| |
| aSanN | Дата: Пятница, 28 Ноября 2008, 18:07 | Сообщение # 7 |
|
Поднаторевший
Группа: Проверенные
Сообщений: 91
Репутация: 2
Награды: 0
Статус: Offline
| Всмысле? а как тогда еще можно задать матрицу?? я только до этого додумался
|
| |
| |
| toizy | Дата: Пятница, 28 Ноября 2008, 18:16 | Сообщение # 8 |
|
Студийная субстанция
Группа: Администраторы
Сообщений: 2309
Репутация: 29
Награды: 12
Статус: Offline
| ну, к примеру, ты создаёшь массив диапазоном -49..50. Это всё равно что массив с диапазоном 1..100 Добавлено (28 Ноябрь 2008, 18:16)
---------------------------------------------
Как ни крути, одномерный
Жизнь оказалась не такой уж и забавной, как поначалу...
|
| |
| |
| aSanN | Дата: Пятница, 28 Ноября 2008, 18:23 | Сообщение # 9 |
|
Поднаторевший
Группа: Проверенные
Сообщений: 91
Репутация: 2
Награды: 0
Статус: Offline
| Ну теоретически получается одномерный, но практически то... Code X=5
Y=70
XY=X*100+Y
M[XY]=1 что-то типо того.. конечно не идеально, но матрицу задать можно..
|
| |
| |
| toizy | Дата: Пятница, 28 Ноября 2008, 18:28 | Сообщение # 10 |
|
Студийная субстанция
Группа: Администраторы
Сообщений: 2309
Репутация: 29
Награды: 12
Статус: Offline
| а, ну это если известно, что Y не будет больше ста. А так - молодец! Додумался Добавлено (28 Ноябрь 2008, 18:28)
---------------------------------------------
Щас в готовые ответы добавлю...
Жизнь оказалась не такой уж и забавной, как поначалу...
|
| |
| |
| aSanN | Дата: Пятница, 28 Ноября 2008, 18:33 | Сообщение # 11 |
|
Поднаторевший
Группа: Проверенные
Сообщений: 91
Репутация: 2
Награды: 0
Статус: Offline
| ну можно написать не сто, а 10000..) квантовые компьютеры еще не придуманы, чтобы работать с такими массивами)
|
| |
| |
| toizy | Дата: Пятница, 28 Ноября 2008, 18:36 | Сообщение # 12 |
|
Студийная субстанция
Группа: Администраторы
Сообщений: 2309
Репутация: 29
Награды: 12
Статус: Offline
| Да почему... вон уже по триста терабайт оперативки вколачивают купить для дому, что ли?..
Жизнь оказалась не такой уж и забавной, как поначалу...
|
| |
| |
| aSanN | Дата: Пятница, 28 Ноября 2008, 18:42 | Сообщение # 13 |
|
Поднаторевший
Группа: Проверенные
Сообщений: 91
Репутация: 2
Награды: 0
Статус: Offline
| неее... если у тебя 300Тб оперативы, то виндоус ХР держит только 4Гб, материнсакие платы держат максимум 16Гб (столько я видел)..
Темболее я сомневаюсь что кто-то додумается на комп с 300Тб поставить ММВ 
|
| |
| |
| toizy | Дата: Пятница, 28 Ноября 2008, 18:51 | Сообщение # 14 |
|
Студийная субстанция
Группа: Администраторы
Сообщений: 2309
Репутация: 29
Награды: 12
Статус: Offline
| Не, ну 32 битная не поддерживает. А вот 64...
Жизнь оказалась не такой уж и забавной, как поначалу...
|
| |
| |
Все права защищены
