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