Loading AI tools
галузь оптимізації в прикладній математиці та інформатиці З Вікіпедії, вільної енциклопедії
Комбінаторна оптимізація (англ. Combinatorial optimization) — розділ теорії оптимізації. Розглядає задачі оптимізації, у яких множина розв'язків є дискретною або може бути зведена до дискретної.
Задача дискретної оптимізації визначається як четвірка , де:
Елементи називають екземплярами . Для кожного екземпляру елементи називають припустимими розв'язками .
В задачі комівояжера задане ціле та відстані між всіма парами міст у вигляді матриці , де . Обхід — це замкнений маршрут, що проходить через кожне місто один раз. Задача полягає у відшуканні обходу з найменшою довжиною.[1]
Можна взяти F={всі перестановки з об'єктів}. Кожна перестановка є обходом, якщо інтерпретувати як місто, відвідуване після міста , . Тоді вартість відображає в
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.