<<
>>

Анализ алгоритма

Очевидно, если только что определенный нами алгоритм переключения состояния завершился, была достигнута устойчивая конфигурация. Впрочем, не так очевид- но то, что он действительно завершится.
В предыдущем примере с направленным графом этот процесс будет просто перебирать три узла, бесконечно переключая их состояния. Сейчас мы докажем, что алгоритм переключения состояния всегда завер- шается, и приведем границу для количества итераций, необходимых для завершения. Тем самым будет доказано утверждение (12.3). Ключом к доказательству того, что этот процесс завершается, служит идея, использованная в нескольких предыду- щих ситуациях: нужно найти метрику прогресса, то есть величину, которая строго увеличивается с каждым переключением состояния и имеет абсолютную верхнюю границу. Она может быть использована для ограничения количества итераций.

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

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

Рис.

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

(Состояние узлов обозначается черным или белым цветом)

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

Однако существует менее очевидная метрика прогресса, которая изменяется с каждым изменением состояния нереализованного узла. А именно: для заданной конфигурации S мы определяем Ф(S) как общий абсолютный вес всех хороших ребер в сети, то есть

ф(S)= ∑kl

(доJr

Очевидно, для любой конфигурации S выполняется Ф(5') > 0 (так как Ф(>S') — сумма положительных целых чисел) и Ф(S) < W = ∑.ы (так как в крайнем случае каждое ребро является хорошим).

Теперь предположим, что в неустойчивой конфигурации S мы выбираем узел u, который является нереализованным, и изменяем его состояние, получая конфи- гурацию S'. Что можно сказать об отношениях между Ф(S') и Ф(S)? Вспомним, что при переключении состояния и все хорошие ребра, инцидентные и, становятся плохими; все плохие ребра, инцидентные и, становятся хорошими; а все ребра, для которых и не является конечной точкой, остаются без изменений. Если обо- значить gu и bu общий абсолютный вес соответственно хороших и плохих ребер, инцидентных и, то имеем

Ф(S') = Ф(S) - gu + b

Но так как узел и был нереализованным в S, мы также знаем, что bu > gu; а по- скольку и bu, и gu являются целыми числами, имеем bu > gu + 1. Следовательно,

Ф(S') > Ф(S) + 1.

Значение Ф начинается с некоторого неотрицательного целого числа, увели- чивается на 1 с каждым изменением состояния и не может превысить W.

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

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

Затем мы изучили поведение простого итеративного алгоритма локального поиска («перевернутую» форму градиентного спуска, так как в данном случае ис- пользуется задача максимизации); при этом было обнаружено следующее:

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

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

В настоящее время простые обходные решения неизвестны. Вопрос о суще- ствовании алгоритма, строящего устойчивые состояния за время, полиномиальное по n и log W (вместо n и W), или с количеством примитивных арифметических операций, полиномиальным только по n (независимо от W), остается открытым.

12.4.

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

Еще по теме Анализ алгоритма:

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