2389 читали · 2 года назад
Задача коммивояжера. Точное решение — метод целочисленного линейного программирования Мы уже пробовали решать точно задачу коммивояжёра методом динамического программирования и методом ветвей и границ. Результат неплох, но слабоват. В этой статье мы увидим, что точное решение ближе, чем принято считать. Будем использовать метод целочисленного программирования, который является частным случаем линейного программирования, который в свою очередь является подклассом математического программирования.
Какую задачу можно решить методом динамического программирования
Динамическое программирование – это мощный метод оптимизации, который применяется для решения задач, обладающих свойствами оптимальной подструктуры и перекрывающимися подзадачами. Задача: Дана последовательность чисел. Найти длину наибольшей возрастающей подпоследовательности. Решение: Псевдокод: for i in range(1, n): for j...