Синтез сети междугородней связи
3.1Определить контур наименьшей длины, который объединяет узловые пункты телекоммуникационной сети в транспортное кольцо.
Дано:размещение пунктов (n = 10), линейно-кабельной канализации, представлено матрицей весов ребер графа, который отражает сеть. Весовые характеристики ребер отвечают расстояниям в километрах линейно- кабельных сооружений между пунктами сети. В качестве указанной матрицы используйте матрицу весов, полученную при выполнении задания 1.
Решением задачи является определение маршрута наименьшей длины. Контур, который включает каждую вершину графа G(N,V) только 1 раз, называется гамильтоновым контуром (или гамильтоновым циклом).
В каждой перестановке можно поставить в соответствие, определенное число, которое определяет длину маршрута как сумму ребер цикла, который соединяет все 10 вершин графа G(N,V). Воспользовавшись графом G (рис 1.1) определим длину каждого маршрута и выбираем наименьшую.
Рисунок 3.1 – график цикла наименьшей длины с первой вершины в первую.
Рисунок 3.1 – график цикла с второй вершины в вторую.
Рисунок 3.1 – график цикла с третей вершины в третью.
Рисунок 3.1 – график цикла с четвертой вершины в четвертую.
Рисунок 3.1 – график цикла с пятой вершины в пятую.
Рисунок 3.1 – график цикла с шестой вершины в шестую.
Рисунок 3.1 – график цикла с седьмой вершины в седьмую
Рисунок 3.1 – график цикла с восьмой вершины в восьмую.
Рисунок 3.1 – график цикла с девятой вершины в девятую.
Рисунок 3.1 – график цикла десятой вершины в десятую.
3.2Дать письменные ответы на следующие ключевые вопросы:
1. В чем заключается «задача коммивояжера»?
2. Что является точным решением «задача коммивояжера»?
3. Какой контур называется гамильтоновым циклом?
4. Что называется эвристикой? Какие алгоритмы относятся к эвристическим?
5. Сформируйте достоинства и недостатки точных и эвристических алгоритмов.
Ответы:
1. Задачей коммивояжера является поиск маршрута наименьшей длины.
2. Точным решением «задача коммивояжера» является гамильтонов цикл наименьшей
длины.
3. Контур, включающий каждую вершину графа равно один раз, называется гамильтоновым контуром (или гамильтоновым циклом).
4. Эвристика – это основанное на опыте правило, стратегия, прием или иное средство, существенно ограничивающее поиск решения сложных задач. К Эвристике относятся приближенные алгоритмы.
5. Точные алгоритмы всегда гарантируют нахождение оптимального решения. Однако точные алгоритмы, как правило, достаточно трудоемкие с вычислительной точки зрения. Эвристические алгоритмы обеспечивают быстрое получение решения с принятой для практики точностью. Такие алгоритмы строятся с использованием рациональных, с точки зрения логики человека, правил выполнения вычислений. Эвристические алгоритмы, как правило, позволяют найти решение близкое к оптимальному.