Нейрокомпьютинг и его применения в экономике и бизнесе

          

Комбинаторная оптимизация и задача коммивояжера


В задачах комбинаторной оптимизации требуется найти наилучшее из конечного, но обычно очень большого числа возможных решений. Если задача характеризуется характерным числом элементов (размерностью задачи), то типичное число возможных решений, из которых предстоит сделать выбор, растет экспоненциально - как

Комбинаторная оптимизация и задача коммивояжера
или еще скорее - как
Комбинаторная оптимизация и задача коммивояжера
(напомним, что согласно известной формуле Стирлинга
Комбинаторная оптимизация и задача коммивояжера
для достаточно больших
Комбинаторная оптимизация и задача коммивояжера
).

Это свойство делает простой метод перебора всех вариантов, в принципе гарантирующий решение при конечном числе альтернатив, чрезвычайно неэффективным, т.к. такое решение требует экспоненциально большого времени. Эффективными же признаются решения, гарантирующие получение ответа за полиномиальное время, растущее как полином с ростом размерности задачи, т.е. как

N. 1)

Различие между полиномиальными и экспоненциальными алгоритмами восходит к фон Нейману (von Neumann, 1953)

Задачи, допускающие гарантированное нахождение оптимума целевой функции за полиномиальное время, образуют класс

Комбинаторная оптимизация и задача коммивояжера
. Этот класс являюется подклассом более обширного класса
Комбинаторная оптимизация и задача коммивояжера
задач, в которых за полиномиальное время можно всего лишь оценить значение целевой функции для конкретной конфигурации, что, естественно, гораздо проще, чем выбрать наилучшую из всех конфигураций. До сих пор в точности не известно, совпадают ли эти два класса, или нет. Эта проблема,
Комбинаторная оптимизация и задача коммивояжера
, о которую сломано уже немало математических копий. Если бы эти классы совпадали, для любой задачи комбинаторной оптимизации, точное можно было бы гарантированно найти за полиномиальное время. В такой "подарок судьбы" никто не верит, и практически разрешимыми считаются задачи, допускающие полиномиальное решение хотя бы для типичных (а не наихудших) случаев. Такова, например, общая задача линейного программирования.

Для более трудных задач достаточно было бы и более слабого условия - нахождения субоптимальных решений, локальных минимумов целевой функции, не слишком сильно отличающихся от абсолютного минимума. Нейросетевые решения как раз и представляют собой параллельные алгоритмы, быстро находящие субоптимальные решения оптимизационных задач, минимизируя целевую функцию в процессе своего функционирования или обучения.


Самые трудные задачи класса
Комбинаторная оптимизация и задача коммивояжера
называют
Комбинаторная оптимизация и задача коммивояжера
-полными. Это название объясняется тем, что если бы удалось доказать, что существует полиномиальное решение такой задачи, то такое решение существовало бы и для любой другой задачи класса
Комбинаторная оптимизация и задача коммивояжера
, т.е. классы
Комбинаторная оптимизация и задача коммивояжера
и
Комбинаторная оптимизация и задача коммивояжера
совпадали бы. Поскольку, как уже говорилось, такой сценарий крайне маловероятен, именно для таких проблем наиболее важен поиск субоптимальных решений.

Все
Комбинаторная оптимизация и задача коммивояжера
-полные задачи одинаково сложны (поскольку все они сводятся друг к другу за полиномиальное время), и методы решения любой из них можно применять также и к другим задачам комбинаторной оптимизации. Поэтому нам в этой лекции достаточно сосредоточиться на одной такой задаче. Исторически наиболее исследованной и популярной задачей такого рода (своего рода "мушкой дрозофилой" комбинаторной оптимизации), которая используется для сравнения различных алгоритмов, стала задача коммивояжера.

В классической постановке, коммивояжер должен объехать
Комбинаторная оптимизация и задача коммивояжера
городов по замкнутому маршруту, посетив каждый из них лишь однажды, таким образом, чтобы полная длина его маршрута была минимальной. Если решать задачу коммивояжера "в лоб" - перебором всех замкнутых путей, связывающих
Комбинаторная оптимизация и задача коммивояжера
городов, то придется проверить все
Комбинаторная оптимизация и задача коммивояжера
возможных маршрутов. Будучи
Комбинаторная оптимизация и задача коммивояжера
-полной, задача коммивояжера не имеет практически реализуемого точного решения. На примере этой задачи мы ниже и рассмотрим различные методы ее приближенного решения с помощью нейросетей.



Самые трудные задачи класса
Комбинаторная оптимизация и задача коммивояжера
называют
Комбинаторная оптимизация и задача коммивояжера
-полными. Это название объясняется тем, что если бы удалось доказать, что существует полиномиальное решение такой задачи, то такое решение существовало бы и для любой другой задачи класса
Комбинаторная оптимизация и задача коммивояжера
, т.е. классы
Комбинаторная оптимизация и задача коммивояжера
и
Комбинаторная оптимизация и задача коммивояжера
совпадали бы. Поскольку, как уже говорилось, такой сценарий крайне маловероятен, именно для таких проблем наиболее важен поиск субоптимальных решений.

Все
Комбинаторная оптимизация и задача коммивояжера
-полные задачи одинаково сложны (поскольку все они сводятся друг к другу за полиномиальное время), и методы решения любой из них можно применять также и к другим задачам комбинаторной оптимизации. Поэтому нам в этой лекции достаточно сосредоточиться на одной такой задаче. Исторически наиболее исследованной и популярной задачей такого рода (своего рода "мушкой дрозофилой" комбинаторной оптимизации), которая используется для сравнения различных алгоритмов, стала задача коммивояжера.

В классической постановке, коммивояжер должен объехать
Комбинаторная оптимизация и задача коммивояжера
городов по замкнутому маршруту, посетив каждый из них лишь однажды, таким образом, чтобы полная длина его маршрута была минимальной. Если решать задачу коммивояжера "в лоб" - перебором всех замкнутых путей, связывающих
Комбинаторная оптимизация и задача коммивояжера
городов, то придется проверить все
Комбинаторная оптимизация и задача коммивояжера
возможных маршрутов. Будучи
Комбинаторная оптимизация и задача коммивояжера
-полной, задача коммивояжера не имеет практически реализуемого точного решения. На примере этой задачи мы ниже и рассмотрим различные методы ее приближенного решения с помощью нейросетей.


Содержание раздела