лку в формуванні умови виходу з циклу, особливо, якщо не знаєш закони де Моргана, до того ж іноді простіше використовувати цикл for, а якщо варіантів мало, можна обійтися взагалі без циклів. Спробуємо усунути вище наведені недоліки. Для розробки загальної схеми перебору з поверненнями скористаємося процедурою з завдання про лабіринті, просто слід її узагальнити:
{пошук одного рішення}
procedure backtracking (k: integer); {k - номер ходу}
begin
{запис варіанту}
if {рішення знайдено} then
{висновок рішення}
< p> else
{перебір всіх варіантів}
if {варіант підходить} then
backtracking (k +1); {рекурсивний виклик}
{стирання варіанту}
end;
begin
backtracking (1);
end.
< p> Зрозуміло дана схема також не ідеальна, але вона усуває зазначені вище недоліки. Також можна відповідно зробити схеми для інших класів переборних завдань. Спочатку схема для пошуку всіх рішень:
{пошук всіх рішень}
procedure backtracking (k: integer); {k - номер ходу}
begin
{запис варіанту}
if {рішення знайдено} then
{запис рішення}
else
{перебір всіх варіантів}
if {варіант підходить} then
backtracking (k +1); {рекурсивний виклик}
{стирання варіанту}
< p> end;
Замість запису рішення його можна виводити у вихідний файл, або обробляти іншим чином залежно від умови задачі. Цю схему можна змінити, що знаходилися не всі рішення, а тільки одне оптимальне. Під оптимальністю рішення зазвичай розуміють, що для даного рішення деяка функція приймає або максимальне, або мінімальне значення. p> Розглянемо докладніше алгоритм перебору з поверненням на прикладі відомої задачі про вісім ферзів. p> Скількома способами можна розставити 8 ферзів на шахівниці так, щоб вони не били один одного? Легенда приписує формулювання і рішення цього завдання "королю математиків "Гауссу. Він перший зумів відшукати всі 92 рішення. p> Рішення. Відповідно до описаної раніше загальною схемою алгоритму перебору з поверненням запропоновану задачу можна було б вирішувати за наведеним нижче алгоритмом "Все розстановки". По ньому ферзі розставляються послідовно на вертикалях з номерами від нуля і далі. У процесі виконання приписи можливі зняття ферзів з дошки (повернення).
Алгоритм "Всі розстановки"
1. Вважаємо D = Г†, j = 0 ( D - безліч рішень, j - поточний стовпець для чергового ферзя). p> 2. Намагаємося в стовпці j просунути вниз по вертикалі або новий (якщо стовпець j порожній), або вже наявний там ферзь на найближчу допустиму рядок. Якщо це зробити не вдалося, то переходимо до пункту 4. p> 3. j В¬ j +1. Якщо j < n -1, то переходимо до пункту 2. В іншому випадку j = n -1, тобто всі вертикалі вже зайняті. Знайдене часткове вирішення запам'ятовуємо в множині D і переходимо до пункту 2. p> 4. j В¬ j -1, тобто знімаємо ферзь з стовпця j і переходимо до попереднього колонки. Якщо j Ві 0, то виконуємо пункт 2. Інакше обчислення припиняємо. Рішення завдання знаходяться в множині D , яке, взагалі кажучи, може бути і порожнім. p> В§ Метод проб і помилок
Розглянемо цей метод також на прикладі задачі про вісім ферзів ..
Процес розстановки ферзів може виглядати так. Поставимо першого ферзя на яку-небудь клітину. Потім поставимо другого ферзя на першу клітку і перевіримо, що йому не загрожує перший. Якщо загрожує, то пересунемо другого ферзя і знову перевіримо і так до тих пір, поки другий ферзь не опиниться на допустимої клітці. Потім будемо рухати третього ферзя і т.д.
У розглянутій задачі номером ходу i буде порядковий номер ферзя, а номером варіанту j - порядковий номер спроби встановити цього ферзя після того, як попередні ферзі встановлені. Може виявитися, що в ході розстановки 1-го ферзя всі варіанти будуть невдалими, тобто ми не зуміємо поставити його на дошку. У такому випадку ми повинні будемо повернутися на хід назад і встановити попереднього (i - 1)-го ферзя по-іншому, тобто перейти до наступного варіанта його розстановки. Очевидно, що для цього треба знати останній розглянутий варіант установки (i - 1)-го ферзя. Потім збільшуємо номер варіанта і продовжуємо перегляд варіантів установки цього ферзя.
Отже, процес розстановки ферзів виглядає наступним чином. Ми рухаємося вперед, збільшуючи номер ходу. Для кожного ходу рухаємося вбік, підбираючи допустимий варіант, та йдемо вперед до наступного ходу, якщо варіант підібраний. Якщо неможливо підібрати варіант, то повертаємося на хід тому і продовжуємо рух вбік, починаючи з наступного варіанту. Після установки останнього ферзя записуємо отримане рішення. У цих рухах вперед і назад за номерами ходів і полягає особливість схе...
