Анализ алгоритма
Вероятно, самой естественной метрикой прогресса могло бы стать количество реализованных узлов: если оно увеличивается при каждом переключении нереали- зованного узла, процесс будет выполняться не более 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 + bu·
Но так как узел и был нереализованным в 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.
Еще по теме Анализ алгоритма:
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Алгоритм исцеления:
- Алгоритм избавления от боли
- 2. Специфика и алгоритмы работы с источниками.
- Алгоритм обработки результатов.
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
- Принципы анализа происшествия.