<<
>>

Поиск хорошего соседа

Чтобы найти лучшего соседа, мы проверяем каждую метку по отдельности. Начнем с метки а. Утверждается, что лучшее переназначение, в котором узлы могут изме- нить свои метки на a, может быть найдено посредством вычисления минимального разреза.
Построение графа минимального разреза G' = (V', E') аналогично вычисле- нию минимального разреза, разработанному для бинарной сегментации изображе- ний. Тогда мы определили источник 5 и сток t для представления двух меток. Здесь мы тоже введем источник и сток, но источник 5 будет представлять метку а, а сток t будет фактически представлять другой вариант, имеющийся у узлов, а именно со- хранение их исходных меток. Идея заключается в том, чтобы найти минимальный разрез в G' и заменить метки всех узлов на стороне 5 разреза меткой а, тогда как все узлы на стороне t сохранят свои исходные метки.

Для каждого узла G в новом множестве V' имеется соответствующий узел, а в E' добавляются ребра (i, t) и (5, i), как это делалось на рис. 7.18 из главы 7 в случае двух меток.

Ребро (i, t) имеет пропускную способность c(а), так как разрезание ребра (i, t) приводит к размещению узла i на стороне источника, а следовательно, соответствует пометке узла i меткой а. Ребро (i, 5) будет иметь пропускную спо- собность c (f (i)), если f (i) Ф а, или она будет выражаться очень большим числом M (или +∞), если f (i) = а. Разрезание ребра (i, t) помещает узел i на сторону стока, а следовательно, соответствует сохранению узлом i исходной метки f (i) Ф а. Боль- шая пропускная способность M предотвращает размещение узлов i с f (i) = а на стороне стока.

В построении для задачи с двумя метками мы добавляли ребра между узлами V и использовали штрафы за разделение как пропускные способности. Этот способ хорошо работает для узлов, разделенных разрезом, или узлов на стороне источника, одновременно имеющих метку а.

Но если i и j находятся на стороне стока, то со- единяющее их ребро еще не разрезано, но i и j разделены, если f(i) Ф f(j). Чтобы ре- шить эту проблему, мы дополним построение G' следующим образом. Для ребра (i, j), если f(i) = f(j) или один из узлов i или j имеет метку а, в E' добавляется ребро (i, j) с пропускной способностью Рj. Для ребер e = (i, j), у которых f(i) Ф f (j) и ни один узел не имеет метку а, чтобы правильно закодировать через граф G', что i и j остаются разделенными, даже если находятся на стороне стока, придется действо- вать иначе. Для каждого такого ребра e в V' добавляется дополнительный узел e, соответствующий ребру e, и ребра (i, e), (e, j) и (e, s) с пропускной способностью p Эти ребра изображены на рис. 12.7.

Рис. 12.7. Построение для ребра e = (i, j) с а Ф f (i) Ф f (j) Ф а

(12.9) Для заданной разметки f и метки а минимальный разрез в графе G' = (¥', E') соответствует соседу разметки f с минимальным штрафом, полученно- му заменой меток подмножества узлов на а. В результате сосед f с минимальным штрафом может быть найден посредством к вычислений минимального разреза, по одному для каждой метки в L.

Доказательство. Пусть (A, B) — разрез s-t в G'. Большое значение M гарантирует, что разрез с минимальной пропускной способностью не разрежет никакие из этих ребер с высокой пропускной способностью. Теперь рассмотрим узел e в G', соот- ветствующий ребру e = (i, j) E. Узел e V' имеет три прилегающих ребра, каждое из которых имеет пропускную способность p... Для любого разбиения остальных узлов e можно разместить так, что разрезано будет не более одного из этих трех ребер. Назовем разрез хорошим, если никакое ребро с пропускной способностьюM не разрезается и для всех узлов, соответствующих ребрам в E, разрезается не более одного из прилегающих ребер. К настоящему моменту мы обосновали, что все раз- резы с минимальной пропускной способностью являются хорошими.

Хорошие разрезы s-t в G' находятся в однозначном соответствии с перена- значениями метокf полученными заменой метки подмножества узлов на а. Рас- смотрим пропускную способность хорошего разреза. Ребра (s, i) и (i, t) добавляют в пропускную способность разреза в точности штраф за назначение. Ребра (i, j), напрямую соединяющие узлы в V, вносят в точности штраф за разделение узлов в соответствующей разметке: р.., если они разделены, и 0 в противном случае. На- конец, рассмотрим ребро e = (i, j) с соответствующим узлом e

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

Еще по теме Поиск хорошего соседа:

  1. Чтобы хорошо говорить, учитесь хорошо писать
  2. Поиск смысла жизни – это поиск бессмертия!
  3. То, что хорошо для одного, не всегда хорошо для другого.
  4. ХОРОШИЕ ИГРЫ
  5. ХОРОШИЕ ИГРЫ
  6. Я ХОРОШИЙ Я ЛЮБИМЫЙ
  7. ПОИСК ИНФОРМАЦИОННЫЙ
  8. Хорошо
  9. Оранжевый: "Хорошо!"
  10. Оранжевый: "Хорошо!"
  11. 3.11.6. Поиск на ощупь
  12. Хорошая и практичная теория
  13. «Все хорошо».
  14. Направление поиска работы
  15. Направление поиска работы
  16. Направление поиска работы