1. Определение выгодного пути

Граф – это совокупность двух конечных множеств: множества точек, которые называются вершинами, и множества пар вершин, которые называются ребрами (или дугами).

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

Пример решения задачи

Требуется перевезти груз из города А в город В. Сеть дорог, связывающих А и В показана на рис. 1.1. Стоимость перевозки груза из города S в город J проставлена над соответствующими дугами сети.

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

Условие. Вершинам сети соответствуют города, а дугам транспортные магистрали (рис. 1.1).

Рис. 1.1

Алгоритм решения

Используется метод динамического программирования.

1. Задача разбивается на шаги искусственным образом. В качестве шага выбирается некоторое подмножество городов, на которое разбивается всё множество в соответствии с заданной сетью транспортной магистрали. Сеть, изображенную на рис. 1.1 удобно разбить на четыре части. Процесс решения задачи разбивается на четыре шага.

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

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

4. Выигрыш, который приносит на n шаге управление , будет ( ) − стоимость перевозки груза из S в J.

Пусть − минимальные затраты на перевозку груза от города S до конечного города, если осталось n шагов.

5. Обозначим через − состояние, в которое должна перейти система под влиянием управления на n шаге.

6. Основное рекуррентное уравнение для данной задачи имеет вид

. (1.1)

Решение задачи

Выполняем первый этап − оптимизацию в условном направлении. Оптимизация в условном направлении выполняется с последнего шага . Рекуррентное уравнение для в соответствии с (1.1) имеет вид .

Состояние системы S на данном шаге может иметь значение 7 или 8 (номера городов, из которых можно выехать на данном шаге). Шаговое управление J = 9 (номер города через который следует ехать из города S).

Выигрыш (затраты по перевозке из S в J) определяется по рис.1 для всех возможных на данном шаге значений S и J: = 9; = 8. Значение так как из города 9 груз вывозить не надо. Таким образом, затраты на перевозку из 7 и 8 в конечный город определяются суммами:

Оформим решение в виде табл. 1.1.

Таблица 1.1

S J	9
7	9+0	9	9
8	8+0	8	9

В первом столбце табл. 1.1 расположены возможные значения состояния системы S на шаге n. В первой строке − возможные значения шагового управления J. В каждой клетке сумма для соответствующих значении S и J на данном шаге. Значения при берутся из предыдущей таблицы. Для . В предпоследнем столбце вычисляются минимальные затраты по перевозке груза из города S, если до конца маршрута осталось n шагов − (наименьшее значение из сумм в строке). В последнем столбце фиксируется номер города , через который следует ехать, чтобы достичь минимальных затрат ,

.

Результат оформим в виде табл. 1.2.

Таблица 1.2

S J	7	8
4	8+9	-	17	7
5	6+9	5+8	13	8
6	-	5+8	13	8

Рекуррентное соотношение для (n-3) имеет вид .

Вычисления для третьего шага оформим в виде табл. 1.3.

Таблица 1.3

S J	4	5	6
2	17+7	-	15+13	24	4
3	-	6+13	8+13	19	5

Для последнего шага − в табл. 1.4.

Таблица 1.4

S J	2	3
1	10+24	11+19	30	3

Второй этап − безусловная оптимизация.

В табл. 1.4 − искомые минимальные затраты по перевозке груза из города А в конечный город В. Для того, чтобы получить эти затраты, груз из города должен быть доставлен в город .

Находим новое состояние системы на втором шаге

.

По новому состоянию S = 3 из табл. 1.3 определяем − город в который нужно ехать из города 3, чтобы получить минимальные затраты . Состояние системы на третьем шаге .

Находим (для ) номер города, в который нужно ехать из города , это из табл. 1.2. Состояние системы на четвертом шаге . В табл. 1.1 этому состоянию соответствует город . Двигаясь от последней таблицы к первой определяем, оптимальный маршрут , затраты на перевозку груза по которому составляют .

Задача для самостоятельного решения

Найти маршрут, связывающий города А (1) и В (10), для которого суммарные затраты на перевозку груза были бы наименьшими, (рис. 1.2)

Использовать метод динамического программирования.

Рис. 1.2

Стоимость перевозки груза по всем направлениям приводится ниже для каждого варианта.