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

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

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

  1. доказывает, что количество свай по крайней мере равно длине ЛИС.
  2. доказывает, что количество стопок с использованием жадной стратегии не более равно LIS.

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

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


sorting algorithm greedy
person sachuraju    schedule 19.09.2013    source источник
comment
нежный отказов для кого-то, чтобы ответить.   -  person sachuraju    schedule 22.09.2013

Ответы (1)


arrow_upward
2
arrow_downward

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

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

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

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

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

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

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

person templatetypedef    schedule 27.08.2015