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