Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2003.04.21;
Скачать: CL | DM;

Вниз

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

 
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]

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


 
Miha-ha ©   (2002-11-24 09:51) [6]

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

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



Страницы: 1 вся ветка

Текущий архив: 2003.04.21;
Скачать: CL | DM;

Наверх




Память: 0.48 MB
Время: 0.022 c
3-67107
Ihtiandr
2003-04-02 16:44
2003.04.21
delete в FastReport


3-67093
Andrio
2003-04-02 14:25
2003.04.21
Экспорт таблицы из InterBase в Paradox


14-67494
Delpher_Gray
2003-04-03 15:02
2003.04.21
Не могу решить проблему...


3-67121
Sherbacov
2003-03-29 16:57
2003.04.21
Что надежнее?(Paradox или Access)


1-67367
Alexander1966
2003-04-09 15:56
2003.04.21
Спрятать форму с дочерними окнами