Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - Адитья Бхаргава

Вернемся к исходному вопросу: какая строка ближе к hish? У строк hish и fish есть общая подстрока длиной в три буквы. У hish и vista есть общая подстрока из двух букв. Скорее всего, Алекс хотел ввести строку fish.

Самая длинная общая подпоследовательность

Предположим, Алекс ввел строку fosh. Какое слово он имел в виду: fish или fort?

Сравним строки по формуле самой длинной общей подстроки.

Длина подстрок одинакова: две буквы! Но fosh при этом ближе к fish:

Мы сравниваем самую длинную общую подстроку, а на самом деле нужно сравнивать самую длинную общую подпоследовательность: количество букв в последовательности, общих для двух слов. Как вычислить самую длинную общую подпоследовательность?

Ниже приведена частично заполненная таблица для 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 ближайших соседей для классификации! В целом алгоритм работает по довольно простому принципу.

Алгоритм k ближайших соседей прост, но полезен! Если вы пытаетесь выполнить классификацию чего-либо, сначала попробуйте применить алгоритм k ближайших соседей. Рассмотрим более реалистичный пример.

Построение рекомендательной системы

Представьте, что вы работаете на сайте Netflix и хотите построить систему, которая будет рекомендовать фильмы для ваших пользователей. На высоком уровне эта задача похожа на задачу с грейпфрутами!

Информация о каждом пользователе наносится на график.

Положение пользователя определяется его вкусами, поэтому пользователи с похожими вкусами располагаются недалеко друг от друга. Предположим, вы хотите порекомендовать фильмы Приянке. Найдите пять пользователей, ближайших к ней.

У Джастина, Джей-Си, Джозефа, Ланса и Криса похожие вкусы. Значит, те фильмы, которые