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

1. если Буквы
ЗНАЧЕНИЮ ЯЧЕЙКИ НАвЕРХУ СЛЕВА +1

а псевдокоде эта формула реализуется так:
if word_a[i] == word_b[j]: •* Буквы совпадают
cell [ i ] [ j ] = cell[i-l][j-l] + 1 < Буквы не совпадают
else:
cell[i][j] = 0
Аналогичная таблица для строк hish и vista:

	1	S	т	А
о	0	О	О	О
о	1	о	о	О
о	0	2	о	о
°	О	О	О	О

ЦI
5

И
ТЕЛЬНЫЙ ^ИЕ(Ж0НЧ*- ТЕЛЬНЫЙ
°^Т6ЕТ ОТвЕТ
Важный момент: в этой задаче окончательное решение далеко не всегда на­ходится в последней ячейке! В задаче о рюкзаке последняя ячейка всегда содержит окончательное решение. Но в задаче поиска самой длинной общей подстроки решение определяется самым большим числом в таблице — и это может быть не последняя, а какая-то другая ячейка.
Вернемся к исходному вопросу: какая строка ближе к hish? У строк hish и fish есть общая подстрока длиной в три буквы. У hish и vista есть общая подстрока из двух букв. Скорее всего, Алекс хотел ввести строку fish.
Самая длинная общая подпоследовательность
Предположим, Алекс ввел строку fosh. Какое слово он имел в виду: fish или fort?
Сравним строки по формуле самой длинной общей подстроки.

	F	О	5	н
F	1	О	О	о
ИЛИ '	о	о	О	о
S	о	о	1	О
и	О	о	о	2

Д

	F	О	$	И
Г	1	О	О	о
о	о	2	о	о
R	о	о	о	о
T	о	о	о	о

лина подстрок одинакова: две буквы! Но fosh при этом ближе к fish:
FOSH
l 4 =
FISH
POSH 4- i
F О R T
Мы сравниваем самую длинную общую подстроку, а на самом деле нужно сравнивать самую длинную общую подпоследовательность: количество букв в последовательности, общих для двух слов. Как вычислить самую длинную общую подпоследовательность?
Н
иже приведена частично заполненная таблица для fish и fosh.
Сможете ли вы определить формулу для этой таблицы? Самая длинная общая подпоследовательность имеет много общего с самой длинной общей подстрокой, и их формулы тоже очень похожи. Попробуйте решить задачу самостоятельно, а я приведу ответ ниже.
Самая длинная общая подпоследовательность — решение
О

1.	* 1 -	и_	И
^А|	*2.-	>2-	а
'*’1	^J2-		>2
-*— 1	г	*Z~	11

САМАЯ ДЛИННАЯ ОБЩАЯ ПОДПОСЛЕДОВА­ТЕЛЬНОСТЬ - г

4S

1 -	9 1 "	I» 1 .	И
п*:	1 -	♦ 1 -	и
	* 1	*2"	*2
I '	ч	*2	tl

САМАЯ ДЛИННАЯ ОБЩАЯ ПОДПОСЛЕДОВА­ТЕЛЬНОСТЬ *■ 3




F О S Н F О
R
т


F О Ь И F I
5 И

кончательная версия таблицы:
А
для СОСЕДЕЙ НА6ЕРЛУ И СЛЕ6А


1. ЕСЛИ БУКВЫ НЕ СОВПАДАЮТ, ВЫБРАТЬ БОЛЬШЕЕ


(ОТЛИЧАЕТСЯ ОТ САМОЙ ДЛИННОЙ ОБЩЕЙ ПОДСТРОКИ)


г. ЕСЛИ БУКВЫ СОВПАДАЮТ, ЗНАЧЕНИЕ РАВНО ЗНАЧЕНИЮ ЯЧЕЙКИ НАВЕРХУ СЛЕВА +1 (КАК И 6 СЛУЧАЕ С САМОЙ ДЛИННОЙ ОБЩЕЙ ПОДСТРОКОЙ)


теперь моя формула для заполнения каждой ячейки:
На псевдокоде эта формула реализуется так:
c
if word_a[i] == word_b[j]: ■* Буквы совпадают
cell[i][j] = cell[l-l][j-l] + 1 else: < Буквы не совпадают

ell[i][j] = m a x(cell[i-l][j], cell[i][j-l])
Поздравляю — вы справились! Безусловно, это была одна из самых слож­ных глав в книге. Находит ли динамическое программирование практиче­ское применение? Да, находит.
□ Биологи используют самую длинную общую подпоследовательность для выявления сходства в цепях ДНК. По этой метрике можно судить о сходстве двух видов животных, двух заболеваний и т. д. Самая длинная общая подпоследовательность используется для поиска лекарства от рассеянного склероза.

• 
  Вы когда-нибудь пользовались ключом diff (например, в команде git diff)? Этот ключ выводит информацию о различиях между двумя фай­лами, а для этого он использует динамическое программирование.
  
• 
  Мы также упоминали о сходстве строк. Расстояние Левенштейна оцени­вает, насколько похожи две строки, а для его вычисления применяется динамическое программирование. Расстояние Левенштейна использу­ется в самых разных областях, от проверки орфографии до выявления отправки пользователем данных, защищенных авторским правом.
  
• 
  Вы когда-нибудь работали в приложении, поддерживающем перенос слов, например Microsoft Word? Как определить, где следует расставить переносы, чтобы длина строки оставалась более или менее постоянной? Динамическое программирование!
  

Упражнения

2. 
   Нарисуйте и заполните таблицу для вычисления самой длинной об­щей подстроки между строками blue и clues.
   

Шпаргалка

• 
  Динамическое программирование применяется при оптимизации не­которой характеристики.
  
• 
  Динамическое программирование работает только в ситуациях, в кото­рых задача может быть разбита на автономные подзадачи.
  
• 
  В каждом решении из области динамического программирования стро­ится таблица.
  
• 
  Значения ячеек таблицы обычно соответствуют оптимизируемой харак­теристике.
  
• 
  Каждая ячейка представляет подзадачу, поэтому вы должны подумать о том, как разбить задачу на подзадачи.
  
• 
  Не существует единой формулы для вычисления решений методом ди­намического программирования.
  

Алгоритм к ближайших соседей

• 
  В
  В этой главе
  
  ы научитесь строить системы классификации на базе алгоритма к ближайших соседей.
  
• 
  Вы узнаете об извлечении признаков.
  
• 
  Вы узнаете о регрессии: прогнозировании чисел (на­пример, завтрашних биржевых котировок или успеха фильма у зрителей).
  
• 
  Вы познакомитесь с типичными сценариями исполь­зования и ограничениями алгоритма к ближайших со­седей.
  

Апельсины и грейпфруты
В
згляните на этот фрукт. Что это, апельсин или грейпфрут? Я слышал, что грейпфруты обычно крупнее, а их кожура имеет красно­ватый оттенок.
М