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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 17.03.2011, 13:06
Новичок

Отправить личное сообщение для stolzen Посмотреть профиль Найти все сообщения от stolzen
 
Регистрация: 03.03.2011
Сообщений: 2

максимальный путь
Имеется очень большой граф, кол-во вершин около 10^6, кол-во ребер - 10^6, Ребер раза в 1,5 больше, чем вершин, причем некоторые вершины имеют достаточно большое кол-во ребер (10, 20). В графе есть циклы.

Для поиска макс. пути можно запускать поиск в ширину из каждой вершины и смотреть, улучшился ли макс путь на этой итерации. Но это происходит ОЧЕНЬ долго. (O(n * (n + m)) = O(2 * 10^12)). За ночь работы программы ответ так и не был найден.

Какие алгоритмы можно использовать для ускорения? Может быть, какие-нибудь эвристики, дающие достаточно хороший приближенный результат.
  #2  
Старый 17.03.2011, 13:34
гocть

 
Сообщений: n/a

максимальный путь в графе с циклами это вообще-то бесконечность
  #3  
Старый 18.03.2011, 09:49
гость1

 
Сообщений: n/a

Если максимальный путь - это самый длинный, то это np-полная задача, вряд ли её удастся решить за O(n * (n + m)).
  #4  
Старый 18.03.2011, 10:31
гocть2

 
Сообщений: n/a

чё ты куришь? максимальный _простой_ путь - NP-полная.

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
замкнутый путь на графе bones Графы 1 23.08.2010 20:36
Путь в Дейкстре misterfix Графы 4 19.12.2009 22:38
Кратчайший путь из А в В siberx Графы 1 11.05.2009 21:25
Гамильтонов путь минимальной длины гость Графы 5 24.02.2009 01:27
Кратачайший путь (динамическое программирование) Николай Математические алгоритмы 6 06.06.2008 04:34