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

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

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

Понятный интерфейс снижает количество человеческих ошибок.

 

1.6 Требования  к надежности и хранению информации

 

В целях избежание  не корректной работы программы  не рекомендуется:

• Удаление данных и файлов и каталога программы;
• Изменение структуры и целостности кода программы;
• Переименование и перемещение файлов в каталоге программы;

Объем программы  составляет 584 кб. Приложения можно  хранить на любых носителях. Ограничения  на транспортировку отсутствуют.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 Основная  часть

 

2.1 Математическая  модель

 

Математическая модель - это математическое представление  реальности.

Математическое моделирование - процесс построения и изучения математических моделей.

Модель - объект произвольной природы, который отражает главные, с точки зрения решаемой задачи, свойства объекта моделирования.

Главные функции модели:

• упрощение получения информации о свойствах объекта;
• передача информации и знаний;
• управление и оптимизация объектами и процессами;
• прогнозирование;
• диагностика.

Идея динамического  программирования заключается в том, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи. К примеру, кратчайший путь в графе из одной вершины (обозначим s) в другую (обозначим t) может быть найден так: сначала считаем кратчайший путь из всех вершин, смежных с s, до t, а затем, учитывая веса ребер, которыми s соединена со смежными вершинами, выбираем лучший путь до t (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага:

1. Разбиение задачи на подзадачи меньшего размера;
2. Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трех шаговый алгоритм;
3. Использование полученного решения подзадач для конструирования решения исходной задачи.

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

Подводя итоги вышесказанного можно сказать, что динамическое программирование пользуется следующими свойствами задачи:

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

Динамическое программирование обычно придерживается двух подходов к решению задач:

• нисходящее динамическое программирование: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач;
• восходящее динамическое программирование: все подзадачи,

 

 

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

 

2.2 Метод  решения задачи

 

Решение задач - процесс, являющийся составной частью мышления, выполнение действий или мыслительных операций, направленное на достижение цели, заданной в рамках проблемной ситуации.

Алгоритм - это всякая система вычислений, выполняемых  по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

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

1. выделить и описать подзадачи, через решение которых будет выражаться искомое решение;
2. выписать рекуррентные соотношения (уравнения), связывающие оптимальные значения параметра для подзадач;
3. вычислить оптимальное значение параметра для всех подзадач;
4. построить само оптимальное решение, используя полученную информацию.

Если нас интересует только значение параметра, то шаг 4 в  алгоритме не нужен (такая ситуация характерна, например, для задач  подсчета количеств допустимых вариантов или некоторых конфигураций, в том числе и комбинаторных). Однако, в случае необходимости построения самого оптимального решения иногда приходится в процессе выполнения шага 3 алгоритма получать и хранить дополнительную информацию. Зачастую именно шаг 4 оказывается самым сложным при реализации подобных алгоритмов.

Ниже приведен пример аналитического решением относительно предметной области, где:

Ui - выбор дороги на i - м шаге по которому направляется груз из данного пункта в соседний пункт;

Fi - итог предыдущего шага местонахождение транспорта с грузом в пункте в котором пребывает перед следующим шагом;

Zi – затраты на перевозку единиц груза из данного пункта в соседний.

Рассмотрим  решение задачи на данном примере. Дана модель соединения городов:

 

 

 

 

 

 

Рисунок 2 – Модель соединения городов

 Основные этапы решения задачи представлены в таблицах 8 – 12.

 Таблица 8 - разбиение вершин по группам

I	I	III	IV	V
с1	с2	с5	с8	с10
	с3	с6	с9
	с4	с7

После чего составим основное функциональное уравнение динамического  программирования:

F_i (x_i – 1, U_i) = extr (Z_i (x_i – 1, U_i) + F_i + 1 (x_i));

Для n шага уравнение примет следующий вид:

Fn (x_n – 1, U_n) = extr (Z_n (x_n – 1, U_n – 1, U_n) + F_n + 1 (x_n));

Таблица 9 - первый этап

х3	U4	Z3	х4	f4
с8	(8,10)	1	С10	1
с9	(9,10)	7	С10	7

 

 

 

 

Для первого этапа  уравнение примет следующий вид:

F4 (x₃ – 1, U₄) = extr (Z₃ (x₃ – 1, U₄ – 1, U₄) + F₄ + 1 (x₃));

Таблица 10 - второй этап

X2	U3	Х3	Z3	F4	Z3+F4	F3
с5	(5,8)	с8	7	1	8	8
	(5,9)	с9	2	7	5	-
с6	(6,8)	с8	9	1	10	-
	(6,9)	с9	2	7	9	9
с7	(7,9)	с9	8	7	15	11

Для второго этапа  уравнение примет следующий вид:

F3 (x₂ – 1, U₃) = extr (Z₃ (x₂ – 1, U₃ – 1, U₃) + F₃ + 1 (x₂));

Таблица 11 - третий этап

X1	U2	Х2	Z2	F4	Z2+F3	F2
с2	(2,5)	с5	1	8	9	9
	(2,7)	с7	6	15	21	-
с3	(3,5)	с5	2	8	10	10
	(3,6)	с6	7	9	16	-
	(3,7)	с7	4	15	19	-
с4	(4,5)	с5	6	8	14	14
	(4,6)	с6	8	9	17	-
	(4,7)	с7	3	15	18	-

 

Для третьего этапа уравнение  примет следующий вид:

F2 (x₁ – 1, U₂) = extr (Z₂ (x₁ – 1, U₂ – 1, U₂) + F₂ + 1 (x₁));

Таблица 12 – четвертый этап

X0	U1	Х1	Z1	F2	Z1+F2	F1
с1	(1,2)	с2	3	9	12	12
	(1,3)	с3	5	10	15	-
	(1,4)	с4	4	14	18	-

 

 

 

 

 

Для четвертого этапа уравнение примет следующий вид:

F1 (x₀ – 1, U₁) = extr (Z₁ (x₀ – 1, U₁ – 1, U₁) + F₁ + 1 (x₀));

Наиболее экономичный  маршрут доставки груза из пункта 1 в пункт 10 это: 1-2-5-8-10, а минимальные расстояние составляют 12 тыс.км.

2.3 Структурная схема программы

Структурная схема программы проиллюстрирована на рисунке 3.

 

 

 

 

Рисунок 3 - Пример структурной схемы программы

 

2.4 Схема  взаимодействия модулей

Схема взаимодействия модулей представлен на рисунке 4.

Рисунок 4 - Схема взаимодействия модулей

 

 

 

 

 

 

 

 

 

3 Руководство  программисту

 

Программа предназначена  для нахождения кратчайшего пути.

Структура программы  построена на взаимодействии двух модулей  «Matrica» в котором осуществляется заполнения матрицы  и произведение необходимых расчетов.  В модуль «Rechenie» выводится аналитическое решение и ответ.

Форматирование  конкретного варианта программы, обладающего  свойством многовариантности, учитывающего состав и структуру технических  средств, может производиться по необходимости средствами Borland Delphi при подключении стандартных библиотек.

 

4 Руководство  пользователя

 

4.1 Общие  сведения

 

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