1631124435-59a81a8a1084f5170bbbb6e23ee88408 (848542), страница 4
Текст из файла (страница 4)
На каждом шагепрямого хода находится оптимальное значение целевой функции подзадачи, а такжеусловно-оптимальное значение одной переменной. На обратном ходе алгоритма по условнооптимальным значениям строится оптимальное решение исходной задачи.Принцип оптимальности Беллмана. Отрезок оптимального процесса от любой его точки доконца процесса сам является оптимальным процессом с началом в данной точке.Алгоритмы ДП применимы в случаях, когда выполняется принцип оптимальности Беллманаи в процессе принятия решений удается выделить отдельные шаги (этапы) процесса иосуществить оптимизацию на каждом шаге.Прямой ход ДП заключается в вычислении значений H(k) и t(k) для k = 0, …, n. ВеличинаH(n) является оптимальным значением целевой функции.
На последнем шаге прямого хода,при k = n, находится оптимальное значение последней переменной, равное t(n).Обратный ход ДП строит оптимальное решение по условно-оптимальному t(k), k = 0, …, n.Для этого достаточно определить значения k. Так как последний день производства t(n)известен, то полагаем k = t(n) – 1. Следовательно, t(k) – предпоследний момент, когдаосуществлялось производство. Повторяя аналогичные операции, находим все моментызапуска производства.22.2.Если частный случай проблемы – полиномиально разрешимая задача, то является липолиномиально разрешимой исходная проблема?Нет.
По определению. Пример:задача о ранце, частный случай - все веса одинаковы.(ОПР: Класс NP-полных проблем (обозначим его NPC) – это подмножество задач PNP,обладающих свойством, что любая задача из класса NP полиномиально сводится к P.ОПР: Класс P NP – это множество задач, для которых полиномиальные алгоритмырешения.)22.3. НЕТ!!!!!! Имеется граф, отражающий связи университета со всеми общежитиями.
Известнастоимость создания дороги по каждому ребру графа. Можно ли с полиномиальнойтрудоемкостью найти дерево минимальной стоимости, которое связывает все общежития иуниверситет?23.1. Теорема о связи прямой и обратной задач о ранце (с доказательством).Пусть β̃ = max{β| Q(β) ≤ A, β ≥ 0}. Тогда S(A) = β̃ и оптимальное решение 0 (β̃) обратнойзадачи (P(β̃)) является оптимальным и для прямой задачи (P(A)).Доказательство.
Обозначим S*= S(A). Так как x*(A) – допустимый вектор для обеих задач(P(S*)) и (P(A)), то Q(S*) ≤ (a, x*(A)) ≤ A. Из неравенства Q(S*) ≤ A и определения β̃ следует,что β̃ ≥ S*. С другой стороны, так как оптимальное решение 0 (β̃) обратной задачи (P(β̃))является допустимым для прямой задачи (P(A)) (так как (a, 0 (β̃)) = Q(β̃) ≤ A), то β̃ ≤ (c, 0 (β̃ )) ≤ (c, x*(A)) = S* . Значит, β̃ = S* = S(A) и (c, 0 (β̃ )) = S(A).23.2. Пусть задачи P, Q NP, P NPC и полиномиально сводится к Q.
Что можно сказать о Q?Это значит, если вы умеете решать P за полиномиальное время, то умеете решать Q заполиномиальное время. (что Q∈ )23.3. Можно ли в сетевой модели сначала найти поздние времена наступления событий, а затемранние? Ответ обосновать.Нет. Для нахождения позднего времени наступление событий в алгоритме Форданеобходимо наличия раннего времени наступления последнего события.24.1. Задача о ближайшем соседе. Схема динамического программирования для ее решения вслучае произвольного числа отрезков разбиения.Задача о ближайшем соседе.
Схема динамического программирования для ее решения вслучае произвольного числа отрезков разбиения.Рассмотрим задачу о ближайшем соседе (ЗБС), моделирующую следующую содержательнуюпостановку. Имеется линейный объект (например, участок дороги или государственнойграницы). Требуется разбить этот объект на участки таким образом, чтобы суммарнаястоимость их обслуживания была минимальна.Пусть объект представлен отрезком [0, M], M ∈ + и точки разбиения ∈ [0, M] могутпринимать только целые значения. Введем функцию f(x, y) ≥ 0, 0 ≤ x ≤ y ≤ M, которая равназатратам, связанным с обслуживанием отрезка [x, y] ⊆ [0, M].Математическая постановка задачи в случае произвольного числа отрезков разбиения:∑=1 (−1 , ) → min,{0 = 0 < 1 < ⋯ < = , > 0Для такой задачи справедливы простые рекуррентные соотношения: ̃(0) = 0, ̃() =min {̃() + (, ), = 1, … , .=0,1,…,−1Прямой ход.
Вычислим значения: ̃ (y) для y = 0, 1, …, 8 и запомним соответствующиеусловно-оптимальные решения.Обратный ход. Имеем минимальные затраты, связанные с разбиением отрезка [0, M] наоптимальное количество частей, S* = ̃ (M) и последнюю точку оптимального разбиения.Вычисляем оптимальное решение.24.2. Пусть задачи P, Q NP, P полиномиально разрешима и полиномиально сводится к Q. Чтоможно сказать о Q?Что Q полиномиально решается.24.3. Записать математическую постановку следующей задачи. Имеется n ис-полнителей и nработ.
Затраты, связанные с назначением i-го исполнителя на j-ю работу равны cij. Требуетсяназначить по одному исполнителю на каждую работу т.о., чтобы суммарные затраты былиминимальны.1, если исполнитель назначен на работу Введем переменные = {0, иначе.Целевая функция: min ∑=1 ∑=1 .{ }Ограничения:Каждый исполнитель выполняет одну работу: ∑=1 =1, i=1, …, m.Любая работа выполняется одним исполнителем: ∑=1 =1, j=1, …, m.25.1. Алгоритм построения максимального паросочетания в двудольном графе (бездоказательств).Пусть задан двудольный граф G = (V1, V2, E), V = V1 ∪ V2.
Одна вершина каждого ребрапринадлежит V1, а другая − V2. Требуется найти в графе G паросочетание максимальноймощности.Предположим имеется некоторое (возможно, пустое) паросочетание M и мы хотим найтилибо аугментальный путь, либо показать, что такого пути нет и значит, паросочетание Mмаксимальное.Замечание 6.1. Так как аугментальный путь P содержит нечетное количество ребер и граф Gявляется двудольным, то одна из конечных вершин пути P принадлежит V1, а другая − V2.Поиск аугментального пути можно начинать с любого подмножества вершин, например, сV1. Алгоритм начинает работу с пометки всех вершин в V1, которые не инцидентны ребрампаросочетания M. Это первые вершины строящихся чередующихся путей.
Первое(нечетное) ребро чередующегося пути должно быть из множества E \ M, и, следовательно,все такие ребра, инцидентные помеченным вершинам из V1, включаются в строящиеся пути.Конечные вершины последних ребер, которые принадлежат V2, также получают метки.Второе (четное) ребро чередующегося пути должно быть из M, и, следовательно, все ребраиз M, инцидентные помеченным вершинам из V2, включаются в чередующиеся пути.Непомеченные вершины из V1, которые являются концевыми для четных ребер, такжепомечаются и т. д.Пометка вершин прекращается, когда либо помеченная вершина из V2 не принадлежит M,значит, найден аугментальный путь, либо ни одна вершина более не может быть помечена,и значит, аугментального пути не существует.Приведем формальное описание алгоритма.Шаг 0.
Заданы двудольный граф G = (V1, V2, E) и паросочетание M. Все вершины не помеченыи не просмотрены.Шаг 1. (Пометка вершин.)1.0. Приписать метку «∗» каждой непомеченной и не принадлежащей M вершине множестваV1.1.1. Если нет непросмотренных вершин, то перейти на шаг 3.Иначе выбрать помеченную и не просмотренную вершину i. Если i ∈ V1, перейти на шаг 1.2.Если i ∈ V2, перейти на шаг 1.3.1.2.
(Просмотр помеченной вершины i ∈ V1.) Для всех (i, j) ∈ E \ M если j ∈ V2 не помечена, топриписать вершине j метку «i». Теперь вершина i просмотрена. Перейти на шаг 1.1.1.3. (Просмотр помеченной вершины i ∈ V2.) Если вершина i не принадлежит M, то перейтина шаг 2. В противном случае, для всех (j, i) ∈ M если j ∈ V1 не помечена, то приписатьвершине j метку «i».Теперь вершина i просмотрена. Перейти на шаг 1.1.Шаг 2. (Аугментация.) Аугментальный путь P найден. Использовать метки начиная с i ∈ V2для восстановления этого пути.
Положить M = (M ∪ P) \ (M ∩ P). Удалить все метки. Перейтина шаг 1.Шаг 3. (Не существует аугментального пути.) Стоп.25.2. Какие требования достаточно наложить на параметры задачи о ранце, чтобы реализоватьсхему динамического программирования?Входные данные (веса предметов) должны быть целочисленные25.3. НЕТ!!!!!!! Записать математическую постановку следующей задачи. Имеется n исполнителей и n работ. Исполнитель i выполняет работу j за tij часов.
Требу-ется назначить поодному исполнителю на каждую работу т.о., чтобы все работы были выполнены за минимальноевремя.26.1. Алгоритм динамического программирования для решения задачи производства и храненияпродукции.Прямой ход ДП заключается в вычислении значений H(k) и t(k) для k = 0, …, n. ВеличинаH(n) является оптимальным значением целевой функции. На последнем шаге прямого хода,при k = n, находится оптимальное значение последней переменной, равное t(n).Обратный ход ДП строит оптимальное решение по условно-оптимальному t(k), k = 0, …, n.Для этого достаточно определить значения k. Так как последний день производства t(n)известен, то полагаем k = t(n) – 1. Следовательно, t(k) – предпоследний момент, когдаосуществлялось производство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
