Комбинаторная оптимизация и задача коммивояжера
В задачах комбинаторной оптимизации требуется найти наилучшее из конечного, но обычно очень большого числа возможных решений. Если задача характеризуется характерным числом элементов (размерностью задачи), то типичное число возможных решений, из которых предстоит сделать выбор, растет экспоненциально - как
или еще скорее - как
(напомним, что согласно известной формуле Стирлинга
для достаточно больших
).
Это свойство делает простой метод перебора всех вариантов, в принципе гарантирующий решение при конечном числе альтернатив, чрезвычайно неэффективным, т.к. такое решение требует экспоненциально большого времени. Эффективными же признаются решения, гарантирующие получение ответа за полиномиальное время, растущее как полином с ростом размерности задачи, т.е. как
N. 1)
Различие между полиномиальными и экспоненциальными алгоритмами восходит к фон Нейману (von Neumann, 1953)
Задачи, допускающие гарантированное нахождение оптимума целевой функции за полиномиальное время, образуют класс
. Этот класс являюется подклассом более обширного класса
задач, в которых за полиномиальное время можно всего лишь оценить значение целевой функции для конкретной конфигурации, что, естественно, гораздо проще, чем выбрать наилучшую из всех конфигураций. До сих пор в точности не известно, совпадают ли эти два класса, или нет. Эта проблема,
, о которую сломано уже немало математических копий. Если бы эти классы совпадали, для любой задачи комбинаторной оптимизации, точное можно было бы гарантированно найти за полиномиальное время. В такой "подарок судьбы" никто не верит, и практически разрешимыми считаются задачи, допускающие полиномиальное решение хотя бы для типичных (а не наихудших) случаев. Такова, например, общая задача линейного программирования.
Для более трудных задач достаточно было бы и более слабого условия - нахождения субоптимальных решений, локальных минимумов целевой функции, не слишком сильно отличающихся от абсолютного минимума. Нейросетевые решения как раз и представляют собой параллельные алгоритмы, быстро находящие субоптимальные решения оптимизационных задач, минимизируя целевую функцию в процессе своего функционирования или обучения.
Самые трудные задачи класса
называют
-полными. Это название объясняется тем, что если бы удалось доказать, что существует полиномиальное решение такой задачи, то такое решение существовало бы и для любой другой задачи класса
, т.е. классы
и
совпадали бы. Поскольку, как уже говорилось, такой сценарий крайне маловероятен, именно для таких проблем наиболее важен поиск субоптимальных решений.
Все
-полные задачи одинаково сложны (поскольку все они сводятся друг к другу за полиномиальное время), и методы решения любой из них можно применять также и к другим задачам комбинаторной оптимизации. Поэтому нам в этой лекции достаточно сосредоточиться на одной такой задаче. Исторически наиболее исследованной и популярной задачей такого рода (своего рода "мушкой дрозофилой" комбинаторной оптимизации), которая используется для сравнения различных алгоритмов, стала задача коммивояжера.
В классической постановке, коммивояжер должен объехать
городов по замкнутому маршруту, посетив каждый из них лишь однажды, таким образом, чтобы полная длина его маршрута была минимальной. Если решать задачу коммивояжера "в лоб" - перебором всех замкнутых путей, связывающих
городов, то придется проверить все
возможных маршрутов. Будучи
-полной, задача коммивояжера не имеет практически реализуемого точного решения. На примере этой задачи мы ниже и рассмотрим различные методы ее приближенного решения с помощью нейросетей.
Самые трудные задачи класса
называют
-полными. Это название объясняется тем, что если бы удалось доказать, что существует полиномиальное решение такой задачи, то такое решение существовало бы и для любой другой задачи класса
, т.е. классы
и
совпадали бы. Поскольку, как уже говорилось, такой сценарий крайне маловероятен, именно для таких проблем наиболее важен поиск субоптимальных решений.
Все
-полные задачи одинаково сложны (поскольку все они сводятся друг к другу за полиномиальное время), и методы решения любой из них можно применять также и к другим задачам комбинаторной оптимизации. Поэтому нам в этой лекции достаточно сосредоточиться на одной такой задаче. Исторически наиболее исследованной и популярной задачей такого рода (своего рода "мушкой дрозофилой" комбинаторной оптимизации), которая используется для сравнения различных алгоритмов, стала задача коммивояжера.
В классической постановке, коммивояжер должен объехать
городов по замкнутому маршруту, посетив каждый из них лишь однажды, таким образом, чтобы полная длина его маршрута была минимальной. Если решать задачу коммивояжера "в лоб" - перебором всех замкнутых путей, связывающих
городов, то придется проверить все
возможных маршрутов. Будучи
-полной, задача коммивояжера не имеет практически реализуемого точного решения. На примере этой задачи мы ниже и рассмотрим различные методы ее приближенного решения с помощью нейросетей.
Содержание раздела
