<<
>>

Разработка алгоритма

Алгоритм, который будет разработан в этом разделе, доказывает следующий ре- зультат.

(12.3) У каждой сети Хопфилда имеется устойчивая конфигурация, которая может быть найдена за время, полиномиальное по n и W= ∑ J⅝|.

Вы увидите, что устойчивые конфигурации крайне естественно встречаются в качестве локальных оптимумов определенных процедур локального поиска в сетях Хопфилда. Чтобы убедиться в том, что утверждение (12.3) не так уж тривиально, стоит заметить, что оно перестает быть истинным при некоторых естественных модификациях модели. Например, представьте, что мы определяем направленную сеть Хопфилда точно так, как описано выше, но с одним исключе- нием — каждое ребро является направленным, а каждый узел определяет, являет- ся он реализованным или нет, проверяя только те ребра, для которых он является начальным. В этом случае сеть может и не иметь устойчивой конфигурации. Для примера возьмем направленную версию сети из трех узлов, упоминавшуюся ра- нее: имеются три узла a, b, с, соединенные направленными ребрами (a, b), (b, с), (с, a), все ребра имеют вес 1. Если все узлы находятся в одном состоянии, все они будут нереализованными; а если состояние одного узла отличается от состояния двух других, то узел, находящийся непосредственно перед ним, будет нереализо- ванным. Следовательно, в этой направленной сети не существует конфигурации, в которой все узлы были бы реализованы.

Очевидно, доказательство (12.3) должно где-то зависеть от ненаправленной природы сети.

Чтобы доказать (12.3), мы проанализируем простую итеративную процедуру поиска устойчивой конфигурации, которую назовем алгоритмом переключения состояния.

Пока текущая конфигурация не является устойчивой Должен существовать нереализованный узел Выбрать нереализованный узел и Переключить состояние и Конец Пока

Пример выполнения алгоритма, приводящий к устойчивой конфигурации, изображен на рис. 12.4.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Разработка алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  12. Разработка Плана
  13. 2.7. Разработка анкеты
  14. 6. Разработка перспектив
  15. Разработка и принятие Основного закона
  16. Состояние научной разработки проблемы.
  17. Правило разработки веера версий
  18. Правило разработки графических схем
  19. Правило разработки графических схем