Я прошел самую длинную общую проблему подпоследовательности в ВВЕДЕНИЕ В АЛГОРИТМЫ по CLRS. Но я не смог понять задумчивый процесс за ней. Большинство других проблем было довольно интуитивно понятным и я уверен, что в будущем я смогу решить подобные проблемы, но я не могу визуализировать проблему LCS, поскольку не понимаю логики определения оптимальной структуры.Самый длинный алгоритм общей подпоследовательности
книга дает следующее объяснение оптимальной структуры к югу
** Теорема 15,1 (Optimal каркасного ЛВП)
Пусть X == и Y == быть последовательности, и пусть Z = быть любым LCS X и Y. 1. Если xm = yn, то zk = xm = yn и Zk−1 - это LCS Xm−1 и Yn−1. 2. Если xm != yn, то zk = xm подразумевает, что Z - это LCS Xm−1 и Y. 3. Если xm != yn, то zk = yn подразумевает, что Z является LCS X и Yn−1. Доказательства (1) Если zk != xm, то можно было бы добавить к xm = ynZ, чтобы получить общую подпоследовательности X и Y длины k + 1, что противоречит предположению о том, что это Z самого длинный общей подпоследовательность X и Y. Таким образом, мы должны иметь zk = xm = yn.
Теперь, предварительно фи х Zk−1 является length-(k − 1) общая подпоследовательность Xm−1 и Yn−1. Мы хотим показать, что это LCS. Предположим, что в целях противоречия существует общая подпоследовательность W от Xm−1 и Yn−1 с длиной больше k−1. Затем добавление xm = yn к W создает общую подпоследовательность X и Y , длина которой больше k, что является противоречием.
(2) Если zk != xm, то Z является общей подпоследовательностью Xm−1 и Y. Если бы не было общей подпоследовательности W из Xm−1 и Y с длиной больше k, то W бы также общая подпоследовательность Xm и Y, что противоречит предположению, что Z является ЛВП из X и Y.
(3) Доказательство симметрична (2). **
Доказательство очевидно, но я не могу видеть, как они пришли с оптимальной подструктуры. Может кто-нибудь помочь?