Решение задачи теста для написания и отладки программы - Решение задач методами динамического программирования, нахождение кратчайшего пути

Шаг 1: исходному узлу присваивается метка [0;-], полагаем i=1.

Шаг 2: вычисляются временные метки [ +, i] для всех узлов, которые можно достичь непосредственно из узла 1(i) и которое не имеет постоянных меток.

Рис. 2

Таблица 2

Узел	Метка	Статус метки
1	[0;-]	Постоянная
2	[2;1]	Временная
5	[6;1]	Временная
6	[8;1]	Временная
9	[7;1]	Временная

Среди узлов 2, 5, 6, и 9 наименьшее значение расстояния имеет узел 2, поэтому статус узла меняется на постоянный.

Рис. 3

Таблица 3

Узел	Метка	Статус метки
1	[0;-]	Постоянная
2	[2;1]	Постоянная
5	[6;1]	Временная
6	[8;1]	Временная
9	[7;1]	Временная
3	[8;2]	Временная
7	[13;2]	Временная

Среди узлов 3, 5, 6,7 и 9 наименьшее значение расстояния имеет узел 5, поэтому статус узла меняется на постоянный.

Шаг 3: если узел j уже имеет метку j[k], полученную из другого узла k и если +<, тогда метка меняется на новую.

Рис. 4

Просматриваются все узлы, достижимые из узла 5.

Таблица 4

Узел	Метка	Статус метки
1	[0;-]	Постоянная
2	[2;1]	Постоянная
5	[6;1]	Постоянная
6	[8;1][9;5]	Временная
9	[7;1]	Временная
3	[8;2]	Временная
7	[13;2]	Временная
10	[11;5]	Временная

Среди узлов 3, 6,7,10 и 9 наименьшее значение расстояния имеет узел 9, поэтому статус узла меняется на постоянный.

Рис. 5

Таблица 5

Узел	Метка	Статус метки
1	[0;-]	Постоянная
2	[2;1]	Постоянная
5	[6;1]	Постоянная
6	[8;1]	Временная
9	[7;1]	Постоянная
3	[8;2]	Временная
7	[13;2]	Временная
10	[11;5][11;9]	Временная
8	[16;9]	Временная

Среди узлов 3, 6,7,10 и 8 наименьшее значение расстояния имеет узел 6, поэтому статус узла меняется на постоянный.

Рис. 6

Таблица 6

Узел	Метка	Статус метки
1	[0;-]	Постоянная
2	[2;1]	Постоянная
5	[6;1]	Постоянная
6	[8;1]	Постоянная
9	[7;1]	Постоянная
3	[8;2]	Временная
7	[13;2]	Временная
10	[11;5]	Временная
8	[16;9][15;6]	Временная

Среди узлов 3,7,10 и 8 наименьшее значение расстояния имеет узел 3, поэтому статус узла меняется на постоянный.

Рис. 7

Таблица 7

Узел	Метка	Статус метки
1	[0;-]	Постоянная
2	[2;1]	Постоянная
5	[6;1]	Постоянная
6	[8;1]	Постоянная
9	[7;1]	Постоянная
3	[8;2]	Постоянная
7	[13;2]	Временная
10	[11;5]	Временная
8	[15;6]	Временная
4	[11;3]	Временная

Среди узлов 4,7,10 и 8 наименьшее значение расстояния имеет узел 10, поэтому статус узла меняется на постоянный.

Рис. 8

Таблица 8

Узел	Метка	Статус метки
1	[0;-]	Постоянная
2	[2;1]	Постоянная
5	[6;1]	Постоянная
6	[8;1]	Постоянная
9	[7;1]	Постоянная
3	[8;2]	Постоянная
7	[13;2]	Временная
10	[11;5]	Постоянная
8	[15;6]	Временная
4	[11;3]	Временная

Среди узлов 4,7, и 8 наименьшее значение расстояния имеет узел 4, поэтому статус узла меняется на постоянный.

Рис. 9

Таблица 9

Узел	Метка	Статус метки
1	[0;-]	Постоянная
2	[2;1]	Постоянная
5	[6;1]	Постоянная
6	[8;1]	Постоянная
9	[7;1]	Постоянная
3	[8;2]	Постоянная
7	[13;2]	Временная
10	[11;5]	Постоянная
8	[15;6]	Временная
4	[11;3]	Постоянная

Среди узлов 7, и 8 наименьшее значение расстояния имеет узел 7, поэтому статус узла меняется на постоянный.

Рис. 10

Таблица 10

Узел	Метка	Статус метки
1	[0;-]	Постоянная
2	[2;1]	Постоянная
5	[6;1]	Постоянная
6	[8;1]	Постоянная
9	[7;1]	Постоянная
3	[8;2]	Постоянная
7	[13;2]	Постоянная
10	[11;5]	Постоянная
8	[15;6]	Временная
4	[11;3]	Постоянная

Узел 8 меняет свой статус на постоянный.

Шаг 4: если все узлы имеют постоянные метки, процесс вычисления заканчивается, в противном случае выбирается метка с наименьшим значением расстояния среди всех временных меток.

Рис. 11

Таблица 11

Узел	Метка	Статус метки
1	[0;-]	Постоянная
2	[2;1]	Постоянная
5	[6;1]	Постоянная
6	[8;1]	Постоянная
9	[7;1]	Постоянная
3	[8;2]	Постоянная
7	[13;2]	Постоянная
10	[11;5]	Постоянная
8	[15;6]	Постоянная
4	[11;3]	Постоянная

Так как все узлы имеют статус "постоянная", то процесс вычисления закончен.

Похожие статьи

• Динамическое программирование - Решение задач методами динамического программирования, нахождение кратчайшего пути

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

• Теоретическая основа линейного программирования, Постановка задачи, Методы решения задач линейного программирования, Симплекс - метод, Геометрический метод - Использование методов линейного программирования

  Постановка задачи Постановка практической задачи ЛП включает следующие основные этапы: - определение показателя эффективности, переменных задачи, -...

• Уменьшение времени построение дерева решений для задач линейного программирования с помощью параллельных вычислений

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

• Исследование найденного опорного плана на оптимальность (2-й шаг метода) - Транспортная задача и ее решение методом потенциалов

  Транспортная задача оптимальность Поставим в соответствие поставщикам потенциалы Ui, , а потребителям - Vj, . В оптимальном плане для всех базисных...

• 2.2 Нахождение кратчайших путей в графе - Определение кратчайшего пути в графе

  Начальные понятия Будем рассматривать ориентированные графы G = < V , E> , дугам которых приписаны веса. Это означает, что каждой дуге < U ,...

• Отладка программы - Решение системы линейных уравнений методом Гаусса

  Отладку программы начинают с составления плана тестирования. Такой план должен представлять себе любой программист. Составление плана опирается на...

• Методика решения задач ЛП графическим методом - Линейное программирование

  I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые. II. Найти и заштриховать...

• Решение задачи, Анализ оптимального решения - Использование методов линейного программирования

  1. Для задания необходимых параметров оптимизации нажатием кнопки Параметры откроем окно "Параметры поиска решения" (рис.4). В этом окне оставьте...

• ЛАБОРАТОРНАЯ РАБОТА, "РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL", Цель работы, Порядок выполнения работы, Инструкция по использованию microsoft excel для решения задач лп - Решение задач линейного программирования с использованием Microsoft Excel

  "РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL" Цель работы Приобретение навыков решения задач линейного программирования...

• Математические методы и средства решения задачи, Описание данных - Разработка программы для проверки нечетности числа в среде разработки С++ Builder 3.11

  Средствами решения задачи является алгоритмический язык С++. Операторы и функции, используемые для решения поставленной задачи: #Include - подключение...

• Транспортная задача - Использование методов линейного программирования

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

• Введение, Постановка задачи - Разработка программы вычисления определенных интегралов численными методами

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

• Математические основы решения задачи линейного программирования графическим способом, Математический аппарат - Линейное программирование

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

• Постановка задачи, Организация сбора информации, JMP, Надстройка для Microsoft Exсel "Интеллектуальный анализ данных" - Деревья решений

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

• Проблема, Существующие решения, Денормализация - Программа расчета агрегатов по накапливающимся данным для построения отчетов

  Рисунок 1. Пример сложной схемы БД Пример проблемной ситуации, которую этот проект должен разрешить представлен на рис. 1. Организатор проводит события...

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

  Разработка структуры программы Согласно заданию проект программы разрабатывается в среде визуального программирования Microsoft Visual Studio 2012 на...

• Решение одноиндексной задачи линейного программирования, Построение модели - Использование методов линейного программирования

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

• Тестирование и отладка программы - Разработка электронного учебного пособия "VBA. Решение задач"

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

• Методы решения примененные в программе, Краткое описание среды визуальной разработки Delphi - Разработка программы для решения систем линейных уравнений методом Гауса и Жордана-Гаусса в программном комплексе Delphi

  Метод Гаусса. Метод Гаусса решения систем линейных уравнений состоит в последовательном исключении неизвестных и описывается следующей процедурой. С...

• Введение, Описание поставленной задачи, Краткая характеристика численного метода, Анализ литературы и программ, патентный поиск - Разработка программы численного решения обыкновенного дифференциального уравнения

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

• Метод наименьшей стоимости - Транспортная задача линейного проектирования

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

• Модель распределенных вычислений MapReduce - Технологии больших данных: анализ и выбор решения для реализации проекта

  Программная модель данных, получившая название "MapReduce", была создана несколько лет назад в компании Google, и там же была осуществлена первая...

• Построение графиков функций, Построение графика периодичной кусочно-ломаной функции с условиями - Автоматизация решения задач пользователя

  Постановка задачи: Для заданных функций необходимо: 1. Построить электронную таблицу (одну для обеих функций) для вычисления значений функций в заданном...

• Определение нового, улучшенного опорного решения транспортной задачи (3-й шаг метода) - Транспортная задача и ее решение методом потенциалов

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

• Математическая формулировка задачи - Разработка программы вычисления определенных интегралов численными методами

  Метод прямоугольников Пусть требуется определить значение интеграла функции на отрезке. Этот отрезок делится точками на равных отрезков длиной Обозначим...

• Вывод уравнения движения заданной модели, Численные методы решений дифференциальных уравнений - Четырехмассовая динамическая модель трансмиссии автомобиля

  Выведем в общем виде уравнение движения заданной динамической модели при помощи уравнений Лагранжа II рода. Полная кинетическая энергия: , Полная...

• Использование языка PERL для написания CGI-cкриптов - Язык программирования PERL. Сфера применения

  Как вы узнали из предыдущей главы, CGI обеспечивает узлам Web вoзмoжнoсть интерактивной работы с клиентскими программами, в качестве которых обычно...

• Модель исходной системы, Выбор методов для переноса - Система автоматизированного разделения кода прикладных программ

  Данная методика рассчитана на приложения с трехуровневой архитектурой: клиент - сервер приложений - сервер базы данных. Так как программа нацелена на...

• Необходимые алгоритмы реализации метода конечных элементов, Теоретические аспекты поставленной задачи - Реализация метода конечных элементов для расчета ферменных конструкций под ОС Android

  Теоретические аспекты поставленной задачи В этой части проекта будут объяснены этапы применения МКЭ для плоской фермы. В первой главе было рассмотрено...

• РЕШЕНИЕ ЗАДАЧИ НА ЭВМ, Интерфейс программы, Решение задачи по разбиению реальных плоских конструкций на конечные элементы - Программное обеспечение расчета конструкций

  Интерфейс программы Главное окно. 1) Во вкладке Файл можно открыть файл, сохранить его и сохранить сетку. 2) Во вкладке Вид. Настраивается отображение...

• Стандартные программы операционной системы Windows. - Приложения технологии системы электронных таблиц Excel к решению задач механики

  Широкое распространение в операционной системе Windows имеет множество стандартных программ обеспечивающих работу устройств компьютера и служащих для...

• Методы и средства защиты пользователей от воздействия на них опасных и вредных факторов - Выбор оптимального решения для виртуализации

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

• Постановка задачи, Язык программирования Delphi - Разработка программы "Будильник"

  Поставленная задача заключается в следующем. Необходимо создать программу для подачи до 5-ти сигналов в заданное время суток на заданную дату или...

• Предлагаемое решение, Таблица агрегатов, Таблица лога изменений - Программа расчета агрегатов по накапливающимся данным для построения отчетов

  База данные кеширование денормализация Предлагаемое решение -- скомбинировать некоторые идеи кеширования и денормализации в специальной библиотеке...

• Описание процедур и алгоритм роботы программы - Разработка программы для решения систем линейных уравнений методом Гауса и Жордана-Гаусса в программном комплексе Delphi

  Программный алгоритм визуальный гаусс В программу включены следующие процедуры: "gauss1", "gaussj", "New1Click", "Button1Click", "Button2Click",...

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

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

• Решим следующую систему методом Гаусса. - Составление программы для решения системы уравнений

  A 11 = 2 0. (1) Для решения систем уравнения с помощью Гаусса будем выделить коэффициенты системы следующим образом: A 11 =2, A 12 = 7, a 13 =13 b 1 = 0...

• Получаем верхнюю треугольную матрицу А:, Разновидности метода исключения: - Составление программы для решения системы уравнений

  , Алгоритм обратного хода: Шаг 1. Вычислим Шаг 2. Вычислим: , Рис. 1. Основной алгоритм решения СЛУ методом исключения Гаусса. Для контроля правильности...

• Решение систем линейных уравнений, Метод исключений Гаусса - Составление программы для решения системы уравнений

  Дана система линейных уравнений (СЛУ) с n неизвестными: В матричной форме записи система (1) имеет вид: (2) Где : n - порядок системы; - матрица...

• Математические методы и средства решения задачи, Описание данных - Программа: проверка истинности высказывания

  Средствами решения задачи является алгоритмический язык С++. Операторы и функции, используемые для решения поставленной задачи: #Include - подключение...

Решение задачи теста для написания и отладки программы - Решение задач методами динамического программирования, нахождение кратчайшего пути

Предыдущая | Следующая