Показ правильного алгоритма

Question

Предположим, у нас есть n продавцов и покупателей, отсортированных в порядке возрастания. Мы говорим, что продавец s и покупатель b «соответствуют», если s < b. Найдите максимальное подмножество A, состоящее из пар пар (точно один покупатель и продавец могут быть сопоставлены).

Мой алгоритм жадный и работает, выбирая первого продавца s1 и находив первого покупателя b1 в позиции c таким образом, чтобы s1 < b1 и добавив это к A. Затем мы переходим ко второму продавцу s2 и итерации с c + 1 в покупателях, пока мы не найдем покупателя b2, такого, что s2 < b2. Мы делаем это до тех пор, пока позиция c не будет равна размеру списка покупателей.

У меня просто возникают проблемы с доказательством правильности алгоритма. Я не уверен, как формализовать метод, чтобы было легко увидеть, что оптимальное решение всегда найдено. Когда я думаю об этом, это имеет смысл, но опять же формальная проверка - это то, с чем я столкнулся.

Answer 1

«Формальное» доказательство - своеобразное смутное описание. Я нарисую доказательство примерно до уровня детализации, который будет отображаться в исследовательском документе (который может быть меньше уровня детализации, необходимого для задачи, заданной в курсе алгоритмов).

Жадный алгоритм явно дает правильное соответствие. (В результате трудностей формальных методов на практике это действительно злоупотребление словом «ясно».)

Чтобы показать, что это соответствие имеет максимальный размер, мы доказываем следующее техническое заявление по индукции. Для всех k, не превышающих этот размер, существует максимальное совпадение, когда k наименьших продавцов сопоставляется как в жадном сопоставлении.

Базовый случай равен k = 0. Мы можем взять любое старое максимальное совпадение, так как оператор является свободным (0 наименьшее - пустое множество).

Индуктивный шаг для k> 0, чтобы доказать, что из утверждения для k - 1 следует утверждение для k. Существует максимальное совпадение M, которое согласуется с жадным решением на k - 1 наименее продаваемых, но, возможно, не на самом деле к-ю, которое мы будем называть 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, но не в жадном решении. Тогда жадное решение является подмножеством М. Это невозможно, потому что покупатель sk в M доступен в жадном решении (жадное решение максимально).

Случай 3: sk не сопоставляется в M. Некоторый более крупный продавец сопоставляется; замените его на sk и примените один из других случаев.