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

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



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

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

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

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

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

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

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

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

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


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

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

Путь 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;

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

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

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

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

Это сообщение отредактировал(а) Нурик Сакура - 10.7.2012, 19:20