Построение кратчайшего пути на сети

Дан неориентированный граф, для каждого ребра которого задана его длина. Вершины графа пронумерованы числами от 1 до N. Требуется найти путь минимальной длины, соединяющий 1-ю вершину с N-й.

Решим эту задачу методом динамического программирования.

I. Инвариантное погружение. Рассмотрим семейство задач P(k), k=1,...,N, где P(k) – задача о нахождении пути минимальной длины, соединяющий 1-ю вершину с k-й. Исходная задача запишется в виде P(N).

II. Функция Беллмана. Пусть B(k) – длина минимального пути в задаче P(k), x*(k) – последовательность дуг оптимального пути в этой задаче.

III. Уравнение Беллмана (связь между решениями задач семейства). Пусть G – множество вершин, для которых задача нахождения минимального пути уже решена. Рассмотрим множество вершин G₁, смежных с множеством G, т.е. не входящих в G, но в которые можно попасть из множества G по некоторой дуге графа.

Обозначим l=(x,y) – дуга l начинается в вершине x и заканчивается в вершине y, d(l) – длина дуги l.

Пусть min{d(l)+B(k) | l=(m,k), m∈G₁, k∈G} = d(l*)+B(k*), l*=(m*,k*). (3.3.1)

Тогда B(m*) = d(l*)+B(k*), (3.3.2)

причем x*(m*) = (x*(k*), l*). (3.3.3)

IV. Решение семейства задач. Уравнения (3.3.1) – (3.3.3) фактически не надо решать. Они указывают последовательность решения задач нашего семейства. Самые простая задача – найти кратчайший путь из 1-й вершины в эту же вершину, при этом B(1)=0, x*(1) не содержит дуг.

Таким образом, первоначально множество G = {1}, G₁ содержит все смежные с 1-й вершины. Уравнения (3.3.1)–(3.3.3) позволяют расширить множество G, вычислив значение B для одной из смежных вершин (для той, на которой достигается минимум в (3.3.1)).

37. Задача оптимального планирования. Обработка деталей на двух станках.

Имеется n деталей, которые необходимо последовательно обработать сначала на одном, а потом на втором станке. Для каждой детали известно время a_i обработки на первом станке и b_i – на втором станке. Последовательность обработки деталей на обоих станках одинакова.

Необходимо найти оптимальный порядок обработки партии, при котором общее время обработки минимально.

I. Семейство задач. Обозначим через P(i₁,..,i_k | Y) задачу, в которой детали с номерами i₁,..,i_k не обрабатываются, а второй станок включается через Y секунд после начала работы (первого станка). Наша исходная задача: P(пустое множество| 0) – все детали обрабатываются, 2-й станок включается сразу.

II. Функция Беллмана. Введем обозначения: B (i₁,..,i_k | Y) – оптимальное время обработки партии в задаче P(i₁,..,i_k | Y), x*(i₁,..,i_k | Y) – оптимальная последовательность обработки деталей.

III. Уравнение Беллмана. Рассмотрим задачу P(i₁,..,i_k | Y). Возьмём одну из деталей i₁,..,i_k поставим в очередь первой. Эта деталь (с номером i) будет полностью обработана через время Δt=a_i+b_i, если Y≤a_i (т.е. второй станок успеет включиться), Δt=Y+b_i, если Y>a_i (т.е. придется ждать включения второго станка).

В итоге Δt =max{Y, a_i}+b_i = a_i + b_i + max{Y – a_i, 0}.

Мы можем считать, что второй станок для оставшихся деталей включается через b_i + max{Y – a_i, 0} секунд после обработки i-й детали на первом станке.

Предполагая, что оставшиеся детали обрабатываются оптимальным образом, мы затрачиваем на такую обработку время, равное a_i + B (i₁,..,i_k, i | b_i + max{Y – a_i, 0}).

Обозначим через I_k множество всех номеров деталей, не совпадающих с номерами i₁,..,i_k.

Тогда получим уравнение Беллмана

B(i₁,..,i_k | Y) = min {a_i + B (i₁,..,i_k, i | b_i + max{Y – a_i, 0}) | i∈I_k}, (3.4.1)

причем

x*(i₁,..,i_k | Y) = (i*, x*(i₁,..,i_k, i*| b_i* + max{Y – a_i*, 0})), (3.4.2)

где i* – индекс, на котором достигается минимум в (3.4.1).

Уравнение (3.4.1) позволяет связать между собой значения целевых функций различных задач нашего семейства, (3.4.2) – последовательности обработки деталей в этих задачах. Уравнение Беллмана (3.4.1) показывает, что для решения задач с n необрабатываемыми деталями нужно знать решение задач с n+1 необрабатываемой деталью. Другими словами, задачи следует рассматривать в порядке возрастания количества обрабатываемых деталей.

IV. Решение семейства задач. Простейшими задачами семейства являются задачи семейства, в которых обрабатывается только одна деталь (с номером k): P(I\{k} | Y), где I – множество всех номеров деталей (напомним, что в обозначениях задачи до вертикальной черты указываются номера всех необрабатываемых деталей).

Как мы уже вычисляли,

B(I\{k} | Y) = max{Y, a_i}+b_i = a_i + b_i + max{Y – a_i, 0}, (3.4.3)

при этом

x*(I\{k} | Y) = (k) (3.4.4)

– вектор с одной координатой.

Уравнение Беллмана (3.4.1)-(3.4.2) позволяет на основании (3.4.3)-(3.4.4) вычислять решения остальных задач семейства.

Поиск по сайту: