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


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


Самые трудные задачи класса

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

Все

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

В классической постановке, коммивояжер должен объехать

N
городов по замкнутому маршруту, посетив каждый из них лишь однажды, таким образом, чтобы полная длина его маршрута была минимальной. Если решать задачу коммивояжера "в лоб" - перебором всех замкнутых путей, связывающих
N
городов, то придется проверить все
(N-1)!/2
возможных маршрутов. Будучи
NP
-полной, задача коммивояжера не имеет практически реализуемого точного решения. На примере этой задачи мы ниже и рассмотрим различные методы ее приближенного решения с помощью нейросетей.




Начало  Назад  Вперед



Книжный магазин