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


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


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

a^N
или еще скорее - как
N!
(напомним, что согласно известной формуле Стирлинга
N!\cong(N/e)^N
для достаточно больших
N
).

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

N. 1)

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

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

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

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




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



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