Головна

Шляхи і цикли Гамільтона. алгоритм Літтла

  1. I. РОЗРОБКА АЛГОРИТМІВ. ГРАФІЧНЕ ЗОБРАЖЕННЯ (БЛОК-СХЕМИ) І СЛОВЕСНА ЗАПИС АЛГОРИТМІВ
  2. IV.1. Одноразові ітераційні цикли
  3. АЛГОРИТМ 10
  4. алгоритм DES
  5. алгоритм RSA
  6. Алгоритм автоматичного формування парних симетричних ключів шифрування-дешифрування відкритих повідомлень на робочих станціях абонентів корпоративної системи.
  7. Алгоритм відра маркерів

У 1857 році математик Вільям Роуен Гамільтон придумав гру. Існує кілька версій того, як це сталося. За однією з версій він описав гру в листі до друга. Відповідно до іншої, він дійсно винайшов гру і продав її виробнику іграшок. У будь-якому випадку, ця гра включала додекаедр, тобто правильний багатогранник, 12 граней яких представляли собою рівні правильні п'ятикутник. У кожному з 20 кутів, або вершин тіла, просвердлюють дірочка, в яку вставлявся кілочок, який зображав місто. Використовуючи мотузку, потрібно знайти шлях через міста, відвідавши кожне місто один раз, і повернутися в початковий місто.

У цьому випадку проблема зводиться до знаходження в графі циклу, що проходить через кожну вершину тільки один раз, виключаючи початкову. Звідси будь-який цикл, що володіє такою властивістю, називається Гамільтона циклом. Цей цикл в деякому сенсі протилежний ейлерову циклу, який проходить через всі ребра тільки один раз. До певного моменту обидва циклу можуть здатися схожими, але насправді цикл Гамільтона набагато складніше.

нехай  - Граф.

визначення 4.4. Гамильтонов шлях - Це простий шлях, який проходить через кожну вершину графа . Гамильтонов цикл - Це простий цикл, який проходить через кожну вершину графа .

До теперішнього часу нікому не вдалося встановити необхідні і достатні умови існування у графа Гамільтона циклу. Проте доведено ряд теорем, в яких наводяться деякі умови існування у графа Гамільтона циклу.

Розглянемо одну з задач, в якій потрібно знайти у зваженому графі гамільтонів цикл мінімальної довжини. Наведемо формулювання завдання і алгоритм її вирішення.

Завдання комівояжера (або бродячого торговця)

Постановка завдання: комівояжер повинен так скласти свій маршрут руху, щоб відвідати один і тільки один раз кожен з  міст і повернутися в початковий пункт. Його маршрут повинен мінімізувати сумарну довжину пройденого шляху.

Після текстової постановки задачі за допомогою математичного мови (символів, функцій, рівнянь або нерівностей і т.д.) побудуємо математичну модель задачі. Суворе поняття «математична модель» введемо в наступному розділі «Елементи математичного моделювання», на даному етапі будемо оперувати даними поняттям, як деяким математичним «перекладом» текстового умови.

Отже, нехай  - Матриця відстаней між містами. Для складання математичної моделі задачі позначимо через змінні  факт переїзду комівояжером з міста  в місто  . Оскільки переїзд з одного міста в інший може здійснюватися тільки один раз, то змінні  повинні приймати тільки два значення: 1 або 0, тобто булеві значення. Таким чином:

Математична модель задачі має наступний вигляд:

 (4.1)

 (4.2)

 (4.3)

.

Система обмежень (4.2) забезпечує побудова маршруту, при якому комівояжер в'їжджає в кожне місто тільки один раз, а система (4.3) - маршруту, при якому він виїжджає з кожного міста тільки один раз. Усунення підциклів і отримання маршруту, що утворює повний цикл, що включає всі міста, досягається при додаванні системи обмежень:

 (4.4)

де всі змінні и  можуть приймати довільні дійсні значення.



Попередня   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   Наступна

Подання графів в комп'ютері | Приклад 1.6. | дерева | Приклад 2.1. | остовне дерева | Приклад 2.2. | Алгоритм Краскала і алгоритм Прима | алгоритм Краскала | алгоритм Прима | алгоритм Дейкстри |

© 2016-2022  um.co.ua - учбові матеріали та реферати