Поиск хорошего соседа
Для каждого узла 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
Еще по теме Поиск хорошего соседа:
- Чтобы хорошо говорить, учитесь хорошо писать
- Поиск смысла жизни – это поиск бессмертия!
- То, что хорошо для одного, не всегда хорошо для другого.
- ХОРОШИЕ ИГРЫ
- ХОРОШИЕ ИГРЫ
- Я ХОРОШИЙ Я ЛЮБИМЫЙ
- ПОИСК ИНФОРМАЦИОННЫЙ
- Хорошо
- Оранжевый: "Хорошо!"
- Оранжевый: "Хорошо!"
- 3.11.6. Поиск на ощупь
- Хорошая и практичная теория
- «Все хорошо».
- Направление поиска работы
- Направление поиска работы
- Направление поиска работы