 Поиск кратчайшего пути |
Прочтите прежде чем задавать вопрос!
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 |
26.07.2005 23:09
Сообщение
#2
|
 Профи Группа: Пользователи Сообщений: 618 Пол: Мужской Репутация: 24 |
А если ограничить пребор прохождением по клетке 2-ой раз? Если клетка уже встречалась, берём следующий вариант. А алгоритм Дейкстры и волновой мне не понравились потому, что непреодолимых препятствий на карте нет и любой из этих алгоритмов в конечном счёте сведётся к тому же перебору. Завтра попробую написать, если получится, выложу.
-------------------- Close the World...txeN eht nepO
|
|
|
|
| Guest |
27.07.2005 7:17
Сообщение
#3
|
|
Гость |
Цитата(Archon @ 26.07.05 23:09) А если ограничить пребор прохождением по клетке 2-ой раз? Завтра попробую написать, если получится, выложу.  Рекурсией попробуешь? Давай, буду ждать. Если на работе опять будет нечего делать, тоже попробую волну. |
|
|
|
Сообщений в этой теме
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 Archon Алгоритм дейкстры, волновой метод... Зачем? Тут ба... 25.07.2005 21:35
Malice
Мне кажется, что волновым простенько получится..... 25.07.2005 22:07 virt
но если в нем есть проход по одной клетке 2 раза... 26.07.2005 7:40 Malice
Проход 2 раза имеется в виду в процессе поиску п... 26.07.2005 11:48 volvo
:no: Уже пробовал как-то, была подобная задача..... 26.07.2005 14:26 |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 4.07.2025 5:21 |