Доказательство самой длинной возрастающей подпоследовательности с использованием жадного терпения

Question

Я наткнулся на решение, которое использует сортировку Patience для получения длины самой длинной увеличивающейся подпоследовательности (LIS). http://www-stat.stanford.edu/~cgates/PERSI/papers/Longest.pdf, а здесь - http://en.wikipedia.org/wiki/Patience_sorting.

Доказательство того, что следование жадной стратегии дает нам правильную длину, состоит из 2 частей:

1. доказывает, что количество свай по крайней мере равно длине LIS.
2. доказывает, что количество куч, использующих жадную стратегию, максимально равно LIS.

Таким образом, в силу 1) и 2), решение дает длину LIS правильно.

Я получаю объяснение 1), но я просто не могу интуитивно понять часть 2). Может кто-то может использовать другой пример, чтобы убедить меня, что это действительно так. Или вы можете даже использовать другую технику доказательства тоже.

Answer 1

Я просто перечитал статью и согласен с тем, что доказательства немного кратковременны. (Я бы сказал, что здесь не хватает некоторых довольно важных шагов!)

Интуитивно понятно, что идея доказательства заключается в том, чтобы показать, что если вы играете с жадной стратегией и в конце игры выбираете любую карту в стопке с номером p, вы можете найти возрастающую подпоследовательность в исходном массиве, длина которого равна p. Если вы можете доказать этот факт, то можете сделать вывод, что максимальное количество куч, производимых жадной стратегией, - это длина самой длинной увеличивающейся подпоследовательности.

Чтобы формально доказать это, мы будем утверждать, что следующие два инварианта выполняются на каждом шаге:

1. Верхние карты в каждой стопке при чтении слева направо расположены в отсортированном порядке.

2. В любой момент времени каждая карта в каждой стопке является частью увеличивающейся подпоследовательности, длина которой определяется индексом стопки.

Часть (1) легко увидеть из жадной стратегии - каждый элемент размещен как можно дальше влево, не нарушая правила, согласно которому меньшие карты всегда должны быть помещены поверх больших карт. Это означает, что если карта помещается в стопку p, мы фактически берем отсортированную последовательность и уменьшаем значение элемента pth до значения, которое больше, чем то, что находится в позиции p - 1 (если оно существует).

Чтобы увидеть часть (2), мы пойдем индуктивно. Первая размещенная карта помещается в колоду 1, и она также является частью увеличивающейся подпоследовательности длины 1 (сама карта). Для индуктивного шага предположим, что это свойство сохраняется после размещения n карт, и рассмотрим (n+1) -й. Предположим, что это заканчивается в куче р. Если p = 1, то утверждение остается в силе, поскольку эта карта сама по себе образует возрастающую подпоследовательность длины 1. В противном случае, p > 1. Теперь посмотрите на карту сверху стопки p - 1. Мы знаем, что ценность этой карты меньше стоимости карты, которую мы только что положили, так как в противном случае мы поместили бы карту поверх этой карты. ворс. Мы также знаем, что карта в верхней части этой колоды предшествует карте, которую мы только что положили в исходном порядке, поскольку мы разыгрываем карты по порядку. Из нашего существующего инварианта мы знаем, что карта в верхней части стопки p - 1 является частью увеличивающейся подпоследовательности длины p - 1, так что подпоследовательность, с этой новой картой, добавленной в нее, образует возрастающую подпоследовательность длины p, так как требуется.