 Поиск кратчайшего пути |
Прочтите прежде чем задавать вопрос!
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
  |
| AlexPS |
 20.07.2005 16:13
Сообщение
#1
|
 Новичок  Группа: Пользователи Сообщений: 34 Пол: Мужской Репутация:  -1   |
Вот такая у меня задача:
Задана матрица натуральных чисел А[1..n,1..m]. За каждый проход через клетку (i,j) взфмается штраф A[i,j]. Необходимо минимизировать штраф и пройти из какой-либо клетки (i1,j1) в (i1,j1). В FAQ я почитал про алгоритм дейкстры... А как бы мне перенести его на мою задачу? Сложность в том, что начальной и конечной точкой пути может быть абсолютно любая клетка матрицы..  -------------------- @13][ P.$.
www.alex-ps.com |
   |
 
|
| mlc |
20.07.2005 16:28
Сообщение
#2
|
|
Гость |
Можно и волновым методом, только не 1-цу прибавлять а вес ячейки.
|
|
|
|
| AlexPS |
20.07.2005 16:32
Сообщение
#3
|
|
Новичок Группа: Пользователи Сообщений: 34 Пол: Мужской Репутация: -1 |
А можно поподробнее, что это за алгоритм... или где-нибудь пример можно посмотреть?
-------------------- @13][ P.$.
www.alex-ps.com |
|
|
|
| volvo |
20.07.2005 17:14
Сообщение
#4
|
|
Гость |
http://algolist.manual.ru/games/wavealg.php
или google.com |
|
|
|
| Archon |
25.07.2005 21:35
Сообщение
#5
|
 Профи Группа: Пользователи Сообщений: 618 Пол: Мужской Репутация: 24 |
Алгоритм дейкстры, волновой метод... Зачем? Тут банальный перебор с некоторыми ограничениями. Следует использовать тот факт, что проходить через клетку повотрно - бессмысленно, так как в таком случае штраф явно будет НЕ минимальным. Попробуй рекурсию.
-------------------- Close the World...txeN eht nepO
|
|
|
|
| Malice |
25.07.2005 22:07
Сообщение
#6
|
 Профи Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: 20 |
Цитата(Archon @ 25.07.05 21:35) Алгоритм дейкстры, волновой метод... Зачем? ... Попробуй рекурсию. Мне кажется, что волновым простенько получится.. А на счет повторного прохода ты как раз и не прав, более дешевый путь не обязательно самый короткий (могу пример привести, если что  ). |
|
|
|
| virt |
26.07.2005 7:40
Сообщение
#7
|
 Знаток Группа: Пользователи Сообщений: 419 Пол: Мужской Репутация: 6 |
Цитата Мне кажется, что волновым простенько получится.. А на счет повторного прохода ты как раз и не прав, более дешевый путь не обязательно самый короткий (могу пример привести, если что ). но если в нем есть проход по одной клетке 2 раза ,то это не будет самым дешевым путем ,если из пути удалить клетки пройденные между этими двумя вхождениями на одну клетку ,то и длина пути и стоимость сократятся. самый эффективный метод -- алгоритм дейкстры. Или метод предложенный mlc. Перебор при n+m > 15 не пройдет по времени. -------------------- |
|
|
|
| Malice |
26.07.2005 11:48
Сообщение
#8
|
|
Профи Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: 20 |
Цитата(virt @ 26.07.05 7:40) но если в нем есть проход по одной клетке 2 раза ,то это не будет самым дешевым путем... Проход 2 раза имеется в виду в процессе поиску пути, а не в конечном варианте, конечно же Просто в волновом алгоритме (классическом) значение в куждую клетку пишется 1 раз, а здесь возможен повторный проход. Поэтому, кстати, рекурсия в итоге выльется в полный перебор.А может и вру, ни кто не хочет попробовать? |
|
|
|
| volvo |
26.07.2005 14:26
Сообщение
#9
|
|
Гость |
Цитата(Malice @ 26.07.05 11:48) А может и вру, ни кто не хочет попробовать? :no: Уже пробовал как-то, была подобная задача... Рекурсию делать не стоит, будет именно полный перебор, я все-таки остановился на алгоритме Дейкстры. |
|
|
|
| Archon |
26.07.2005 23:09
Сообщение
#10
|
|
Профи Группа: Пользователи Сообщений: 618 Пол: Мужской Репутация: 24 |
А если ограничить пребор прохождением по клетке 2-ой раз? Если клетка уже встречалась, берём следующий вариант. А алгоритм Дейкстры и волновой мне не понравились потому, что непреодолимых препятствий на карте нет и любой из этих алгоритмов в конечном счёте сведётся к тому же перебору. Завтра попробую написать, если получится, выложу.
-------------------- Close the World...txeN eht nepO
|
|
|
|
| Guest |
27.07.2005 7:17
Сообщение
#11
|
|
Гость |
Цитата(Archon @ 26.07.05 23:09) А если ограничить пребор прохождением по клетке 2-ой раз? Завтра попробую написать, если получится, выложу. Рекурсией попробуешь? Давай, буду ждать. Если на работе опять будет нечего делать, тоже попробую волну. |
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 21.09.2024 1:11 |