Максимальный цикл в графе
 |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
| ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
| [216.73.216.21] |
|
|
правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
Модераторы: Akina, shadeofgray
| Страницы: (2) 1 [2] все ( Перейти к последнему сообщению ) |
Максимальный цикл в графе
|
Сообщ.
#16
,
|
|
|
|
Цитата kl @ Совершенно очевидно, что это NP-complete задача, ибо если бы за полиномиальное время можно было бы найти максимальный простой цикл, то мы бы автоматически решили бы и TSP (задачу коммивояжера). Просто путем проверки, гамильтонов ли цикл. Так что про точный алгоритм можно забыть (если конечно P != NP). Лучшее что придумало человечество на сегодняшний день - H.N. Gabow. Finding Paths and Cycles of Superpolylogarithmic Length, In Proceedings of the 36th ACM Symposium on the Theory of Computing (STOC), 2004, 407-416 Но и там циклы далеки от максимальных. Правда время полиномиально Правильно ли я понимаю, что если будет приведен не эвристический, а алгоритм точного нахождения решения исходной задачи за полиномиальное время, то многие в мире скажут Спасибо? |
0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
0 пользователей:
[ Script execution time: 0,0143 ] [ 15 queries used ] [ Generated: 23.06.25, 16:51 GMT ]