Задача о гамильтоновом пути: различия между версиями

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