«Формальное» доказательство — это своего рода расплывчатое описание. Я набросаю доказательство примерно с уровнем детализации, который можно было бы увидеть в исследовательской статье (который может быть ниже уровня детализации, необходимого для набора задач в курсе алгоритмов).
Жадный алгоритм явно производит действительное сопоставление. (Из-за трудностей формальных методов на практике это действительно злоупотребление словом «ясно».)
Чтобы показать, что это паросочетание имеет максимальный размер, мы докажем по индукции следующее техническое утверждение. Для всех k, не превышающих этот размер, существует максимальное паросочетание, при котором сопоставляются k наименьших продавцов, как в жадном паросочетании.
Базовый случай: k = 0. Мы можем взять любое старое максимальное паросочетание, так как утверждение бессодержательно истинно (наименьшее 0 — это пустое множество).
Шаг индукции состоит в том, чтобы для k > 0 доказать, что утверждение для k - 1 влечет за собой утверждение для k. Существует максимальное паросочетание M, которое согласуется с жадным решением для k - 1 наименьшего количества продавцов, но, возможно, не для k-го наименьшего, которое мы будем называть sk. Теперь дело за аргументом.
Случай 1: sk совпадает в M и в жадном решении. Пусть bG будет покупателем sk в жадном решении, а bM будет покупателем sk в M. Если bG = bM, то дело сделано. В противном случае bG ‹ bM, потому что жадное решение выбрало минимально подходящего покупателя среди всех покупателей, исключая только покупателей для s1, ..., sk-1 (которые сопоставляются таким же образом в M). Если bG доступен в M, то переключите покупателя sk на bG. В противном случае поменяйте bG на bM в M; продавец, ранее покупавший у bG, получает более крупного покупателя, поэтому своп действителен.
Случай 2: sk соответствует M, но не соответствует жадному решению. Тогда жадное решение является подмножеством M. Это невозможно, потому что покупатель sk в M доступен в жадном решении (жадное решение максимально).
Случай 3: sk не соответствует M. Соответствует какой-то более крупный продавец; замените его на sk и примените один из других случаев.
person
David Eisenstat
schedule
05.10.2014
