Що таке проблема комівояжера?

З: Що таке проблема комівояжера?

В: Задача комівояжера (ЗК) - це класична алгоритмічна задача в галузі інформатики та дослідження операцій. Вона фокусується на оптимізації, причому кращі рішення часто означають дешевші, коротші або швидші рішення.

З: Як виражається TSP?

В: Найпростіше TSP можна представити у вигляді графа, що описує розташування множини вершин.

З: Хто вперше визначив ОСТ?

В: Задача комівояжера була сформульована у 1800-х роках ірландським математиком В. Р. Гамільтоном та британським математиком Томасом Кіркманом.

З: Хто досліджував її у 1930-х роках?

В: У 1930-х роках математики Карл Менгер у Відні та Гарварді продовжували вивчати її.

З: Що незабаром після цього представив Гаслер Вітні?

В: Хаслер Вітні з Прінстонського університету ввів назву "задача комівояжера" незабаром після її визначення.

З: Що означає "краще рішення" в цьому контексті?

В: У цьому контексті кращий розв'язок часто означає розв'язок, який є дешевшим, коротшим або швидшим.

З: Який алгоритм Менгер вважав очевидним при вивченні TSP?

В: Менгер вважав очевидним алгоритм грубої сили при вивченні TSP і помітив, що використання евристики найближчого сусіда не завжди дає оптимальні результати.