Потрібно знайти оптимальну кільцеву структуру трас, з'єднують усі станції.
Математична постановка задачі. Заданий граф G=(X, U), де X - безліч вершин, в яких закінчуються ситуаційні траси; U - безліч ребер, відповідних ділянкам ситуаційних трас.
Х? ? Х - підмножина вершин, в яких розташовані телефонні станції. Lij - довжина ділянки траси uij. Потрібно знайти цикл С в графі G, що проходить по всіх вершин безлічі Х? і має мінімальну довжину:.
Рис 5.2.1 Структура ситуаційних трас
Аналіз алгоритмів
Розглянемо задачу, коли Х? =Х. У цьому випадку потрібно побудувати кільце, що проходить по всіх вершин, тобто, припускаємо, що у всіх вершинах розташовані станції. Ця задача відома в теорії графів як «Завдання комівояжера». Вона належить класу NP - важких завдань, для яких не існує точних ефективних алгоритмів. Тому завдання вирішують наближеними, евристичними алгоритмами з обчисленням нижньої і верхньої оцінок рішення.
У разі Х? ? Х наше завдання ще більш ускладнюється. Опишемо метод, за допомогою якого вона може бути зведена до «Завданню комівояжера».
Побудова аппроксимирующего графа
Крок 1. Обчислити за алгоритмом Дейкстри найкоротші шляхи між усіма парами вершин з безлічі Х?. Алгоритм реалізується наступним чином:
- вибираємо вершину (РАТС) і знаходимо вершини, суміжні з нею. Присвоюємо кожної знайденої вершині пару чисел, що складається з номера кореневої (обраної) і довжини відповідного ребра. Для решти вершин графа зіставляють пару (0,?);
- з безлічі невідмічених вершин знайдемо вершину з мінімальною вагою, включаємо її в дерево найкоротших шляхів і відзначаємо її. Далі вже для знову зазначеної вершини знаходимо суміжні з нею. Знайденої вершині (суміжній) присвоюємо вага мінімальний їх двох можливих: або вже існуючий, або вага, отриманий з суми довжини ребра з вагою попередньої вершини; так необхідно повторювати до тих пір, поки вершини не будуть переглянуті і відзначені.
Крок 2. Побудувати повний граф G? =(X?, U?), У якого безліч вершин збігається з безліччю вершин X?. Безліч ребер з'єднує дві пари вершин. Для кожного ребра u ij покласти його вага рівним довжині найкоротшого шляху з Х i в Х j у вихідному графі G, отриманому на кроці 1.
Крок 3. На отриманому графі можна вирішувати задачу комівояжера, т. е. знайти цикл мінімальної ваги, проходить по всіх вершин X?.
Крок 4. Отримавши структуру циклу в графі G? , Виділити найкоротші шляхи в графі G, відповідні ребрам отриманого циклу.
Методи рішення «Завдання комівояжера».
Розглянемо алгоритм отримання верхньої та нижньої оцінок для «Завдання Комівояжера» (ЗК).
Нижньої оцінкою для ЗК є рішення, отримане за допомогою алгоритму Прима-Краскала, в результаті якого будується Найкоротша Остовне дерево (КОД). Довжина шуканого циклу не може бути менше сумарної ваги КОД.
Верхня оцінка циклу в ЗК може бути отримана з використанням стратегії «йди у найближчий». Опишемо докладніше цей алгоритм.
Крок 1. Вибрати вихідну вершину і вважати її поточної вершиною споруджуваного нового циклу.
Крок 2. Знайти найближчу вершину до поточної вершині щодо довжини ребра і зробити її поточною. Збільшити вагу циклу на довжину ребра.
Крок 3. Якщо не всі вершини включені в цикл, то крок 2 повторюється. Якщо в цикл включені всі вершини графа, то запам'ятати сумарна вага ребер, включених в цикл. Якщо вага отриманого циклу менше попереднього рішення, вважати його найкращим.
Крок 4. Якщо не всі вершини графа переглянуті як вихідні вершини циклів, то перейти на крок 1, інакше цикл, що має мінімальну вагу є верхньою оцінкою для ЗК.
Крок 5. Отримане кільце мінімальної довжини вкласти в структуру ситуаційних трас первинної мережі. При цьому гілки кільця не повинні містити елементи структури ситуаційних трас більше одного разу.
Використовуючи дані завдання на виконання розрахунково-графічного завдання і викладену методику, необхідно визначити довжину оптимального кільця за структурою ситуаційних трас міста.
Обчислимо за алгоритмом Дейкстри найкоротші шляхи між усіма парами АТС.
Малюнок 5.2.2 - Найкоротші шляху від РАТС 1 і РАТС 2
Малюнок 5.2.3 - Найкоротші шляху від РАТС 3 і РАТС 4
Малюнок 5.2.4 - Найкоротші шляху від АМТС
Таблиця 5.2.1. Довжина найкоротших шляхів
РАТС 1РАТС 2РАТС 3РАТС 4АМТСРАТС...
