Суровцев 23-пр1_b91f677e-4723-4ea5-9eb6-49c40ac84f36

1.

Введение
В рамках данного проекта создал граф на
основе карты из компьютерной игры The
Elder Scrolls III: Morrowind. В графе
вершинами являются поселения, а ребрами
— маршруты быстрого перемещения
между этими населёнными пунктами. Эти
маршруты включают поездки на силт
страйдерах, а также путешествия на
кораблях. Взвешенные ребра представляют
собой затраченные часы на поездку, что
позволяет более точно оценить время
перемещения между локациями.

2.

A1
8
5
A2
2
5 3
3
A1: Дагон Фел
A2: Хуул
A3: Маар Ган
A4: Гнисис
A5: Альд'рун
A6: Балмора
A7: Гнаар Мок
A8: Хла Оуд
A9: Сейда Нин
A10: Вивек
A11: Эбангард
A12: Суран
A13: Молаг Мар
A14: Тель Бранора
A15: Садрит Мора
A16: Тель Арун
A17: Тель мора
A18: Вос
7
10
A17
A18
5
A3
3
4
A4
9
4 54
2
4
A5
A16
A15
4
A7
4
11
A6
3
A8
8
5
4
4
A9
5
5
2
A12
1
4
A10
1
A11
5
6
3
A13
10
11
2
A14

3.

Весовая матрица графа:

4.

Минимальное остовное дерево:

5.

Кратчайший маршрут:

6.

Обход графа: в глубину

7.

Обход графа: в ширину

8.

Задача коммивояжёра:
алгоритм ближайшего
соседа
В результате маршрута A6-A12-A13-A10-A9 получаем длину
5+3+4+2+3=17

9.

Задача коммивояжёра:
Построим минимальное
остовное дерево
Минимальное остовное дерево состоит рёбер A12-A10-A13-A6 и
имеет вес 8

10.

Задача коммивояжёра:
Построим минимальное
остовное дерево
Складываем минимальный вес остовного дерево и сумму двух кратчайших
рёбер удалённой вершин:
8+3+2=13
Получаем, что для приведение графа: 13 < L < 17