Опис алгоритму методу

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

Алгоритм програми

1. Зчитати кількість міст та їх матрицю відстаней

2. Довжина найкоротшого шляху нескінченність

3. Виконати пункт 4 з такими параметрами: номер поточного міста – , кількість міст в шляху – , довжина поточного шляху .

4. Додати наступне місто до шляху, або повернутися у попереднє місто:

   1. Якщо довжина поточного шляху менша за довжину запам’ятованого найкоротшого шляху , то:

      1. Якщо кількість міст в шляху дорівнює загальній кількості міст, то:

         1. Додати останню вершину до шляху

         2. Додати до довжини шляху відстань від даного міста до нульового

         3. Якщо довжина шляху менша за довжину запам’ятованого найкоротшого шляху , то:

            1. Запам’ятати вартість даного найкоротшого шляху

            2. Запам’ятати даний шлях

      2. Інакше якщо ще не всі міста пройдені, то:

         1. Помітити дане місто пройденим

         2. Додати дане місто до шляху

         3. Для всіх міст виконати:

            1. Якщо -те місто ще не пройдено, то:

               1. Виконати пункт 4 з такими параметрами: номер поточного міста – , кількість міст в шляху – поточна кількість міст , довжина шляху: довжина поточного шляху відстань між даним містом та -тим.

         4. Помітити дане місто не пройденим.

5. Вивести результати на екран:

   1. Якщо довжина найкоротшого шляху нескінченність, то:

      1. Вивести повідомлення, що шляху обходу всіх міст по одному разу не існує.

   2. Інакше:

      1. Вивести довжину найкоротшого шляху на екран

      2. Вивести всі елементи найкоротшого шляху на екран

Відеокопії екрана

Аналіз достовірності результатів

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

Задача про парламент

Умова задачі [2]

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

Допоможіть жителям організувати такий, якомога менший парламент, в якому будуть представлені всі партії.