Алгоритми з поверненням

Найбільш цікава область програмування - задачі так званого штучного інтелекту. Тут маємо справу з алгоритмами, які шукають рішення шляхом проб та помилок. Цей процес розділяється на окремі задачі, які переважно розглядаються в термінах рекурсії та вимагають дослідження кінцевого числа підзадач. Методом проб та помилок вибирається деякий ланцюжок висновків. У випадку невдач організовується перебір з поверненням для пошуку іншого ланцюжка. Для організації пошуку правильного ланцюжка використовується дерево пошуку. Зростання такого дерева часто буває експоненціальним. Прикладами таких задач є «Задача про 8 ферзів», «Задача виходу з лабіринту», «Задача про хід коня», «Задача про стабільні браки», «Задача оптимального вибору» та інші.

ЛЕКЦІЯ 13