Що таке проблема комівояжера?
З: Що таке проблема комівояжера?
В: Задача комівояжера (ЗК) - це класична алгоритмічна задача в галузі інформатики та дослідження операцій. Вона фокусується на оптимізації, причому кращі рішення часто означають дешевші, коротші або швидші рішення.
З: Як виражається TSP?
В: Найпростіше TSP можна представити у вигляді графа, що описує розташування множини вершин.
З: Хто вперше визначив ОСТ?
В: Задача комівояжера була сформульована у 1800-х роках ірландським математиком В. Р. Гамільтоном та британським математиком Томасом Кіркманом.
З: Хто досліджував її у 1930-х роках?
В: У 1930-х роках математики Карл Менгер у Відні та Гарварді продовжували вивчати її.
З: Що незабаром після цього представив Гаслер Вітні?
В: Хаслер Вітні з Прінстонського університету ввів назву "задача комівояжера" незабаром після її визначення.
З: Що означає "краще рішення" в цьому контексті?
В: У цьому контексті кращий розв'язок часто означає розв'язок, який є дешевшим, коротшим або швидшим.
З: Який алгоритм Менгер вважав очевидним при вивченні TSP?
В: Менгер вважав очевидним алгоритм грубої сили при вивченні TSP і помітив, що використання евристики найближчого сусіда не завжди дає оптимальні результати.
