Задачи о сравнении строк методами динамического программирования

ВВЕДЕНИЕ

Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953 г. он уточнил это определение до современного. Первоначально эта область была основана, как системный анализ и инжиниринг. Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования.

Слово «программирование» в словосочетании «динамическое программирование» в действительности к традиционному программированию (написанию кода) почти никакого отношения не имеет и происходит от словосочетания «математическое программирование», которое является синонимом слова «оптимизация». Программирование в данном случае понимается как допустимая последовательность событий.

Целью данной курсовой работы является решение задачи о сравнении строк методами динамического программирования.

Основными задачами данной курсовой работы является изучение основ динамического программирования (особенностей, алгоритмов решения задач), ознакомление с основным алгоритмом для практического решения задач; изучение технологии решения задач о замене оборудования и ее реализация для типовых задач.

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

В процессе работы будут выполнены следующие задачи:

• изучение алгоритма вычисления расстояния Левенштейна;
• оформление блок-схемы задачи;
• разработка консольного приложения на языке Си, реализующее необходимые вычисления.

Приложение представляет собой «Калькулятор расстояния Левенштейна», который будет полезен для пользователей, которым необходимо сравнить любые строки.

1 Аналитический обзор методов и средств разработки программного комплекса

1.1 Основы динамического программирования. Основное понятие

Динамическое программирование – раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные на вычислении последствий каждого решения и выработке оптимальной стратегии для последующих решений. Процессы принятия решений, которые строятся по такому принципу, называются многошаговыми процессами. Математически оптимизационная задача строится с помощью таких соотношений, которые последовательно связаны между собой: например, полученный результат для одного года вводится в уравнение для следующего (или, наоборот, для предыдущего) Таким образом, можно получить на вычислительной машине результаты решения задачи для любого избранного момента времени и «следовать» дальше. Динамическое программирование применяется не обязательно для задач, связанных с течением времени. Многошаговым может быть и процесс решения вполне статической задачи. Таковы, например, некоторые задачи распределения ресурсов.

Потребности практики вызвали к жизни специальные методы, которые удобно объединять под названием «исследование операций». Под этим термином понимается применение математических, количественных методов для обоснования решений во всех областях целенаправленной человеческой деятельности. Целью исследования операций является выявление наилучшего способа действия при решении той или иной задачи. Главная роль при этом отводится математическому моделированию. Для построения математической модели необходимо иметь строгое представление о цели функционирования исследуемой системы и располагать информацией об ограничениях, которые определяют область допустимых значений. Цель и ограничения должны быть представлены в виде функций.