Алгоритмы поиска ДЛИННЫХ путей

← →
FlameHeap (2002-11-19 09:45) [0]

Здравсвуйте!
Везде всегда очень подробно рассматриаются алгоритмы нахождения самых коротких и "дешевых" путей... А есть ли какие-нибудь алгоритмы нахождения самого длинного пути? Имеется ввиду путь на графе из узла А в узел В не содержащий циклов и обладающей наибольшей стоимостью... Или какую эвристику можно применить для поиска подобного пути на большом графе (порядка 100000 узлов)???
Заранее благодарен.

← →
Ich Hasse © (2002-11-19 20:43) [1]

А можно вопрос зачем искать "длинный" путь???

Используй какой-нибудь волновой алгоритм...

← →
FlameHeap (2002-11-20 08:00) [2]

Грубо говоря, процесс (игру :)) можно разделить на 2 этапа:
1. Активный - захват ресурсов и ограничение противника... (здесь с алгоритмами всё ясно - проблем никаких)
2. Пассивный - наиболее рациональное использование захваченных ресурсов. Т.к. использование одних ресурсов автоматически запрещает использование других, то необходимо определить самый "длинный" путь, т.е. такой график использования захваченных ресурсов, при котором удастся просуществовать как можно дольше...

← →
Mitrofan (2002-11-20 10:47) [3]

Возможно алгоритм нахождения максимального пути следующий:
Делаем для каждого ребра графа следующее:
длина_ребра := - длина_ребра;
и далее решаем задачу нахождения минимального пути на том же самом графе. Но насчет правильности не уверен :)

← →
FlameHeap (2002-11-20 13:30) [4]

Алгоритмы нахождения минимального пути при отрицательном весе ребер приводят к полному перебору, что, к сожалению, неприемлемо... :(((

← →
Mitrofan (2002-11-20 13:51) [5]

Тогда может следующая формула подойдет:
для каждого ребра делаем:
длина_ребра := максимальноая_длина_ребра - длина_ребра
И затем ищем минимальный путь.

Ищем все пути из одой вершины в другую, не выделяя кратчайший!!!
А потом определяем какой кратчайший а какой длиннейший!!!

Литература:
"Математика для программистов"
Раздел "Теория графов" Алгоритм Дейкстры.....
Я специально такой проблеммой не интересовался, но можно, думаю, это сделать!
Или ещё вариант:
Разделить путь на 2(3,4,5 и т.д) т.е.
ищешь кратчайший путь до "любой" вершины, а от неё до нужной!!!
А вот как выбрать "любую" вершину - это исходя из решаемой задачи.

Алгоритмы поиска ДЛИННЫХ путей Найти похожие ветки