EN|RU

Том 18, номер 1, 2011 г., Стр. 27-40

УДК 519.854
Еремеев А. В.
О сложности оптимальной рекомбинации для задачи коммивояжёра

Аннотация:
Рассматривается вычислительная сложность оптимальной рекомбинации для задачи коммивояжёра в симметрическом и общем случаях. Доказана NP-трудность этих задач в сильном смысле, и рассмотрены подходы к их решению.
Ил. 3, библиогр. 15.

Ключевые слова: задача коммивояжёра, генетический алгоритм, оптимальная рекомбинация, вычислительная сложность, сводимость задач.

Еремеев Антон Валентинович 1
1. Омский филиал Института математики им. С. Л. Соболева СО РАН,
ул. Певцова, 13, 644099 Омск, Россия
е-mail: eremeev@ofim.oscsbras.ru

Статья поступила 2 августа 2010 г.
Исправленный вариант — 18 октября 2010 г.

 © Институт математики им. С. Л. Соболева, 2015