4551
правка
Задача коммивояжера с несколькими внутренними точками: различия между версиями
Материал из WEGA
Задача коммивояжера с несколькими внутренними точками (посмотреть исходный код)
Версия от 10:53, 25 мая 2018
, 25 мая 2018→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 35: | Строка 35: | ||
Хоффман и Окамото [ ] доказали, что задача является разрешимой с фиксированным параметром, считая параметром количество внутренних точек k. Временная сложность предложенного ими алгоритма составляет O( | Хоффман и Окамото [10] доказали, что задача является разрешимой с фиксированным параметром, считая параметром количество внутренних точек k. Временная сложность предложенного ими алгоритма составляет <math>O(6^k n^5 log \; n)</math>. Грантсон, Боргельт и Левкопулос [6] улучшили ее до <math>O(4^k k n^4) \;</math>, а Спиллнер [18] – до <math>O(2^k k n^3) \;</math>. Еще один алгоритм с фиксированным параметром был предложен Грантсон, Боргельтом и Левкопулосом в работах [7, 8]. Наилучший известный на данный момент результат временной сложности получили Кнауэр и Спиллнер; он составляет <math>O(2^{c \sqrt{k} \; log \; k} k^{3/2} n^3)</math>, где <math>c = (2 + \sqrt{2})/(\sqrt{3} - \sqrt{2}) < 11</math>. | ||
