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

         

то станет ясным, что полный


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

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

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

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

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

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

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




Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий