Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

Вернуться   Форум программистов > Технологии > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail


Ответ
 
Опции темы
Старый 25.04.2011, 18:41   #1
Sanek-MU
 
Регистрация: 19.12.2010
Сообщений: 6
По умолчанию Найти минимальный путь между элементами матрицы

Помогите разобраться с решением задачи
Дана целочисленная матрица MxN (максимальный размер - 8х8). В ней указывают 2 элемента, и между ними нужно найти путь, по которому сумма элементов будет минимальна.
Каким образом получить все пути (понятно, что из каждой клетки можно пойти по 3 путям, потом из каждой ещё по трём и т.п., но я с рекурсией не очень дружу) или как сюда прикрутить алгоритм Дейкстры?
Sanek-MU вне форума Ответить с цитированием
Старый 25.04.2011, 18:59   #2
ololo-schoolboy
Форумчанин
 
Регистрация: 25.12.2010
Сообщений: 247
По умолчанию

алгоритм Дейкстры это не то, здесь нужен поиск в ширину, нужно создать вторую матрицу (ну или еще одно поле в этой же), и по мере поиска записывать в нее будет записана сумма очков полученная при до хождении до нее, потом когда дойдешь до цели используй жадный (в данном случае наоботрот не жадный) алгоритм чтобы найти оптимальный путь
ololo-schoolboy вне форума Ответить с цитированием
Старый 25.04.2011, 18:59   #3
Smitt&Wesson
Старожил
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Сообщений: 13,968
По умолчанию

Дался Вам этот Дейкстра. Вот нормальный алгоритм:
Изображения
Тип файла: jpg Короткий-путь1.jpg (537.0 Кб, 195 просмотров)
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder
Smitt&Wesson вне форума Ответить с цитированием
Старый 25.04.2011, 19:43   #4
Sanek-MU
 
Регистрация: 19.12.2010
Сообщений: 6
По умолчанию

ОК, я попозже поразбираюсь ещё с этим, но то, что на кратинке, вроде не совсем подходит к моей задаче... Потому что там из угла в угол, и там путь в целом может быть направлен вверх/влево/по диагонали, а у меня - во все 4 стороны, и тот метод вроде не подходит в таком случае.
Sanek-MU вне форума Ответить с цитированием
Старый 25.04.2011, 19:48   #5
Smitt&Wesson
Старожил
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Сообщений: 13,968
По умолчанию

Это то, что нужно. Дело в том, что если заданы два элемента внутри матрицы, мы усекаем матрицу до m, n и ищем путь в этом подпространстве.
Этот путь всегда будет лежать внутри этой подматрицы, не верите? Проверьте.
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder

Последний раз редактировалось Smitt&Wesson; 25.04.2011 в 19:52.
Smitt&Wesson вне форума Ответить с цитированием
Старый 25.04.2011, 19:51   #6
Sanek-MU
 
Регистрация: 19.12.2010
Сообщений: 6
По умолчанию

Код:
100  1   1   1 
100  9  100  1 
100 100 100  9 
100 100 100 100
Путь между девятками разве лежит в усечённой матрице?
Sanek-MU вне форума Ответить с цитированием
Старый 25.04.2011, 19:57   #7
Smitt&Wesson
Старожил
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Сообщений: 13,968
По умолчанию

В этом случае согласен. Алгоритм работает с реальной стоимостью проезда по дорогам. Т.е. с реальными затратами. А в произвольной матрице, сдесь надо с гра'фами работать.
Скорее всего нахождение максимального потока в гра'фе.
Но и в этом случае, матрицу придёться перестраивать. Графы (направленные) имеют вход и выход.
Внутри графа, путь найти невозможно (по крайней мере, я такого не встречал.).
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder

Последний раз редактировалось Smitt&Wesson; 25.04.2011 в 20:00.
Smitt&Wesson вне форума Ответить с цитированием
Старый 25.04.2011, 20:00   #8
Sanek-MU
 
Регистрация: 19.12.2010
Сообщений: 6
По умолчанию

Ну вот в этом вся и беда, какие-либо частные случаи этой задачи я бы осилил без проблем, но вот такую не получается уже недели две Кроме как получать все возможные пути, не вижу решения, а с этим у меня проблема.
Sanek-MU вне форума Ответить с цитированием
Старый 25.04.2011, 20:01   #9
Utkin
Старожил
 
Аватар для Utkin
 
Регистрация: 04.02.2009
Сообщений: 18,305
По умолчанию

Алгоритм Дейкстры описан в журнале ПРОграммист, исходники на Дельфи. Но там немного по-другому задается маршрут...
Маньяк-самоучка
Utkin появился в результате деления на нуль.
Осторожно! Альтернативная логика
Utkin вне форума Ответить с цитированием
Ответ

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Опции темы


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Обработка матриц.В каждой строке матрицы найти первый минимальный и первый максимальный элементы и поменя 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 01:24