Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Поиск самого дешёвого пути в Графе по Матрице

Автор: MiwKaGammY 5.6.2008, 12:21

Есть изначальные данные: матрица X,Y;задаються стены. Сначало есть К-денег, за каждый ход надо платить А, а если ход отличаеться от предыдущего по направлению то A+B; в некоторых клеточках есть цифры, если путь проходит через клеточку то K=K+цифра. Задача как обычно найти путь от Start до Finish и при этом потратить как можно меньше денег. Но проблема в том что я не могу подобрать алгоритм    A* находит путь ,но не учитывает цену и бонусы для Форда-Беллмана я не могу создать матрицу цен(минимальная стоймость от вершины до вершины) - или я просто туплю? С самого начало я подумал что здесь точно граф, но потом начало складываться что может быть попробовать какие-нибудь алгоритмы из "Поиск Максимального Потока" или что нить из Динамического Программирования...  Собственно у кого какие соображения?  Буду Благодарен За Любые Идеи && Предложения

Автор: skyboy 5.6.2008, 12:25

Цитата(MiwKaGammY @  5.6.2008,  11:21 )  я не могу создать матрицу цен(минимальная стоймость от вершины до вершины) учитывая условие  Цитата(MiwKaGammY @  5.6.2008,  11:21 )  если ход отличаеться от предыдущего по направлению то A+B у тебя не получится матрица смежности, т.к. стоимость перехода между каждыми двумя вершинами величина непостоянная. какая размерность? может, поиск в глубину будет приемлимым решением?

Автор: MiwKaGammY 5.6.2008, 12:36

X,Y<=10^6; 1 ≤ A ≤ 100, 1 ≤ B ≤ 100; 0 ≤ Количесто бонусов на карте  ≤ 20; 10 секунд на выполнение; а разве DFS подойдёт? без изменений?

Автор: skyboy 5.6.2008, 12:48

уу... с таким количеством будет сложно :( Цитата(MiwKaGammY @  5.6.2008,  11:36 ) а разве DFS подойдёт? без изменений?  а чего бы ему не подойти? по-моему, самый универсальный(потому - потенциально самый медленный) алгоритм. но с такими ограничениями... не знаю, скорее всего на несколько порядков дольше будет. задачка олимпиадная, что ли?

Автор: MiwKaGammY 5.6.2008, 13:08

горизонтальный обход дерева(по ширине) это DFS(Depth-first search) или BFS(Best-first_search)  ? Добавлено через 11 минут и 5 секунд мм DFS не прокатит потому что у меня ещё есть бонусы.. и как бы DFS найдёт мне дорогу, а рядом будет вершина с бонусом и если бы я через неё прошёл я бы потратил бы ещё чуть чуть но заработал бы много =)  может искать все пути ? какой для этого алгоритм подошёл бы в матрице?

Автор: skyboy 5.6.2008, 13:36

у тебя задача - потратить как можно меньше денег, или чтоб в конце пути осталось как можно больше? Добавлено через 1 минуту и 9 секунд Цитата(MiwKaGammY @  5.6.2008,  12:08 ) мм DFS не прокатит потому что у меня ещё есть бонусы.. убрать проверку на минимальность текущего пути относительно стоимости существующего полного пути. и тебе DFS станет  Цитата(MiwKaGammY @  5.6.2008,  12:08 )  искать все пути Добавлено через 1 минуту и 44 секунды текущая сумма денег может принимать отрицательные значения?

Автор: MiwKaGammY 5.6.2008, 14:32

Задача: подсчитать максимальное возможное кол-во денег которое можно получить дойдя до финиша текущая сумма - нет

Автор: skyboy 5.6.2008, 14:46

Цитата(MiwKaGammY @  5.6.2008,  13:32 ) подсчитать максимальное возможное кол-во денег которое можно получить дойдя до финиша хехе. а через одну и ту же клетку можно проходить несколько раз? если да, то можно тупо топтаться на клетках, дающих "деньги". до бесконечности  зы Я не цепляюсь к условию. Просто, если найти "слабое место", можно будет обойтись простым алгоритмом и продемонстрировать смекалку. Если надо решение именно в такой постановке(для чего?) - просто скажи. Добавлено через 10 секунд идей пока никаких.

Автор: MiwKaGammY 5.6.2008, 14:56

не, топтаться нельзя     тут просто тупо надо найти решение .... :/ постоновка именно такая :( я просто жудко туплю, у меня задаються данные стены, положения старта/финиша,координаты бонусов, и цены... я не могу себе представить как это можно представить... в виде ребер или матрицы смежности, тоесть сразу можно отбросить такие алгоритмы :///  тут надо какую то волну пустить - но она не учтёт бонусы... чем можно перебрать все возможные пути? - запущу несколько Thread`ов 4gb памяти и всё будет классно =]

Автор: maxim1000 5.6.2008, 15:11

если допустим проход по одной клетке несколько раз, перебрать все возможные пути не получится - их будет бесконечно много

Автор: MiwKaGammY 5.6.2008, 15:19

ну исключить вовсе или можно добавить условие, что бы не ходишь по одной и той же клете в одном и том же направлении ну хоть как то

Автор: subdmitry 10.6.2008, 21:50

Рассматривай граф, в котором вершине соответствует пара (позиция в матрице, направление по которому пришли в эту позицию). Тогда задача сведется к алгоритму Дейкстры. Правда, если, как ты говоришь, размер матрицы до 10^6 x 10^6, то решать ее Дейкстрой может быть несколько накладно (или я не правильно понял?), хотя тут можно придумать другие алгоритмы.

Автор: Paulskit 12.6.2008, 18:55

+1 за Дейкстру. Недавно тоже была похожая задача - алгоритм Дейкстры идеально подошел.

Автор: subdmitry 13.6.2008, 17:39

Дейкстра заведомо не уложится в отведенные 10 секунд. Перебирать 10^12 позиций поля за это время на современной технике нереально. Надо смотреть что-то из разряда path finding.  В общем, тут нужна херуистика, ведущая как-то к цели. Если бы не было стен, все было бы просто, а так лично мне не вполне понятно, как это делать. Знаю только, что эта область хорошо разработана программистами компьютерных игр.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)