|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
25.04.2011, 18:41 | #1 |
Регистрация: 19.12.2010
Сообщений: 6
|
Найти минимальный путь между элементами матрицы
Помогите разобраться с решением задачи
Дана целочисленная матрица MxN (максимальный размер - 8х8). В ней указывают 2 элемента, и между ними нужно найти путь, по которому сумма элементов будет минимальна. Каким образом получить все пути (понятно, что из каждой клетки можно пойти по 3 путям, потом из каждой ещё по трём и т.п., но я с рекурсией не очень дружу) или как сюда прикрутить алгоритм Дейкстры? |
25.04.2011, 18:59 | #2 |
Форумчанин
Регистрация: 25.12.2010
Сообщений: 247
|
алгоритм Дейкстры это не то, здесь нужен поиск в ширину, нужно создать вторую матрицу (ну или еще одно поле в этой же), и по мере поиска записывать в нее будет записана сумма очков полученная при до хождении до нее, потом когда дойдешь до цели используй жадный (в данном случае наоботрот не жадный) алгоритм чтобы найти оптимальный путь
|
25.04.2011, 18:59 | #3 |
Старожил
Регистрация: 31.05.2010
Сообщений: 13,543
|
Дался Вам этот Дейкстра. Вот нормальный алгоритм:
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder |
25.04.2011, 19:43 | #4 |
Регистрация: 19.12.2010
Сообщений: 6
|
ОК, я попозже поразбираюсь ещё с этим, но то, что на кратинке, вроде не совсем подходит к моей задаче... Потому что там из угла в угол, и там путь в целом может быть направлен вверх/влево/по диагонали, а у меня - во все 4 стороны, и тот метод вроде не подходит в таком случае.
|
25.04.2011, 19:48 | #5 |
Старожил
Регистрация: 31.05.2010
Сообщений: 13,543
|
Это то, что нужно. Дело в том, что если заданы два элемента внутри матрицы, мы усекаем матрицу до m, n и ищем путь в этом подпространстве.
Этот путь всегда будет лежать внутри этой подматрицы, не верите? Проверьте.
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder Последний раз редактировалось Smitt&Wesson; 25.04.2011 в 19:52. |
25.04.2011, 19:51 | #6 |
Регистрация: 19.12.2010
Сообщений: 6
|
Код:
|
25.04.2011, 19:57 | #7 |
Старожил
Регистрация: 31.05.2010
Сообщений: 13,543
|
В этом случае согласен. Алгоритм работает с реальной стоимостью проезда по дорогам. Т.е. с реальными затратами. А в произвольной матрице, сдесь надо с гра'фами работать.
Скорее всего нахождение максимального потока в гра'фе. Но и в этом случае, матрицу придёться перестраивать. Графы (направленные) имеют вход и выход. Внутри графа, путь найти невозможно (по крайней мере, я такого не встречал.).
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder Последний раз редактировалось Smitt&Wesson; 25.04.2011 в 20:00. |
25.04.2011, 20:00 | #8 |
Регистрация: 19.12.2010
Сообщений: 6
|
Ну вот в этом вся и беда, какие-либо частные случаи этой задачи я бы осилил без проблем, но вот такую не получается уже недели две Кроме как получать все возможные пути, не вижу решения, а с этим у меня проблема.
|
25.04.2011, 20:01 | #9 |
Старожил
Регистрация: 04.02.2009
Сообщений: 17,351
|
Алгоритм Дейкстры описан в журнале ПРОграммист, исходники на Дельфи. Но там немного по-другому задается маршрут...
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Обработка матриц.В каждой строке матрицы найти первый минимальный и первый максимальный элементы и поменя | ride013 | Помощь студентам | 4 | 20.04.2011 13:14 |
Си найти минимальный путь от точки до точки | dikr | Помощь студентам | 4 | 09.05.2010 11:58 |
Найти кратчайший путь между точками | lucky | Общие вопросы Delphi | 0 | 27.05.2009 07:26 |
найти минимальный элемент в каждой строке матрицы и записать все минимальные элементы в отдельный массив | W_P | Помощь студентам | 6 | 28.12.2007 00:24 |