Форум программистов [Powered by Invision Power Board]

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

Форум программистов > Алгоритмы > [REQUEST] Алгоритмы для поиска длиннейшего пути

Автор: Нурик Сакура 9.7.2012, 15:49

Доброго времени суток, уважаемые Винградовцы =^_^=

Возникла у меня небольшая проблема. Пытаюсь решить задачку поиска длиннейшего пути, но что-то пока не преуспел. Точнее, если пойти тупым перебором, то оно, конечно, решится. В теории. Но как-то я не очень люблю такие методы. Потому решил обратиться к вам, авось кто-то натолкнет на здравые мысли или хотя бы укажет направление, в котором нужно копать. Итак...

Цитата

Дана матрица N x M, представляющая собой карту проходимости: ячейки со значением 0 заблокированы, ячейки со значением 1 - свободны. Необходимо из некой заданной свободной точки (x, y) найти максимально длинный (проходящий через максимальное количество ячеек) и максимально дешевый (см.дальше) односторонний (каждую ячейку можно посетить лишь один раз) путь. Передвигаться можно двумя способами. "Прямо" - вверх, вниз, влево или вправо, каждое такое движение стоит 1 очко действия. "Диагонально" - вверх-влево, вверх-вправо, вниз-влево, вниз-вправо, каждое такое движение стоит 2 очка действия. Чем меньше суммарно затрачено очков действия, тем лучше - это и есть та самая "дешевизна".

Да, несомненно, прежде чем писать сюда, я воспользовался гуглом и кое-какими залежами памяти о теории графов и поисках пути, но большая часть того, что мне удалось найти, в основном, ориентирована на поиск кратчайшего пути из точки А в точку Б.

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

P.S.: я не прошу решить задачу за меня, мне нужна подсказка, куда двигать мысли. Но буду признателен (и дам плюс в репу) за любой рабочий код по теме smile

Автор: mrgloom 10.7.2012, 13:10

http://en.wikipedia.org/wiki/Longest_path_problem
http://stackoverflow.com/questions/2529130/graph-longest-path
NP-hard

Автор: baldina 10.7.2012, 14:44

Нурик Сакура, Вы ищете точное решение, или подойдет приближенное?

Автор: Нурик Сакура 10.7.2012, 16:39

Хм, интересно, а в чем может быть приближение?

Задача, как мне кажется, предельно проста - есть точка А, есть карта всех точек, куда можно/нельзя идти. Найти путь, проходящий через максимальное количество точек, с минимальными суммарными затратами. Обычный перебор будет решать долго, но, в конечном итоге, выдаст одно или несколько решений. Точных решений. Так в чем "приближение"?

Автор: baldina 10.7.2012, 17:18

Цитата(Нурик Сакура @ 10.7.2012, 16:39

)

Хм, интересно, а в чем может быть приближение?

поиск приближенное решения - один из традиционных подходов к решению NP-сложных задач. иначе - полный перебор.
если Вы удовлетворитесь приближением, можно было рекомендовать алгоритм Дейкстры, в котором в качестве критерия выступает не минимальный путь, а максимальный путь+вес хода. Кстати, баланс между длиной пути и весами переходов у вас не определен.

Автор: Нурик Сакура 10.7.2012, 18:18

Цитата(baldina @ 10.7.2012, 17:18

)

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

Спасибо за идею, посмотрю.

Цитата(baldina @ 10.7.2012, 17:18

)

Кстати, баланс между длиной пути и весами переходов у вас не определен

Немного не понял, как именно он должен быть определен? Я вроде указал, что:

Цитата(Нурик Сакура @ 9.7.2012, 15:49

)

Чем меньше суммарно затрачено очков действия, тем лучше - это и есть та самая "дешевизна".

Таким образом, из двух путей одинаковой длины необходимо выбрать тот, у которого суммарные затраты на переходы меньше. Например:

Путь 1:
F(1;1) -> T(1;2) -> 1 AP;
F(1;2) -> T(1;3) -> 1 AP;
F(1;3) -> T(2;3) -> 1 AP;
F(2;3) -> T(3;4) -> 2 AP;

Путь 2:
F(1;1) -> T(2;1) -> 1 AP;
F(2;1) -> T(3;2) -> 2 AP;
F(3;2) -> T(2;3) -> 2 AP;
F(2;3) -> T(3;4) -> 2 AP;

Оба пути одинаковой длины. Но второй "дороже" первого.

Автор: baldina 10.7.2012, 19:01

Цитата(Нурик Сакура @ 10.7.2012, 18:18

)

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

т.е. затраты на переходы работают только при равенстве путей? тогда ясно

Автор: Нурик Сакура 10.7.2012, 19:10

Хм... А вы меня на одну мысль натолкнули. Если найдется путь, который будет, например, сплошь по диагонали и он будет самым длинным, но при этом и очень "дорогим". В то же время, может существовать путь на несколько точек короче, но максимально дешевый. В идеале, "сыграть" должен он. Тогда, получается, в задаче смещается приоритет с "самый длинный" на "самый дешевый длинный".

Короче говоря, я так думаю, нужно избавляться от диагональных ходов. То есть оставить только четыре варианта "сдвига" - вверх, вниз, влево и вправо. Это существенно уменьшит количество возможных ходов и, соответственно, поиск самого длинного.