Бектрекінг (backtracking) - це алгоритм, який використовується для розв'язання комбінаторних задач, таких як головоломки, задачі про перебору комбінацій, складання графів та інші. Його основна ідея полягає в тому, щоб систематично перебирати всі можливі варіанти розв'язку задачі, відстежуючи і виправляючи помилки по мірі їх виникнення.
Основна концепція полягає в тому, щоб спробувати кожен можливий варіант розв'язку задачі, рухаючись по дереву рішень. Якщо на якому-небудь етапі виявляється, що поточний варіант не може бути продовжений до правильного розв'язку, алгоритм повертається назад (backtracks) і спробує інший варіант.
-
Вибір варіанту: Обирається наступний можливий варіант розв'язку задачі.
-
Перевірка: Перевіряється, чи є обраний варіант допустимим та чи приводить він до розв'язку задачі.
-
Виконання: Якщо вибраний варіант прийнятний, він виконується, і алгоритм рухається далі глибше в пошуках розв'язку.
-
Повернення назад (backtrack): Якщо вибраний варіант не призводить до розв'язку, або виявляється, що він не може бути продовжений, алгоритм повертається назад до попереднього етапу вибору і обирає інший варіант.
Цикл вибору, перевірки, виконання та повернення назад продовжується до тих пір, поки не буде знайдено розв'язок або поки всі можливі комбінації не будуть перевірені.
Бектрекінг є потужним методом для розв'язання комбінаторних задач і використовується в багатьох областях, таких як штучний інтелект, оптимізація, криптографія та багато інших.
Правила:
- поле 9 на 9 треба заповнити цифрами від 1 до 9
- цифри не можуть повторюватись у стовпцях
- цифри не можуть повторюватись у колонках
- цифри не можуть повторюватись у блоках 3 на 3
Для розв'язування судоку було створено два алгоритми. Складність кожного з них - 9^(n^2). Перший алгоритм - сухий перебір. Для кожної порожньої клітинки перебирає усі варіанти, що не порушують правила і за допомогою бектрекінгу заповнюємо усі клітинки. Бектрекінг у першому алгоритмі реалізовано через рекурсію, де функція повертатиме False, якщо для даної цифри не існує розв'язків. У такому випадку клітинка перевизначається на наступне число, яке не порушує правила. Якщо для будь якої клітинки не існує правильного числа, виведеться "No resut exists!". Якщо надане поле не дотримується правил, повертається "The field is invalid!".
Для реалізації другого алгоритму було прийнято рішення відштовхуватись від людського способу розв'язування судоку, що означатиме заповнення лише тих клітинок, у які за правилами підходить лише одна цифра. Для цього у другому алгоритмі реалізовано функцію logical_fill, яка поступово спрощує судоку, тим самим зменшуючи кількість потрібних ітерацій на наступному етапі бектрекінгу, який заповнює решту клітинок, для яких не знайшлось однозначного результату. Аналогічно до першого алгоритму, при наданні неправильного поля, функція поверне "The field is invalid!", та при відсутності розв'язку результатом буде "No resut exists!".
Після дослідження продуктивності, видно що перший алгоритм набагато швидше
Задача: Задача M-розфарбування (M-coloring) полягає в тому, щоб призначити кожному вузлу графа один із M кольорів таким чином, щоб жодні два сусідні вузли не мали однакового кольору. Якщо вдалося так розфарбувати весь граф, то граф називається M-розфарбованим.
на вхід дається -> (число вершин, число кольорів, ймовірність з'єднання) на вихід -> якщо можна розфарбувати, то малюнок як саме. якщо не вистачає кольорів - повідомлення, що не можна розфарбувати
-Функція is_valid: Ця функція перевіряє, чи може поточний вузол бути розфарбований певним кольором, порівнюючи його з коліром сусідів. Якщо хоча б один з сусідів має той самий колір, що і поточний вузол, функція повертає False, інакше - True.
-Функція coloring: Ця рекурсивна функція вирішує задачу розфарбування графа. Вона спробує призначити кожному вузлу кольори, використовуючи метод бектрекінгу. Якщо вдалося розфарбувати всі вузли, функція повертає True, в іншому випадку - False.
-Функція run: Ця функція ініціалізує граф, додаючи до нього випадкові ребра з заданою ймовірністю. Потім вона викликає функцію coloring, щоб спробувати розфарбувати граф, та якщо це вдається, вона візуалізує результат за допомогою бібліотеки networkx та matplotlib. Якщо ж функція coloring повертає False, виводиться повідомлення про те, що рішення не існує.
-Змінні num_nodes, num_colors та probability: Вони визначають кількість вузлів у графі, кількість кольорів, якими можна розфарбувати граф, і ймовірність додавання кожного ребра між вузлами в графі відповідно. Ці значення можна змінювати в залежності від вимог задачі.
-Створення графу G: За допомогою бібліотеки NetworkX створюється граф з вузлами та випадково доданими ребрами на основі встановленої ймовірності.
-Виклик функції coloring: Викликається рекурсивна функція coloring, яка намагається розфарбувати граф. Якщо це вдається, тобто функція повертає True, то відбувається візуалізація графа за допомогою networkx.draw та matplotlib.pyplot.show. Якщо ж функція coloring повертає False, виводиться повідомлення про те, що рішення не існує.
складність алгоритму : O(num_colors * (num_colors ^ num_nodes))
У нас є 2 типи лабіринтів: звичайні і з телепортами
- Можливість читання макетів лабіринтів з текстових файлів.
- Використання алгоритму пошуку в глибину для знаходження шляху рішення.
- Візуалізація лабіринту та шляху рішення за допомогою Pygame.
Помістіть свої файли з макетами лабіринтів у директорію test_cases_simple.
Запустіть скрипт maze_solver.py: python maze_solver.py
Програма відобразить лабіринт та шлях рішення. Закрийте вікно, щоб вийти з програми.
Формат файлу з макетом лабіринту Макет лабіринту повинен бути визначений у текстовому файлі, де кожен символ представляє певний елемент:
"." або (пробіл) для порожніх клітин. "#" для стін. "?" для точки старту. "!" для кінцевої точки.
Початкова позиція на мапі, де розташований символ початку шляху, визначається і позначається як кореневий вузол дерева. Також знаходиться кінцева позиція, де знаходиться символ кінця шляху.
Починаючи з кореневого вузла, рекурсивно додаються дочірні вузли, які представляють допустимі сусідні позиції на мапі. Для кожної позиції обчислюються її допустимі сусіди (верх, низ, ліворуч, праворуч), і якщо вони не знаходяться в межах мапи або представляють собою перешкоду, вони не розглядаються. Якщо сусідня позиція ще не була відвідана, створюється новий вузол для цієї позиції і рекурсивно викликається побудова дерева для цієї нової позиції.
Після побудови дерева розпочинається рекурсивний пошук шляху від початкової позиції до кінцевої. Кожен раз, коли рекурсивно викликається функція пошуку шляху, вона перевіряє, чи поточна позиція вузла є кінцевою. Якщо так, шлях знайдено, і повертається список з позиціями вузлів, які утворюють шлях. Якщо поточна позиція не є кінцевою, функція рекурсивно викликається для кожного дочірнього вузла поточного вузла, доки не буде знайдено шлях або не будуть перевірені всі можливі напрямки.
Якщо шлях знайдено, повертається список з позиціями вузлів, які утворюють шлях від початку до кінця. Якщо шлях не знайдено (наприклад, якщо неможливо досягнути кінцеву позицію), повертається відповідне повідомлення.
Часова складність алгоритму залежить від кількості клітин на мапі та кількості можливих шляхів. Просторова складність алгоритму залежить від розміру дерева, що будується. Це може бути важливо для великих мап з великою кількістю можливих шляхів.
Також , ми вирішували кросворди, як наглядний приклад використання бектрекінгу ми вибрали задачу з розставленням 8 королев на шахматній дошці , адже це найочевидніша задача в якій потрібно використовувати бектрекінг . Щодо ідеї імплементації ми визначали чи місце на якому ми знаходимось є безпечним і ставили туди королеву. Бектрекінг є дуже ефективним для реалізації цієї задачі через , оскільки бектрекінг перевіряє кожен можливий варіант, він швидко виявляє та відкидає некоректні рішення, тобто ті, де королеви можуть атакувати одна одну , він відкидає зразу цілі гілки графа. Це дозволяє значно скоротити кількість перевірок та прискорити пошук правильного розв'язку.
Введіть розмір шахівниці (N x N) та кількість королев, які потрібно розмістити.
Програма знайде та відобразить всі можливі варіанти розміщення королев на шахівниці.
Кожен варіант розміщення королев представляється у вигляді шахівниці, де символ "♛" позначає королеву, а символ "_" позначає порожню клітину.
n!
Для кросвордів це також надзвичайно зручний та швидкий спосіб , через відкидання зразу неможливих варіантів. Щодо кросворду ми оприділились з форматом , де в нас є список слів і дошка на яку їх потрібно вставити. Основними проблемами з якими досить легко справитись через бектрекінг – це була обробка країв , визначення допустимих перетинів між словами та управління конфліктами. З управлінням конфліктами , тобто Якщо слова мають багато можливих перетинів, може виникнути конфлікт при виборі оптимального розміщення , можуть бути великі проблеми , якщо не використовувати бектрекінг, адже досить важко знайти алгоритм за яким можна це прорахувати.
В програмі потрібно ввести розмірність кросворду та слова, які треба розмістити.
Програма знайде всі можливі розв'язки кросворду та виведе їх на екран.
Кожен розв'язок кросворду виводиться у вигляді сітки, де слова позначені символами, а вільні клітинки - пустими місцями або дефісами.
n ^ m