RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив
Дискретн. анализ и исслед. опер., 2011, том 18, выпуск 1, страницы 27–40 (Mi da636)
Эта публикация цитируется в 1 статье

О сложности оптимальной рекомбинации для задачи коммивояжёра

А. В. Еремеев

Омский филиал Института математики им. С. Л. Соболева СО РАН, Омск, Россия

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

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

УДК: 519.854

Статья поступила: 02.08.2010
Переработанный вариант: 18.10.2010



Реферативные базы данных:

© МИАН, 2024