 Поиск кратчайшего пути |
Прочтите прежде чем задавать вопрос!
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 |
   |
 
|
  |
Ответов
| Archon |
25.07.2005 21:35
Сообщение
#2
|
 Профи Группа: Пользователи Сообщений: 618 Пол: Мужской Репутация: 24 |
Алгоритм дейкстры, волновой метод... Зачем? Тут банальный перебор с некоторыми ограничениями. Следует использовать тот факт, что проходить через клетку повотрно - бессмысленно, так как в таком случае штраф явно будет НЕ минимальным. Попробуй рекурсию.
-------------------- Close the World...txeN eht nepO
|
|
|
|
| Malice |
25.07.2005 22:07
Сообщение
#3
|
 Профи Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: 20 |
Цитата(Archon @ 25.07.05 21:35) Алгоритм дейкстры, волновой метод... Зачем? ... Попробуй рекурсию. Мне кажется, что волновым простенько получится.. А на счет повторного прохода ты как раз и не прав, более дешевый путь не обязательно самый короткий (могу пример привести, если что  ). |
|
|
|
Сообщений в этой теме
AlexPS Поиск кратчайшего пути 20.07.2005 16:13
mlc Можно и волновым методом, только не 1-цу прибавлят... 20.07.2005 16:28 AlexPS А можно поподробнее, что это за алгоритм... или гд... 20.07.2005 16:32 volvo http://algolist.manual.ru/games/wavealg.php
или go... 20.07.2005 17:14 virt
но если в нем есть проход по одной клетке 2 раза... 26.07.2005 7:40
Malice
Проход 2 раза имеется в виду в процессе поиску п... 26.07.2005 11:48 volvo
:no: Уже пробовал как-то, была подобная задача..... 26.07.2005 14:26 Archon А если ограничить пребор прохождением по клетке 2-... 26.07.2005 23:09 Guest
:) Рекурсией попробуешь? Давай, буду ждать. Ес... 27.07.2005 7:17 |
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 4.07.2025 5:25 |