Лекції >> Програмування, комп’ютери і кібернетика >> Переборні задачі

Задача комівояжера 

Деякі задачі розв’язують, перебираючи можливі розв’язки і перевіряючи, яке з них істина. При цьому треба подбати, щоб істинний розв’язок був серед можливих, інакше його не знайти. Якщо невідомий інший спосіб ро в’язку задачі, її називають переборною.

Класичним прикладом переборної задачі служить задача комівояжера. Дано множину з N міст, відстані між який відомі. У якому порядку повинний відвідати їх комівояжер, заїжджаючи в кожне місто лише один раз, щоб загальний пройдений шлях був найкоротшим?

Можливими розв’язками тут є перестановки з N міст. З них потрібно вибрати ту, що дасть найменшу сумарну довжину маршруту. Перше, що потрібно зробити, розв’язуючи задачу комівояжера, це організувати перебір перестановок. Занумеруємо міста числами від 1 до N. Всі пере оротшим?

Можливими розв’язками тут є перестановки з N міст. З них потрібно вибрати ту, що дасть найменшу сумарну довжину маршруту. Перше, що потрібно зробити, розв’язуючи задачу комівояжера, це організувати перебір перестановок. Занумеруємо міста числами від 1 до N. Всі перестановки можна одержати, обираючи з множини [1..N] один елемент усілякими способами і приєднуючи до нього по черзі перестановки з  елементів , що залишилися. Це рекурсивний алгоритм, тому що для одержання побудови перестановок із N елементів він потребує  перестановку з N-1 елемента. Додамо, що єдина перестановка з одного елемента - це самий елемент.

Запрограмуємо одержання перестановок у вигляді рекурсивної процедури. Множину елементів, що переставляються, зробимо параметром процедури. Іншим параметром буде позиція перестановки, що заповнюється даним викликом процедури. Всі становки можна одержати, обираючи з множини [1..N] один елемент усілякими способами і приєднуючи до нього по черзі перестановки з  елементів , що залишилися. Це рекурсивний алгоритм, тому що для одержання побудови перестановок із N елементів він потребує  перестановку з N-1 елемента. Додамо, що єдина перестановка з одного елемента - це самий елемент.

Запрограмуємо одержання перестановок у вигляді рекурсивної процедури. Множину елементів, що переставляються, зробимо параметром процедури. Іншим параметром буде позиція перестановки, що заповнюється даним викликом процедури. Всі перестановки будемо по черзі будувати в зовнішньому масиві з N цілих чисел.

Програма одержання перестановок з множини чисел [1..N]

Program Perebor;

Const

  N=5;

Type

  IntSet = Set Of 1..N;

Var

  A: Array [1..N] Of Integer;

о, що єдина перестановка з одного елемента - це самий елемент.

Запрограмуємо одержання перестановок у вигляді рекурсивної процедури. Множину елементів, що переставляються, зробимо параметром процедури. Іншим параметром буде позиція перестановки, що заповнюється даним викликом процедури. Всі перестановки будемо по черзі будувати в зовнішньому масиві з N цілих чисел.

Програма одержання перестановок з множини чисел [1..N]

Program Perebor;

Const

  N=5;

Type

  IntSet = Set Of 1..N;

Var

  A: Array [1..N] Of Integer;

Procedure Perest (S: IntSet; K: Integer);

Var

  I: Integer;

Begin

  For I:=1 To N Do

    If I In S Then

      Begin

        A[K]:=I;

        Perest(S-[I], K+1)

      End

End;

Begin

  Perest([1..N], 1);

End.

Ця програма тільки будує перестановки в масиві А і більше нічого не робить, навіть не виводить їх на екран. Перестановка готова, коли S=[].

Доповнимо процедуру Perest підрахунком довжини маршруту, заданого перестановкою, і вибором самого короткого з маршрутів. Для схову найкоротшого з побудованих маршрутів і його довжини скористаємося зовнішніми змінними Amin і Lmin. Відстані між містами утримуються в двовимірному масиві Dist.

Попробуйте самостійно розв’язати задачу комівояжера.

Метод гілок і меж

Головна складність переборних задач у тому, що кількість можливих розв’язків буває в буквальному значенні безмежним. Порахуйте, скільки існує перестановок, скажемо, із 50 міст. Навіть якщо комп'ютер зможе опрацьовувати по мільйону перестановок у секунду то на це пішло б багато часу. Як же розв’язують такі задачі? Один із підходів полягає в тому, щоб знайти таку стратегію перебору й аналізу можливих вирішень, коли можна відкидати їх цілими групами, не займаючись перевіркою кожного окремо.

Наприклад, якщо для комівояжера знайдений маршрут довжиною Lrnin, а заїзд до перших K міст чергового варіанта вже дає довжину, більшу, ніж Lrnin, то вже нема чого перевіряти не тільки цей варіант, але і всі маршрути, що збігаються з ним у перших K містах.

Перебір маршрутів можна розглядати як прямування по гілках дерев, а відкидання маршрутів - як відсікання гілок дерева на межі досягнення ними вже знайденої мінімальної довжини маршруту. Цим пояснюється назва методу гілок і меж.

Метод гілок і меж не є алгоритмом вирішення переборних задач. Його можна вважати ідеєю вирішення, що потребує творчого підходу для кожної оригінальної задачі.

Схожі матеріали
05.10.2012 Введення та виведення даних, розробки та опису лінійних програм.
20.12.2011 Pascal - лабораторні роботи - для студентів III-го курсу (лекції Ляшенко Б.М.)
12.12.2010 Робота з підпрограмами
12.12.2010 Робота з рядковими та символьними величинами.
12.12.2010 Робота з циклічними програмами
12.12.2010 Робота з масивами даних.
12.12.2010 Розробка та описання програм з розгалуженнями
12.12.2010 Початки програмування
12.12.2010 Етапи розв’язання задач з використанням ЕОМ
12.12.2010 Поняття про алгоритм

Тести даної категорії
12.12.2010 ПОЧАТКИ АЛГОРИТМІЗАЦІЇ. ВСТУП ДО ПРОГРАМУВАННЯ

Останні створені тести
16.11.2015 Олімпійські ігри Стародавньої Греції. Відродження олімпійських ігор. Олімпійський рух сучасності.
28.10.2015 British Writers. Тест для студентів 4 курсу ННІ педагогіки
27.10.2015 The Passive Voice. Тест для студентів 2 курсу ННІ педагогіки
27.10.2015 Articles. Тест для студентів 1 курсу неспеціальних факультетів
27.10.2015 The Active Voice. Тест для студентів 2 курсу ННІ педагогіки
08.10.2014 INTEL
22.10.2012 Цивільний захист
26.09.2012 Мовнокомунікативна компетентність. Орфографічна складова
21.09.2012 OC Windows
31.05.2012 Lexikalisch-grammatischer Test. Тест для студентів 1 курсу неспеціальних факультетів.
Рекомендовані лекції
12.12.2010 Етапи розв’язання задач з використанням ЕОМ
09.12.2014 Лекції з ЦЗ для студентів 6-х курсів денної форми навчання
22.03.2016 ОС та СП. Тема 5. Безпека. Тези
22.02.2016 ОС та СП. Тема 2. Процеси та потоки. Слайди
12.12.2010 Рекурсія
12.12.2010 Робота з рядковими та символьними величинами
12.12.2010 Структура та синтаксис програм
12.12.2010 Циклічні програми
13.11.2014 MICROSOFT OFFICE. СКЛАД, ПРИЗНАЧЕННЯ, ОСНОВНІ ПРОГРАМИ-ДОДАТКА
22.02.2016 ОС та СП. Тема 2. Процеси та потоки. Тези