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

Упражнения

9.2 Предположим, что вы собираетесь в турпоход. Емкость вашего рюкзака составляет 6 фунтов, и вы можете взять предметы из следующего списка. У каждого предмета имеется стоимость; чем она выше, тем важнее предмет:

• вода, 3 фунта, 10;

• книга, 1 фунт, 3;

• еда, 2 фунта, 9;

• куртка, 2 фунта, 5;

• камера, 1 фунт, 6

Как выглядит оптимальный набор предметов для похода?

Самая длинная общая подстрока

Мы рассмотрели одну задачу динамического программирования. Какие выводы из нее можно сделать?

• Динамическое программирование применяется для оптимизации какой-либо характеристики при заданных ограничениях. В задаче о рюкзаке требуется максимизировать стоимость отобранных предметов с ограничениями по емкости рюкзака.

• Динамическое программирование работает только в ситуациях, в которых задача может быть разбита на автономные подзадачи, не зависящие друг от друга.

Построить решение на базе динамического программирования бывает непросто. В этом разделе мы сосредоточимся на этой теме. Несколько общих рекомендаций:

• в каждом решении из области динамического программирования строится таблица;

• значения ячеек таблицы обычно соответствуют оптимизируемой характеристике. Для задачи о рюкзаке значения представляли общую стоимость товаров;

• каждая ячейка представляет подзадачу, поэтому вы должны подумать о том, как разбить задачу на подзадачи. Это поможет вам определиться с осями.

Рассмотрим еще один пример. Допустим, вы открыли сайт dictionary.com. Пользователь вводит слово, а сайт возвращает определение. Но если пользователь ввел несуществующее слово, нужно предположить, какое слово имелось в виду. Алекс ищет определение «fish», но он случайно ввел «hish». Такого слова в словаре нет, но зато у вас есть список похожих слов.

(Это несерьезный пример, поэтому список ограничен всего двумя словами. Вероятно, на практике такой список будет состоять из тысяч слов.)

Итак, Алекс ввел строку hish. Какое слово он хотел ввести на самом деле: fish или vista?

Построение таблицы

Как должна выглядеть таблица для этой задачи? Вы должны ответить на следующие вопросы.

• Какие значения должны содержаться в ячейках?

• Как разбить эту задачу на подзадачи?

• Каков смысл осей таблицы?

В динамическом программировании вы пытаетесь максимизировать некоторую характеристику. В данном случае ищется самая длинная подстрока, общая в двух словах. Какую общую подстроку содержат hish и fish? А как насчет hish и vista? Именно это требуется вычислить.

Как говорилось ранее, значения в ячейках обычно представляют ту характеристику, которую вы пытаетесь оптимизировать. Вероятно, в данном случае этой характеристикой будет число: длина самой длинной подстроки, общей для двух строк.

Как разделить эту задачу на подзадачи? Например, можно заняться сравнением подстрок. Вместо того чтобы сравнивать hish и fish, можно сначала сравнить his и fis. Каждая ячейка будет содержать длину самой длинной подстроки, общей для двух подстрок. Такое решение также подсказывает, что строками и столбцами таблицы, вероятно, будут два слова. А значит, таблица будет выглядеть примерно так:

Если у вас голова идет кругом, не огорчайтесь. Это сложный материал — собственно, именно поэтому я объясняю его в конце книги! Ниже будет приведено упражнение, чтобы вы могли самостоятельно потренироваться в динамическом программировании.

Заполнение таблицы

Сейчас вы уже достаточно хорошо представляете, как должна выглядеть таблица. По какой формуле заполняются ячейки таблицы? Мы можем немного упростить свою задачу, потому что уже знаем решение — у hish и fish имеется общая подстрока длины 3: ish.

Однако этот факт ничего не говорит о том, какая формула должна использоваться. Программисты иногда шутят об использовании алгоритма Фейнмана. Алгоритм Фейнмана, названный по имени известного физика Ричарда Фейнмана, работает так:

1. Записать формулировку задачи.

2. Хорошенько подумать.

3. Записать решение.

Да, программисты — большие шутники!

По правде говоря, простого способа вычислить формулу для данного случая не существует. Вам придется экспериментировать и искать работоспособное решение. Иногда алгоритм предоставляет не точный рецепт, а основу, на которую вы наращиваете свою идею.

Попробуйте предложить решение этой задачи самостоятельно. Даю подсказку — часть таблицы выглядит так:

Чему равны другие значения? Вспомните, что каждая ячейка содержит значение подзадачи. Почему ячейка (3, 3) содержит значение 2? Почему ячейка (3, 4) содержит значение 0?

Попытайтесь вывести формулу самостоятельно, прежде чем продолжить читать. Даже если вам не удастся получить правильный ответ, мои объяснения покажутся вам намного более понятными.

Решение

Итоговая версия таблицы выглядит так:

А это моя формула для заполнения ячеек:

На псевдокоде эта формула реализуется так:

if word_a[i] == word_b[j]:      Буквы совпадают

  cell[i][j] = cell[i-1][j-1] + 1      Буквы несовпадают

else:

  cell[i][j] = 0

Аналогичная таблица для строк hish и vista:

Важный момент: в этой задаче окончательное решение далеко не всегда находится в последней ячейке! В задаче о рюкзаке последняя ячейка всегда содержит окончательное решение. Но в задаче поиска самой длинной общей подстроки решение определяется самым большим числом в таблице — и это может быть не последняя, а какая-то другая ячейка.