p align="justify"> Вихідними даними для алгоритму є матриця відстаней S.
Алгоритм:
) Приведення матриці відстаней S по рядках і стовпцях та визначення нижньої оцінки безлічі варіантів гамільтонових контурів.
В
де ci і qi - елементи приведення по рядках і стовпчиках відповідно,
- довжина найкоротшого гамільтонового контуру в досліджуваному безлічі варіантів.
) Визначення оцінок на включення до шуканий гамільтонів контур для всіх В«нульовихВ» дуг.
) Включення дуг з максимальною оцінкою в рішення.
При цьому необхідно дотримуватися таких правил:
В· у вирішення включаються дуги з максимальними рівними оцінками;
В· дуги не повинні утворювати приватних контурів;
В· дуги повинні відповідати обраному напрямку обходу.
4) Корекція матриці S, яка полягає в викреслення рядків з номерами i і стовпців j відповідно з дугами, включеними до рішення.
) Гамильтонов контур знайдено? Якщо ні - перехід до пункту 6, якщо так - перехід до пункту 8. p> 6) Визначення підмножини гамільтонових контурів з мінімальною оцінкою.
) Перехід до пункту 1.
) Гамильтонов контур оптимальний? Якщо ні - перехід до пункту 6. Якщо так - кінець алгоритму. br/>
.3 Рішення завдання за варіантом
Задані координати отворів на друкованій платі (малюнок 10). Необхідно знайти таку траєкторію обходу всіх цих отворів при роботі свердлильного верстата, щоб її довжина була мінімальною. За направлення обходу контуру приймемо напрямок за годинниковою стрілкою. На підставі технологічної карти визначимо відстані між центрами отворів в міліметрах і складемо матрицю відстаней S.
В
Рисунок 9 - Технологічна карта
Матриця відстаней S буде мати вигляд:
-й крок: наведемо отриману матрицю по рядках. Для цього з кожного рядка віднімаємо її мінімальний елемент. Знайдемо суму мінімальних для кожного рядка елементів сi. br/>
Наведемо отриману матрицю по стовпцях шляхом вирахування з кожного шпальти його мінімального елемента. Знайдемо суму мінімальних для кожного стовпця елементів qi. br/>В
Тепер отримаємо уточнену оцінку знизу для гамільтонових контурів:
В
Знайдемо збільшення оцінок для дуг, у яких, для цього складемо найменші значення в i-му рядку і j-му стовпці:
В
Максимальне збільшення оцінки, рівне 22, має дуга (4,2). Включаємо до рішення дугу (4,2), так як вона задовольняє обраному обходу. Викреслюємо четвертий рядок і другий стовпець. Отримуємо матрицю відстаней, в якій накладена заборона на дугу (2,4). P
-й крок: Отриману матрицю аналогічно наводимо по рядках:
