Содержание
программирование алгоритм динамический задача
Введение
1. Теоретическая справка
2. Сведения о средствах языка программировани
3. Алгоритм Флойда-Уоршелла
4. Инструкция по установке
5. Инструкция пользователю
6. Программная реализация
7. Инструкция программисту
8. Тестирование
Заключение
Список использованной литературы
Приложения
Введение
В настоящее время существует множество алгоритмов решения динамических задач, которые применяются в зависимости от того какие условия функционирования стоят перед разрабатываемой программой.
В данном курсовом проекте необходимо, спроектировать программный комплекс решения задачи динамического программирования, при разработке программы обучиться навыкам объектно-ориентированного программирования на языке С++.
Требуется разработать пользовательский интерфейс, освоить основные объекты и их свойства. При оформлении курсового проекта изучить оформление прикладной документации согласно ГОСТу.
Научная значимость данной работы состоит в описании и исследовании наиболее наглядной задачи динамического программирования - алгоритма поиска кратчайшего пути. Практическая значимость темы «Решение задачи динамического программирования» состоит в анализе проблем реализации и использовании современного подхода к задачам динамического программирования.
1. Теоретическая справка
Динамическое программирование в теории управления и теории вычислительных систем -- способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.
Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.
Метод динамического программирования сверху -- это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.
Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах Ричардом Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953 году он уточнил это определение до современного. Первоначально эта область была основана, как системный анализ и инжиниринг, которая была признана IEEE. Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме.
Слово «программирование» в словосочетании «динамическое программирование» в действительности к «традиционному» программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация». Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определённое расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий.
Оптимальная подструктура в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи. К примеру, кратчайший путь в графе из одной вершины (обозначим s) в другую (обозначим t) может быть найден так: сначала считаем кратчайший путь из всех вершин, смежных с s, до t, а затем, учитывая веса рёбер, которыми s соединена со смежными вершинами, выбираем лучший путь до t (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.
1 Разбиение задачи на подзадачи меньшего размера.
2Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм.
3 Использование полученного решения подзадач для конструирования решения исходной задачи.
Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).
Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи, F3=F2+F1 и F4=F3+F2 -- даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали F2 дважды. Если продолжать дальше и посчитать F5, то F2 посчитается ещё два раза, так как для вычисления F5 будут нужны опять F3 и F4. Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решения для задач, которые он уже решал.
Чтобы избежать такого хода событий, мы будем сохранять решения подзадач, которые мы уже решали, и когда нам снова потребуется решение подзадачи, мы вместо того, чтобы вычислять его заново, просто достанем его из памяти. Этот подход называется мемоизацией. Можно проделывать и подзадачи нам больше не потребуется, можно выкинуть его из памяти, освободив её для других нужд, или если процессор простаивает и мы знаем, что решение некоторых, ещё не посчитанных подзадач, нам понадобится в дальнейшем, мы можем решить их заранее.
Подводя итоги вышесказанного можно сказать, что динамическое программирование пользуется следующими свойствами задачи:
- перекрывающиеся подзадачи;
- оптимальная подструктура;
- возможность запоминания решения часто встречающихся подзадач.
Динамическое программирование обычно придерживается двух подходов к решению задач:
- нисходящее динамическое программирование: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач.
- восходящее динамическое программирование: все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи.
Этот способ лучше нисходящего программирования в смысле размера необходимого стека и количества вызова функций, но иногда бывает нелегко заранее выяснить, решение каких подзадач нам потребуется в дальнейшем.
Языки программирования могут запоминать результат вызова функции с определённым набором аргументов (мемоизация), чтобы ускорить «вычисление по имени». В некоторых языках такая возможность встроена (например, Scheme, Common Lisp, Clojure, Perl, D), а в некоторых требует дополнительных расширений (C++).
Известны сериальное динамическое программирование, включённое во все учебники по исследованию операций, и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах.
Обычное динамическое программирование является частным случаем несериального динамического программирования, когда граф взаимосвязей переменных -- просто путь. НСДП, являясь естественным и общим методом для учёта структуры задачи оптимизации, рассматривает множество ограничений и/или целевую функцию как рекурсивно вычислимую функцию. Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причём эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объём вычислений на каждом этапе может сохраняться в разумных пределах.
Одним из основных свойств задач, решаемых с помощью динамического программирования, является аддитивность. Неаддитивные задачи решаются другими методами. Например, многие задачи по оптимизации инвестиций компании являются неаддитивными и решаются с помощью сравнения стоимости компании при проведении инвестиций и без них.
2. Сведения о средствах языка программирования
Язык Си++ является универсальным языком программирования, в дополнение к которому разработан набор разнообразных библиотек. Поэтому, строго говоря, он позволяет решить практически любую задачу программирования. Тем не менее, в силу разных причин (не всегда технических) для каких-то типов задач он употребляется чаще, а для каких-то - реже.
Си++ как преемник языка Си широко используется в системном программировании. На нем можно писать высокоэффективные программы, в том числе операционные системы, драйверы и т.п. Язык Си++ - один из основных языков разработки трансляторов.
Поскольку системное программное обеспечение часто бывает написано на языке Си или Си++, то и программные интерфейсы к подсистемам ОС тоже часто пишут на Си++.
Распределенные системы, функционирующие на разных компьютерах, также разрабатываются на языке Си++. Этому способствует то, что у широко распространенных компонентных моделей CORBA и COM есть удобные интерфейсы на языке Си++.
Обработка сложных структур данных - текста, бизнес-информации, Internet-страниц и т.п. - одна из наиболее распространенных возможностей применения языка. В прикладном программировании, наверное, проще назвать те области, где язык Си++ применяется мало.
Разработка графического пользовательского интерфейса на языке Си++ выполняется, в основном, тогда, когда необходимо разрабатывать сложные, нестандартные интерфейсы.
В целом надо сказать, что язык Си++ в настоящее время является одним из наиболее распространенных языков программирования в мире.
Самая короткая программа на языке Си++ выглядит так:
// Простейшая программа
int main() { return 1; }
Первая строчка в программе - комментарий, который служит лишь для пояснения. Признаком комментария являются два знака деления подряд ( // ).
main - это имя главной функции программы. С функции main всегда начинается выполнение. У функции есть имя ( main ), после имени в круглых скобках перечисляются аргументы или параметры функции (в данном случае у функции main аргументов нет). У функции может быть результат или возвращаемое значение. Если функция не возвращает никакого значения, то это обозначается ключевым словом void. В фигурных скобках записывается тело функции - действия, которые она выполняет. Оператор return 1 означает, что функция возвращает результат - целое число 1.
Если мы говорим об объектно-ориентированной программе, то она должна создать объект какого-либо класса и послать ему сообщение. Чтобы не усложнять программу, мы воспользуемся одним из готовых, предопределенных классов - классом iostream (поток ввода-вывода, базовый класс для iostream). Этот класс определен в файле заголовков " iostream.h ". Поэтому первое, что надо сделать - включить файл заголовков в нашу программу:
#include <iostream.h>
int main() { return 1; }
Кроме класса, файл заголовков определяет глобальный объект этого класса cout. Объект называется глобальным, поскольку доступ к нему возможен из любой части программы. Этот объект выполняет вывод на консоль. В функции main мы можем к нему обратиться и послать ему сообщение.
Операция сдвига << для класса iostream определена как "вывести". Таким образом, программа посылает объекту cout сообщения "вывести строку Hello, world!" и "вывести перевод строки" ( endl обозначает новую строку). В ответ на эти сообщения объект cout выведет строку " Hello, world!" на консоль и переведет курсор на следующую строку.
Компиляция и выполнение программы
Программа на языке Си++ - это текст. С помощью произвольного текстового редактора программист записывает инструкцию, в соответствии с которой компьютер будет работать, выполняя данную программу.
Для того чтобы компьютер мог выполнить программу, написанную на языке Си++, ее нужно перевести на язык машинных инструкций. Эту задачу решает компилятор. Компилятор читает файл с текстом программы, анализирует ее, проверяет на предмет возможных ошибок и, если таковых не обнаружено, создает исполняемый файл, т.е. файл с машинными инструкциями, который можно выполнять.
Откомпилировав программу один раз, ее можно выполнять многократно, с различными исходными данными.
Не имея возможности описать все варианты, остановимся только на двух наиболее часто встречающихся.
Если Вы используете персональный компьютер с операционной системой Windows N, то компилятор у Вас, скорее всего, Visual C++. Этот компилятор представляет собой интегрированную среду программирования, т.е. объединяет текстовый редактор, компилятор, отладчик и еще ряд дополнительных программ. Мы предполагаем, что читатель работает с версией 5.0 или старше. Версии младше 4.2 изучать не имеет смысла, поскольку реализация слишком сильно отличается от стандарта языка.
В среде Visual C++ прежде всего необходимо создать новый проект. Для этого нужно выбрать в меню File атрибут New. Появится новое диалоговое окно. В закладке Projects в списке различных типов выполняемых файлов выберите Win32 Console Application. Убедитесь, что отмечена кнопка Create new workspace. Затем следует набрать имя проекта (например, test ) в поле Project name и имя каталога, в котором будут храниться все файлы, относящиеся к данному проекту, в поле Location. После этого нажмите кнопку " OK ".