Поиск хорошего соседа
Чтобы найти лучшего соседа, мы проверяем каждую метку по отдельности. Начнем с метки a. Утверждается, что лучшее переназначение, в котором узлы могут изменить свои метки на a, может быть найдено посредством вычисления минимального разреза.
Построение графа минимального разреза G’ = (V’, E’) аналогично вычислению минимального разреза, разработанному для бинарной сегментации изображений.
Идея заключается в том, чтобы найти минимальный разрез в G’ и заменить метки всех узлов на стороне s разреза меткой a, тогда как все узлы на стороне t сохранят свои исходные метки.
Ребро (i, s) будет иметь пропускную способность ci( f (i)), если f (i) ≠ a, или она будет выражаться очень большим числом M (или +∞), если f (i) = a. Разрезание ребра (i, t) помещает узел i на сторону стока, а следовательно, соответствует сохранению узлом i исходной метки f (i) ≠ a. Большая пропускная способность M предотвращает размещение узлов i с f (i) = a на стороне стока.
В построении для задачи с двумя метками мы добавляли ребра между узлами V и использовали штрафы за разделение как пропускные способности. Этот способ хорошо работает для узлов, разделенных разрезом, или узлов на стороне источника, одновременно имеющих метку a.
Но если i и j находятся на стороне стока, то соединяющее их ребро еще не разрезано, но i и j разделены, если f (i) ≠ f ( j).
Чтобы решить эту проблему, мы дополним построение G’ следующим образом. Для ребра (i, j), если f (i) = f ( j) или один из узлов i или j имеет метку a, в E’ добавляется ребро (i, j) с пропускной способностью pij.
Для ребер e = (i, j), у которых f (i) ≠ f ( j) и ни один узел не имеет метку a, чтобы правильно закодировать через граф G’, что i и j остаются разделенными, даже если находятся на стороне стока, придется действовать иначе.
Для каждого такого ребра e в V’ добавляется дополнительный узел e, соответствующий ребру e, и ребра (i, e), (e, j) и (e, s) с пропускной способностью pij. Эти ребра изображены на рис. 12.7.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу