Данный задача известна как «Задача о коммивояжере». Для определения контура наименьшей длинны мы будем использовать исходную матрицу весов. Будет совершен перебор всех начальных вершин, начиная с первой, заканчивая десятой. Из всех вариантов маршрутов определим маршрут минимальной длинны, причем на каждом шаге будет включаться ближайший узел не использованный ранее:
№
Маршрут
∑
1 – 2 – 3 – 7 – 10 – 9 – 8– 5 – 6 – 4 – 1
2 – 1 – 5 – 8 – 9 – 10 – 7 – 3 – 6 – 4 – 2
3 – 2 – 4 – 1 – 7 – 10 – 9 – 8 – 5 – 6 – 3
4 – 1 – 5 – 6 – 8 – 9 – 10 – 7 – 3 – 2 – 4
5 – 1 – 4 – 2 – 3 – 6 – 7 – 10 – 9 – 8 – 5
6 – 4 – 2 – 3 – 7 – 10 – 9 – 8 – 1 – 5 – 6
7 – 1 – 5 – 8 – 10 – 9 – 6 – 4 – 2 – 3 – 7
8 – 1 – 4 – 2 – 3 – 7 – 10 – 9 – 6 – 5 – 8
9 – 6 – 5 – 1 – 4 – 2 – 3 – 7 – 10 – 8 – 9
10 – 8 – 5 – 1 – 4 – 2 – 3 – 7 – 6 – 9 – 10
Из полученных результатов можно видеть, что контур наименьшей длинны это контур под номером 1, его суммарная протяженность наименьшая.
Данный контур необходимо нанести на найденное ранее дерево.
Изобразим полученный контур:
Наложим полученный контур на ранее полученное дерево:
Мы получили сеть абонентского доступа типа кольцо + дерево минимальной длинны.
Контрольные вопросы
4.2.1 В чем заключается «задача коммивояжера»?
«Задачей коммивояжера» является сформировать контур включающий в себя все вершины представленного графа минимальной длинны.
4.2.2 Что является точным решение «задачи коммивояжера»?
Оптимальным для решения данной задачи является гамильтонов цикл наименьшей длинны.
4.2.3 Какой контур называется гамильтоновым циклом?
Контур, включающий в себя каждую вершину графа ровно один раз, называется гамильтоновым контуром (или гамильтоновым циклом).
4.2.4 Что называется эвристикой? Какие алгоритмы относятся к эвристическим?
В широком смысле эвристика - раздел науки, раскрывающий природу мышления человека, его методы решения различных задач. Эвристика основана на методике логического выведения гипотез и приводит к успешному результату в тех случаях, когда имеется опыт решения подобных. Алгоритмы, в которых присутствует логическое выведение гипотез – можно считать эвристическими алгоритмами.
4.2.5 Сформулируйте достоинства и недостатки точных и эвристических алгоритмов.
При использовании точных алгоритмов мы гарантировано получаем решение, а при использовании эвристических алгоритмов мы может там и не получить нужный нам результат.
5. Построение маршрутных матриц
Для построения маршрутных таблиц нам необходимо будет воспользоваться двумя алгоритмами. Алгоритм Дейкстры позволит нам построить кратчайшие пути из заданной вершины во все остальные. Другой алгоритм – построение «ярусного дерева», построение путей от некоторой заданной вершины к остальным вершинам графа.
Нахождение кратчайшего пути в связывающей сети
В данной части для каждой вершине будет соответствовать свой граф, на котором будет изображены кратчайшие пути для исходной вершины к остальным.
