Основы теории нейронных сетей


         

Задача коммивояжера - часть 2


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

городПорядок следования
1234
A0100
B0001
C1000
D0010

Продемонстрируем теперь, как сконструировать сеть для решения этой NP-полной проблемы. Каждый нейрон снабжен двумя индексами, которые соответствуют городу и порядковому номеру его посещения в маршруте. Например,

показывает, что город
был
-м по порядку городом маршрута.

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

Первое требование удовлетворяется введением следующей, состоящей из трех сумм, функции энергии:

где

,
и
— некоторые константы. Этим достигается выполнение следующих условий:

  1. Первая тройная сумма равна нулю в том и только в том случае, если каждая строка (город) содержит не более одной единицы.
  2. Вторая тройная сумма равна нулю в том и только в том случае, если каждый столбец (порядковый номер посещения) содержит не более одной единицы.
  3. Третья сумма равна нулю в том и только в том случае, если матрица содержит ровно

    единиц. Второе требование — предпочтение коротких маршрутов — удовлетворяется с помощью добавления следующего члена к функции энергии:

Заметим, что этот член представляет собой длину любого допустимого маршрута. Для удобства индексы определяются по модулю

, т. е.
, a
— некоторая константа.

При достаточно больших значениях

,
и

низкоэнергетические состояния будут представлять допустимые маршруты, а большие значения

гарантируют, что будет найден короткий маршрут.

Теперь зададим значения весов, т. е. установим соответствие между членами в функции энергии и членами общей формы (см. уравнение 6.2).

Получаем

(не допускает более одной единицы в строке)

(не допускает более одной единицы в столбце)

(глобальное ограничение)




Содержание  Назад  Вперед