3.2.1. Метод потенциалов

Метод потенциалов рассмотрим на конкретном примере. В качестве исходных данных будем использовать транспортную сеть, представленную на рисунке … . Требуется рассчитать матрицу расстояний и матрицу указателей для данной транспортной сети.

Один цикл расчетов позволяет нам рассчитать значения для одной строки матрицы расстояний и матрицы указателей. Поскольку транспортная сеть содержит в себе 9 пунктов, а матрицы, соответственно, 9 строк и 9 столбцов, для полного заполнения матриц требуемыми данными необходимо выполнить 9 циклов расчета. Начнем первый цикл, в ходе которого рассчитаем требуемые значения для второго пункта, т.е. для второй строки матрицы расстояний и матрицы указателей. При этом будем использовать следующие обозначения:

v(i) – значение потенциала i-ой вершины;

w(i) – значение указателя i-й вершины;

c(i,j) – длина звена, связующего i-ю и j-ю вершины.

На рисунке значение потенциала i-й вершины указывается над самой i-й вершиной, а радом в скобках обозначается значение указателя i-й вершины. Например, вершина 4: v(4) = 20, w(4) = 5. Значение длины связующего звена указывается рядом со звеном с добавлением знака «+», например, c(3,4) = 5.

1. Выберем в качестве начальной вершины – вершину 2. Начальной вершине присвоим следующие значения: v(2) = 0, w(2) = 2. Иными словами, начальная вершина обладает нулевым потенциалом и нулевым указателем.

2. Все вершины сети распределяем по уровням, как показано на рисунке … . Распределение производится следующим образом:

1) первый уровень включает в себя только одну начальную вершину;

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

3) третий уровень включает вершины, которые имеют связующие звенья с вершинами второго уровня, т.е. вершины 3, 4 и 7;

4) четвертый уровень включает вершины, которые имеют связующие звенья с вершинами третьего уровня, т.е. вершины 8 и 6.

3. Вводим такие понятия, как ведущий и ведомый уровни:

Ÿ ведущий уровень – это последний по счету уровень, у которого определены значения потенциалов и указателей;

Ÿ ведомый уровень – это уровень, у которого не определены значения потенциалов и указателей и который следует сразу за ведущим уровнем.

Множество вершин ведущего уровня будем обозначать множеством X, множество вершин ведомого уровня – множеством Y.

Определяем ведущий и ведомый уровни. На данном этапе расчетов ведущим является первый уровень, т.е. X = {2}, а ведомым, соответственно, второй уровень, т.е. Y = {1, 5, 9}.

4. Известно, что вершины ведомого уровня связаны с начальной вершиной. Длины связующих звеньев: c(2,9) = 8, c(2,1) = 7, c(2,5) = 13. Тогда определяем потенциалы и указатели вершин ведомого второго уровня по следующей схеме:

Ÿ v(j) = v(i) + c(i,j) = c(i,j), iÎX, jÎY

Ÿ w(j) = j, jÎY

В результате получаем:

1) вершина 9: v(9) = c(2,9) = 8, w(9) = 9;

2) вершина 1: v(1) = c(2,1) = 7, w(1) = 1;

3) вершина 5: v(5) = c(2,5) = 13, w(5) = 5.

5. Производим проверку на разность потенциалов вершин ведомого уровня. Находим вершины ведомого уровня, которые имеют между собой связующее звено. Такими вершинами на втором уровне являются вершины 1 и 9: c(1,9) = 5. Известно, что v(1) = 7 и v(9) = 8. Проверка разности потенциалов состоит в проверке выполнения следующего условия:

Ÿ v(i) – v(j) £ c(i,j), i,jÎY, v(i) ? v(j),

то есть, применительно к вершинам 1 и 9:

Ÿ v(9) – v(1) £ c(1,9) ® 8 – 7 £ 5 (выполняется).

Поскольку условие выполняется, то объявляется, что проверка на разность потенциалов пройдена успешно. В этом случае никаких действий по пересчету значений потенциалов и указателей вершин 1 и 9 не производится.

6. После проверки на разность потенциалов переопределяем ведущий и ведомый уровни сети. Первый уровень теряет статус ведущего. Ведущим уровнем объявляется второй уровень, т.е. X = {9, 1, 5}, а ведомым уровнем, соответственно, третий уровень, т.е. Y = {3, 4, 7}.

7. Известна длина связующих звеньев между вершинами ведущего и ведомого уровней: c(9,3) = 8, c(1,3) = 9, c(5,4) = 7, c(5,7) = 12. Определяем потенциалы и указатели вершин ведомого третьего уровня по следующей схеме:

Ÿ v(j) = min{v(i) + c(i,j) | iÎX}, jÎY, т.е. путь к вершине j проводим через такую вершину i, которая обеспечивает вершине j минимальное значение потенциала;

Ÿ w(j) = w(i*) : v(i*) + c(i*,j) = min{v(i) + c(i,j) | iÎX}, i*ÎX, jÎY, т.е. указатель j-й вершины полагается равной указателю той i-й вершины ведущего уровня, которая обеспечивает j-й вершине минимальное значение потенциала.

Таким образом, получаем:

Ÿ вершина 3: v(3) = min{v(9)+c(9,3); v(1)+ c(1,3)} = min{8 + 8 = 16; 7 + 9 = 16} = 16, w(3) = w(9) = 9 или w(3) = w(1) = 1. В данном случае складывается ситуация, когда из пункта 2 в пункт 3 можно проехать либо через пункт 9, либо через пункт 1. И в том, и в другом случае длина пути будет одинаковая – 16 км. Поскольку все равно, через какой пункт добираться, то можно выбрать любой, например, w(3) = w(1) = 1;

Ÿ вершина 4: v(4) = v(5) + c(5,4) = 13 + 7 = 20, w(4) = w(5) = 5;

Ÿ вершина 7: v(7) = v(5) + c(5,7) = 13 + 12 = 25, w(7) = w(5) = 5.

8. Производим проверку на разность потенциалов вершин ведомого уровня. Между вершинами 3 и 4 существует связующее звено: c(3,4) = 5 при 3, 4ÎY. Известны потенциалы: v(3) = 16, v(4) = 20. Проверяем на выполнение условие:

Ÿ v(4) – v(3) £ c(3,4) ® 20 – 16 £ 5 (выполняется).

Проверка пройдена, никаких действий не производим.

9. После проверки на разность потенциалов переопределяем ведущий и ведомый уровни сети. Второй уровень теряет статус ведущего.

10. Известна длина связующих звеньев между вершинами ведущего и ведомого уровней: c(3,8) = 7, c(4,8) = 6, c(7,6) = 7. Определяем потенциалы и указатели вершин ведомого четвертого уровня по известной уже схеме:

Ÿ v(j) = min{v(i) + c(i,j) | iÎX}, jÎY;

Ÿ w(j) = w(i*) : v(i*) + c(i*,j) = min{v(i) + c(i,j) | iÎX}, i*ÎX, jÎY.

Таким образом, получаем:

Ÿ вершина 3: v(8) = min{v(3)+c(3,8); v(4)+ c(4,8)} = min{16 + 7 = 23; 20 + 6 = 26} = 23, w(8) = w(3) = 1. В данном случае минимальное значение потенциала вершины 8 обеспечивается при движении через вершину 3. Поэтому указатель вершины 8 полагается равным указателю вершины 3;

Ÿ вершина 6: v(6) = v(7) + c(7,6) = 25 + 7 = 32, w(6) = w(7) = 5.

11. Производим проверку на разность потенциалов вершин ведомого уровня. Между вершинами 8 и 6 существует связующее звено: c(8,6) = 8 при 8, 6ÎY. Известны потенциалы: v(8) = 23, v(6) = 32. Проверяем на выполнение условие:

Ÿ v(6) – v(8) £ c(6,8) ® 32 – 23 £ 8 (не выполняется).

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

Ÿ v(i) = v(j) + c(i,j) и

Ÿ w(i) = w(j).

Применительно к вершинам 6 и 8 получаем:

Ÿ вершина 6: v(6) = v(8) + c(8,6) = 23 + 8 = 31, w(6) = w(8) = 1.

Данные расчеты означают, что из пункта 2 в пункт 6 следует ехать через пункт 8, а не пункт 7, поскольку в первом случае длина пути составит 31 км против 32 км во втором случае.

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

Таблица 3.8

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

По окончании первого цикла расчета начинаются новые циклы, в которых в качестве начальной вершины выбираются вершины 1, 3, 4, …, 9.

Те шаги, которые были выполнены в ходе реализации рассмотренного одного цикла расчетов, можно свести в единый общий алгоритм. Ниже приводится краткое описание данного алгоритма:

Шаг 1. Определяется начальная вершина сети.

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

Ÿ вершины (k-1)-го уровня имели связующие звенья с вершинами k-го уровня;

Ÿ вершины k-го уровня имели связующие звенья с вершинами (k+1)-го уровня;

Ÿ вершины (k-1)-го уровня не имели связующих звеньев с вершинами (k+1)-го уровня.

Шаг 3. Первый уровень объявляется ведущим уровнем, а второй уровень – ведомым.

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

Ÿ v(j) = v(i) + c(i,j) = c(i,j), iÎX, jÎY

Ÿ w(j) = j, jÎY

где X – множество вершин ведущего уровня, Y – множество вершин ведомого уровня.

Если ведомым является третий, четвертый и остальные уровни сети, то значения определяются по формулам:

Ÿ v(j) = min{v(i) + c(i,j) | iÎX}, jÎY;

Ÿ w(j) = w(i*) : v(i*) + c(i*,j) = min{v(i) + c(i,j) | iÎX}, i*ÎX, jÎY.

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

Ÿ v(i) – v(j) £ c(i,j), i,jÎY, v(i) ? v(j).

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

Ÿ v(i) = v(j) + c(i,j),

Ÿ w(i) = w(j).

Шаг 6. Переопределяются ведущий и ведомый уровни сети по следующей схеме:

Ÿ ведущий уровень теряет статус ведущего уровня;

Ÿ ведомый уровень теряет статус ведомого и становится ведущим уровнем;

Ÿ уровень, следующий за ведомым, приобретает новый статус ведомого уровня.

Шаг 7. Повторять шаги 4–6 до тех пор, пока в ходе очередного повторения на шаге 6 не обнаружится, что ведомый уровень является последним уровнем сети.

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

Шаг 9. Повторять шаги1–8, поочередно выбирая в качестве начальной все вершины сети, до тех пор, пока все строки матрицы расстояний и матрицы указателей не будут заполнены соответствующими значениями.