Ниже приведена частично заполненная таблица для fish и fosh.
Сможете ли вы определить формулу для этой таблицы? Самая длинная общая подпоследовательность имеет много общего с самой длинной общей подстрокой, и их формулы тоже очень похожи. Попробуйте решить задачу самостоятельно, а я приведу ответ ниже.
Самая длинная общая подпоследовательность — решение
Окончательная версия таблицы:
А теперь моя формула для заполнения каждой ячейки:
На псевдокоде эта формула реализуется так:
if word_a[i] == word_b[j]: 
Буквы совпадают
cell[i][j] = cell[i-1][j-1] + 1 
Буквы не совпадают
else:
cell[i][j] = m a x(cell[i-1][j], cell[i][j-1])
Поздравляю — вы справились! Безусловно, это была одна из самых сложных глав в книге. Находит ли динамическое программирование практическое применение? Да, находит.
• Биологи используют самую длинную общую подпоследовательность для выявления сходства в цепях ДНК. По этой метрике можно судить о сходстве двух видов животных, двух заболеваний и т.д. Самая длинная общая подпоследовательность используется для поиска лекарства от рассеянного склероза.
• Вы когда-нибудь пользовались ключом diff (например, в команде git diff)? Этот ключ выводит информацию о различиях между двумя файлами, а для этого он использует динамическое программирование.
• Мы также упоминали о сходстве строк. Расстояние Левенштейна оценивает, насколько похожи две строки, а для его вычисления применяется динамическое программирование. Расстояние Левенштейна используется в самых разных областях, от проверки орфографии до выявления отправки пользователем данных, защищенных авторским правом.
• Вы когда-нибудь работали в приложении, поддерживающем перенос слов, например Microsoft Word? Как определить, где следует расставить переносы, чтобы длина строки оставалась более или менее постоянной? Динамическое программирование!
Упражнения
9.3 Нарисуйте и заполните таблицу для вычисления самой длинной общей подстроки между строками blue и clues.
Шпаргалка
• Динамическое программирование применяется при оптимизации некоторой характеристики.
• Динамическое программирование работает только в ситуациях, в которых задача может быть разбита на автономные подзадачи.
• В каждом решении из области динамического программирования строится таблица.
• Значения ячеек таблицы обычно соответствуют оптимизируемой характеристике.
• Каждая ячейка представляет подзадачу, поэтому вы должны подумать о том, как разбить задачу на подзадачи.
• Не существует единой формулы для вычисления решений методом динамического программирования.
10. Алгоритм k ближайших соседей
В этой главе
• Вы научитесь строить системы классификации на базе алгоритма k ближайших соседей.
• Вы узнаете об извлечении признаков.
• Вы узнаете о регрессии: прогнозировании чисел (например, завтрашних биржевых котировок или успеха фильма у зрителей).
• Вы познакомитесь с типичными сценариями использования и ограничениями алгоритма k ближайших соседей.
Апельсины и грейпфруты
Взгляните на этот фрукт. Что это, апельсин или грейпфрут? Я слышал, что грейпфруты обычно крупнее, а их кожура имеет красноватый оттенок.
Мой мыслительный процесс выглядит примерно так: у меня в мозге существует некое подобие графика.
Как правило, крупные и красные фрукты оказываются грейпфрутами. Этот фрукт большой и красный, поэтому, скорее всего, это грейпфрут. Но что, если вам попадется фрукт вроде такого?
Как классифицировать этот фрукт? Один из способов — рассмотреть соседей этой точки. Возьмем ее трех ближайших соседей.
Среди соседей больше апельсинов, чем грейпфрутов. Следовательно, этот фрукт, скорее всего, является апельсином. Поздравляем: вы только что применили алгоритм k ближайших соседей для классификации! В целом алгоритм работает по довольно простому принципу.