Задача о гамильтоновом пути: различия между версиями
| [непроверенная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Метки: отменено через визуальный редактор |
Jumpow (обсуждение | вклад) отклонено последнее 1 изменение (94.26.147.29): А вы знаете, что кроме O большого существует и o маленькое? Метка: ручная отмена |
||
Строка 19:
Андреас Бьёрклунд даёт альтернативный подход, использующий [[Формула включений-исключений|принцип включения/исключения]] для сокращения числа перебираемых гамильтоновых циклов и задача подсчёта циклов может быть решена путём вычисления определителя некоторой матрицы.
Используя этот метод, он показал, как решить задачу о гамильтоновом цикле для произвольных графов с ''n'' вершинами с помощью [[Алгоритм Монте-Карло|алгоритма Монте-Карло]] за время <math>O(1{,}657^n)</math>. Для [[Двудольный граф|двудольных графов]] этот алгоритм можно улучшить до времени <math>
Для графов с максимальной степенью три аккуратный [[поиск с возвратом]] может найти гамильтонов цикл (если таковой существует) за время <math>O(1{,}251^n)</math>{{sfn|Iwama, Nakashima|2007|с=108–117}}.
| |||