Завдання про комівояжера - це

Усі ефективні (що скорочують повний перебір) методи розв'язання задачі комівояжера - методи евристичні. У більшості евристичних методів не найефективніший маршрут, а наближене рішення. Найчастіше затребувані звані any-time алгоритми, тобто поступово поліпшують деяке поточне наближене рішення.

Завдання комівояжера є NP-повне завдання. Часто у ньому проводять обкатку нових підходів до евристичного скорочення повного перебору.

На практиці застосовуються різні модифікації ефективніших методів: метод гілок та кордонів та метод генетичних алгоритмів, а також алгоритм мурашиної колонії.

Метод гілок та кордонів

Література

  • Ананій В. ЛевітінГлава 3. Метод грубої сили: Завдання комівояжера// Алгоритми: введення в розробку та аналіз = Introduction to The Design and Analysis of Algorithms. - М.: "Вільямс", 2006. - С. 159-160. - ISBN 0-201-74395-7
  • Томас Х. Кормен, Чарльз І. Лейзерсон, Рональд Л. Рівест, Кліффорд ШтайнАлгоритми: побудова та аналіз= Introduction to Algorithms. - 2-ге вид. - М.: "Вільямс", 2006. - С. 1296. - ISBN 0-07-013151-1

Примітки

  1. ↑Костевич Л.С. Математичне програмування: Інформ. технології оптимальних рішень: Навч. посібник/Л.С. Костевич. - Мн.: Нове знання, 2003. іл., стор 150, ISBN 985-6516-83-8

Упаковка в контейнери: двомірна упаковка • лінійна упаковка • пакування за вагою • пакування за вартістю

Завдання про ранець (рюкзак)Бульова формулаЗавдання здійсненності булевих формулКомівояжерЗавдання комівояжераВершинне покриттяЗавдання про вершинне покриттяКлікаЗавдання про клікНезалежна множинаЗавдання про незалежну множину (набір)Покриття множиниЗавдання про покриття безлічіЛатинський квадратЗавдання про заповнення латинського квадратаУзагальнене судокуЗавдання узагальненого судокуКакуроЗавдання якуроПлями (узагальнені)Завдання пошуку найкоротшого рішення (кістяків більше 15)Класи складності

Wikimedia Foundation. 2010 .

Дивитись що таке "Завдання про комівояжера" в інших словниках:

завдання про комівояжера — задача про бродячого торговця Вид задачі математичного програмування, полягає у відшуканні найкращого маршруту для комівояжера (бродячого торговця), який повинен об'їхати всі доручені йому міста і повернутися назад за найкоротший термін або з ... Довідник технічного перекладача

Завдання Про Комівояжера — завдання математичного програмування щодо визначення оптимального маршруту руху комівояжера, мета якого полягає в тому, щоб відвідати всі об'єкти, записані в завданні, за найкоротший термін і з найменшими витратами. Теоретично графів З.о до … Словник бізнес-термінів

ЗАДАЧА ПРО КОМІВОЯЖЕР — вид завдання математичного програмування; полягає у відшуканні найкращого маршруту для комівояжера, який повинен об'їхати всі доручені йому міста та повернутися назад за найкоротший термін або з найменшими витратами на проїзд. Мовою теорії… … Великий економічний словник

ЗАДАЧА ПРО КОМІВОЯЖЕР — (TRAVELING SALESMAN PROBLEM) вид задачі програмування матем., полягає у відшуканні найкращого маршруту для комівояжера, який повинен об'їхати всі доручені йому міста і повернутися назад за найкоротший термін або з найменшимивитратами на… … Глосарій термінів з вантажоперевезень, логістики, митного оформлення

Завдання про комівояжера, про бродячого торговця — [travelling salesman problem] вид завдання математичного програмування, полягає у відшуканні найкращого маршруту для комівояжера (бродячого торговця), який повинен об'їхати всі доручені йому міста і повернутися назад за найкоротший термін або з … Економіко-математичний словник

Завдання комівояжера — Оптимальний маршрут комівояжера через 15 найбільших міст Німеччини. Вказаний маршрут є найкоротшим із усіх можливих 43 589 145 600. Завдання комівояжера (англ. Travelling salesman problem, TSP) (комівояжер … Вікіпедія

З — Забалансове фінансування (Оff balance sheet finance) Забалансові рахунки (Оff balance accounts) Залежна компанія (підприємство) (affiliated company) … Економіко-математичний словник

ДИСКРЕТНЕ ПРОГРАМУВАННЯ — галузь математики, що займається дослідженням та вирішенням екстремальних завдань на кінцевих множинах. Нехай М=і f числова функція, визначена на елементах множини М. Потрібно знайти елемент на кром досягається абсолютний … Математична енциклопедія

Дискретне програмування — [discrete programming] розділ оптимального програмування, вивчає екстремальні завдання, у яких шукані змінні накладається умова цілісності, а область допустимих рішень кінцева. Таким чином, тут використовується модель... Економіко-математичний словник

Теорія розкладів — [scheduling theory] наукова дисципліна, присвячена розробці методів оптимізації оперативно-календарного планування. Завдання Т.Р. один із видів завдань дослідження операцій, що об'єднуються у класі завдань упорядкування.Вони полягають у визначенні... Економіко-математичний словник