Файл: Лабораторная работа 1 5 Бинарные деревья 5 Цель работы 5 Краткие теоретические сведения 5 Постановка задачи 6.docx

Рисунок 2.23 – Во вторую матрицу в поле [1,4] занесено значение 2, поскольку для перехода из вершины 1 в вершину 4 в качестве промежуточной использована вершина 2

Далее алгоритм ищет, в какие вершины можно попасть из вершины 1, используя три промежуточных вершины. Далее алгоритм прекратит поиски, поскольку используя четыре промежуточных вершины алгоритм придет в исходную вершину, то есть в вершину 1, что не имеет смысла. Используя три промежуточных вершины попасть ни в одну из вершин невозможно. Поиски для вершины 1 прекращены.

Затем алгоритм ищет кратчайшие пути от вершины 2 до всех остальных. Так же, как и для вершины 1, алгоритм проверяет, куда можно попасть из вершины 2, используя только одну промежуточную вершину. Такими являются вершины 1, куда можно попасть через вершину 3 и вершина 4, в которую также можно попасть через вершину 3.

Рассчитаем в условных единицах затраты на преодоление каждого пути: чтобы попасть из вершины 2 в вершину 1 через вершину 3, потребуется

2+7=9 условных единиц.

Чтобы попасть из вершины 2 в вершину 4 через вершину 3 потребуется

2+3=5 условных единиц.

Алгоритм сравнивает полученные значения со значениями, которые на данный момент находятся в первой матрице:

чтобы пройти из вершины 2 в вершину 1 потребуется бесконечно много условных единиц, то есть на данный момент добраться из вершины 2 в вершину 1 невозможно. В то же время найден путь, в котором придется затратить только 9 условных единиц для того, чтобы попасть из вершины 2 в вершину 1. Затраты в 9 условных единиц на преодоление пути меньше, чем бесконечное значение затрат, поэтому в первой матрице в поле [2,1] записывается вместо бесконечно большого значения значение 9. Затем длина пути из вершины 2 в вершину 4 через вершину 3 с затратами 5 условных единиц сравнивается со значением, хранящимся в поле [2,4] первой матрицы. Затраты в 5 условных единиц меньше, чем в 11 условных единиц, поэтому в поле [2,4] первой матрицы записывается вместо значения 11 значение 5. Во второй матрице поле [2,1] записывается 3, поскольку чтобы попасть из вершины 2 в вершину 1, нужно сначала пройти в вершину 3, в ячейку [2,4] также записывается значение 3, поскольку для того, чтобы попасть из вершины 2 в вершину 4, нужно сначала пройти вершину 3.

На этом этапе матрицы выглядят так:
Первая матрица:

№ вершины	1	2	3	4
1	0	2	4	7
2	9	0	2	5
3	7	10000	0	3
4	10000	10000	10000	0

---

Рисунок 2.24 – В первую матрицу занесены значения 9 и 5 – затраты на преодоление путей от вершины 2 до вершин 1 и 4

Вторая матрица:

№ вершины	1	2	3	4
1	0	2	2	2
2	3	0	3	3
3	1	0	0	4
4	0	0	0	0

Рисунок 2.25 – Во вторую матрицу в поля [2,1] и [2,4] занесено значение 3, поскольку для перехода из вершины 2 в вершины 1 и 4 в качестве промежуточной использована вершина 3

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

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

На следующем этапе работы алгоритм ищет кратчайшие пути от вершины 3 до всех остальных. Метод ищет вершины, в которые можно попасть из вершины 3 через одну промежуточную вершину. Такими вершинами являются вершины 2 и 4, в которые переход осуществляется через вершину 1. Рассчитаем затраты на преодоление каждого пути в условных единицах: чтобы попасть из вершины 3 в вершину 2 через вершину 1, потребуется

7+2=9 условных единиц.

Чтобы попасть в вершину 4 из вершины 3 через вершину 1, потребуется

7+10=17 условных единиц.

Алгоритм сравнивает полученные значения со значениями из первой матрицы:

---

чтобы пройти из вершины 3 в вершину 2 потребуется бесконечно много условных единиц, то есть на данный момент добраться из вершины 3 в вершину 2 невозможно. В то же время найден путь, в котором придется затратить только 9 условных единиц для того, чтобы попасть из вершины 3 в вершину 2. Затраты в 9 условных единиц на преодоление пути меньше, чем бесконечное значение затрат, поэтому в первой матрице в поле [3,2] записывается вместо бесконечно большого значения значение 9. Затем длина пути из вершины 3 в вершину 4 через вершину 1 с затратами 17 условных единиц сравнивается со значением, хранящимся в поле [3,4] первой матрицы. Затраты в 17 условных единиц больше, чем в 11 условных единиц, то есть рассмотренный путь не является более выгодным. Во второй матрице в поле [3,2] записывается 1, поскольку чтобы попасть из вершины 3 в вершину 2, нужно сначала пройти в вершину 1 в ячейку [3,4] ничего не записывается.

На этом этапе матрицы выглядят так:

Первая матрица:

№ вершины	1	2	3	4
1	0	2	4	7
2	9	0	2	5
3	7	9	0	3
4	10000	10000	10000	0

Рисунок 2.26 – В первую матрицу занесено значение 9 – затраты на преодоление пути от вершины 3 до вершины 2

Вторая матрица:

№ вершины	1	2	3	4
1	0	2	2	2
2	3	0	3	3
3	1	1	0	4
4	0	0	0	0

---

Рисунок 2.27 - Во вторую матрицу в поле [3,2] занесено значение 1, поскольку для перехода из вершины 3 в вершину 2 в качестве промежуточной использована вершина 1

Далее алгоритм ищет, в какие вершины можно попасть из вершины 3 через две промежуточных вершины. Такими вершинами являются вершины 3 и 4. В вершину 3 переходить не имеет смысла. В вершину можно попасть через вершины 1 и 2. Рассчитаем затраты в условных единицах на преодоление этого пути: чтобы попасть из вершины 3 в вершину 4 через две промежуточных вершины, потребуется

7+2+11=20 условных единиц.

Алгоритм сравнивает полученное значение со значением, которое на данный момент находится в первой матрице:

Чтобы пройти от вершины 3 до вершины 4 напрямую, потребуется затратить 3 условных единицы, поэтому путь через вершины 1 и 2, на который необходимо затратить 20 условных единиц, не является более выгодным, поэтому ни в первую, ни во вторую матрицу ничего не записывается.

Затем алгоритм ищет вершины, в которые можно попасть из вершины 3 через три промежуточных вершины. Таких вершин нет, поэтому алгоритм прекращает поиск, так как через четыре промежуточных вершины в любом случае будет осуществлен переход в исходную вершину.

На следующем этапе работы алгоритм определяет кратчайшие пути от вершины 4 до всех остальных. Алгоритм ищет, в какие вершины можно попасть из вершины 4 через одну промежуточную вершину. Таких вершин нет, поэтому алгоритм ищет вершины, в которые можно попасть из вершины 4 через две промежуточных вершины. Таких вершин также не существует. Алгоритм переходит к поиску вершин, в которые можно попасть из вершины 4 через три промежуточных вершины. Таких вершин не существует, поэтому алгоритм прекращает работу, поскольку через четыре промежуточных вершины переходить куда-либо бессмысленно – будет осуществлен возврат в исходную вершину.

Больше вершин нет, поэтому окончательный вид матриц выглядит так:
Первая матрица:

№ вершины	1	2	3	4
1	0	2	4	7
2	9	0	2	5
3	7	9	0	3
4	10000	10000	10000	0

---

Рисунок 2.28 – Вид первой матрицы (матрицы кратчайших расстояний) после работы алгоритма

Вторая матрица:

№ вершины	1	2	3	4
1	0	2	2	2
2	3	0	3	3
3	1	1	0	4
4	0	0	0	0

Рисунок 2.29 – Вид второй матрицы (матрицы промежуточных вершин) после работы алгоритма

Покажем, как записывается кратчайший путь с помощью второй матрицы. Пусть требуется записать путь из вершины 1 в вершину 4. Сначала просматривается поле [1,4], где находится номер вершины 2, значит нужно идти в вершину 2. Далее, проверяется поле [2,4], куда надо идти из вершины 2, чтобы попасть в вершину 4. В этом поле записана вершина 3, значит, из вершины 2 идём в вершину 3. Далее проверяется поле [3,4], там находится номер вершины 4, значит, осуществляется переход в вершину 4. Далее рассматривается поле [4,4], и алгоритм прекращает выстраивание пути. Таким образом, путь с минимальными затратами из вершины 1 в вершину 4 проходит через следующие вершины:

1-2-3-4.

Результаты работы программы:

Кратчайший путь из вершины 1 в вершину 2: 1-2;

Кратчайший путь из вершины 1 в вершину 3: 1-2-3;

КП из вершины 1 в 4: 1-2-3-4;

КП из вершины 2 в 1: 2-3-1;

КП из вершины 2 в 3: 2-3;

КП из вершины 2 в 4: 2-3-4;

КП из вершины 3 в 1: 3-1;

КП из вершины 3 в 2: 3-1-2;

КП из вершины 3 в 4: 3-4.

3. 1   2   3   4   5   6   7

---