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

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

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

1. Зчитати розмір та матрицю лабіринту.

2. Знайти початок та вихід з лабіринту:

   1. Для всіх клітинок лабіринту:

      1. Якщо значення клітинки дорівнює , то запам’ятати координати цієї клітинки, як координати входу лабіринту

      2. Якщо значення клітинки дорівнює , то запам’ятати координати цієї клітинки, як координати виходу з лабіринту

3. Виконати пункт 4 для координат входу в лабіринт

4. Перейти з даної клітинки на сусідню, або якщо перейти не можна, то повернутися назад:

   1. Якщо дана клітинка це вихід:

      1. Позначити, що ми знайшли розв’язок

   2. Інакше:

      1. Якщо можна перейти вгору і ще не було виконано переходу на поточному кроці, то:

         1. Запам’ятати що ми виконали перехід на поточному кроці

         2. Позначити верхню клітинку пройденою

         3. Додати верхню клітинку до шляху

         4. Виконати пункт 4 для верхньої клітинки

      2. Якщо можна перейти вліво і ще не було виконано переходу на поточному кроці, то:

         1. Запам’ятати що ми виконали перехід на поточному кроці

         2. Позначити ліву клітинку пройденою

         3. Додати ліву клітинку до шляху

         4. Виконати пункт 4 для лівої клітинки

      3. Якщо можна перейти вниз і ще не було виконано переходу на поточному кроці, то:

         1. Запам’ятати що ми виконали перехід на поточному кроці

         2. Позначити нижню клітинку пройденою

         3. Додати нижню клітинку до шляху

         4. Виконати пункт 4 для нижньої клітинки

      4. Якщо можна перейти вправо і ще не було виконано переходу на поточному кроці, то:

         1. Запам’ятати що ми виконали перехід на поточному кроці

         2. Позначити праву клітинку пройденою

         3. Додати праву клітинку до шляху

         4. Виконати пункт 4 для правої клітинки

      5. Якщо на поточному кроці не було знайдено клітинку на яку можна перейти, то:

         1. Видалити з шляху останній крок

         2. Виконати пункт 4 для попереднього кроку шляху

5. Якщо вихід з лабіринту знайдений, то:

   1. Позначити знайдений шлях на матриці лабіринту

      1. Для кожного елементу знайденого шляху, клітинку позначити цифрою 4.

   2. Вивести лабіринт на екран.

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

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

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

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

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

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

Вхідні та вихідні тести

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

Програма виводить довжину мінімального шляху комівояжера та сам шлях на екран.

Приклад 1:

Кількість міст:

Матриця відстаней між містами:

-1 19 11 14 6 11 8

12 -1 14 9 1 13 12

5 1 -1 2 18 17 14

11 3 15 -1 1 13 2

19 6 20 6 -1 8 5

5 19 19 2 4 -1 16

5 1 3 7 1 4 -1

Довжина мінімального шляху комівояжера:

Шлях комівояжера:

Приклад 2:

Кількість міст:

Матриця відстаней між містами:

-1 10 22 13 17 18 20 29 28 30

10 -1 13 9 22 17 16 22 27 32

22 13 -1 13 30 20 13 13 25 35

13 9 13 -1 17 9 8 15 19 25

17 22 30 17 -1 10 19 27 18 13

18 17 20 9 10 -1 8 17 12 15

20 17 13 8 19 8 -1 9 12 21

29 22 13 15 27 17 9 -1 16 29

28 27 25 19 18 12 12 16 -1 13

30 32 35 25 13 15 21 29 13 -1

Довжина мінімального шляху комівояжера:

Шлях комівояжера:

Приклад 3:

Кількість міст:

Матриця відстаней між містами:

-1 32 19 33 22 41 18 15 16 31

32 -1 51 58 27 42 35 18 17 34

19 51 -1 23 35 49 26 34 35 41

33 58 23 -1 33 37 23 46 46 32

22 27 35 33 -1 19 10 23 23 9

41 42 49 37 19 -1 24 42 42 10

18 35 26 23 10 24 -1 25 25 14

15 18 34 46 23 42 25 -1 1 32

16 17 35 46 23 42 25 1 -1 32

31 34 41 32 9 10 14 32 32 -1

Довжина мінімального шляху комівояжера:

Шлях комівояжера: