Лексичний перебір

1.Повернемось до перебору:

а). Ми мали: 1,2,3

1,3,2

2,1,3

2,3,1

3,2,1

3,1,2

б). А якщо ми маємо

3,8,7

Як утворити всі можливі перестановки?

1. Утворити перестановки 1,2,3 і використати їх як індексний масив.

в) Маємо 1,1,2

1,2,1

2,1,1

2. Побудуємо лексичний перебір для довільних елементів масиву

X=3 2 4 2 4 3 1

а) Рухаємось справа наліво. Крок вперед можна зробити, якщо наступне число більше за попереднє. Ми зупинилися перед числом 2. Це число потрібно помітити.

б) Рухаємось справа наліво. Крок вперед можна зробити, якщо число менше за знайдене число(2). Ми зупинилися перед числом 3. Це число потрібно помітити.

в) Переставляємо знайдені числа.

г) Запишемо числа, розміщені після першого знайденого в зворотному порядку.

Перебір з поверненням

Розглянемо метод розв’язку цілого ряду переборних задач на прикладі відомої задачі про тури, які треба розставити на шахівниці так, щоб вони не били один одного. Для наочності візьмемо дошку 3х3 клітинки і розставляти будемо відповідно 3 тури. З відомих формул комбінаторики випливає, що ми будемо мати 3!=6 варіантів розміщень. Очевидно. що при будь-якім розміщенні на кожній горизонталі і на кожній вертикалі повинно бути по одній турі. При відомій вправності і фантазії 3 тури можна ще розставити “вручну” . Ну, а вісім чи більше ( на відповідній дошці, звичайно)? Важкувато...Спробуємо перекласти цю задачу на плечі машини.

Нехай ми маємо два покажчики - стрілки ðñ

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

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

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

Намагаємося знову підняти туру, на яку вказує покажчик. Це можливо. Піднімаємо її і горизонтальний покажчик на 1 позицію вправо, а вертикальний - на 1.

`

Пробуємо помістити туру по покажчиках, якщо немає - піднімаємо вертикальний наверх, поки не знайдемо не биту клітку. Ставимо туру, і знову горизонтальний покажчик піде на одну позицію вправо. Готове чергове розміщення.

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

Виберемо структуру даних. Поле представимо у виді матриці A[n:n], де N кількість кліток у кожній горизонталі і вертикалі ( та й тур у нашому випадку теж N). Якщо в даній клітинці немає тури - A[і,j]=0 , а якщо є то A[і,j]=1. Ще нам знадобляться дві змінні цілого типу для збереження в них значення покажчиків П_В и П_Г.

Для конструювання алгоритму на високому рівні деталізації нам необхідно мати такі процедури і функції:

ПОСТАВ_І_ВПРАВО - ставить туру в клітинку з заданими координатами і переміщає горизонтальний покажчик на одну позицію вправо , а вертикальний установлює на першу позицію (процедура)

ЗНІМИ_І_ВЛІВО - знімає туру з даної клітки і переміщає горизонтальний покажчик на одну позицію вліво , вертикальний покажчик встановлює в позицію тури, на яку тепер указує горизонтальний покажчик ( процедура )

ПРАВИЛЬНА_КЛІТИНКА - логічна функція. Повертає істина, якщо туру можна поставити в дану клітку, і хибно, якщо поставити в клітинку не можна.

ВЛІВО - переміщає горизонтальний покажчик на одну позицію вліво і установлює вертикальний покажчик на туру в цій вертикалі (процедура).

ВИВЕДЕННЯ - виводить на екран результат (процедура)

Тепер наш алгоритм може бути представлений так:

алг Пошук_з_поверненням

поч

для і від 1 до n

нц

для j від 1 до n

нц

A[і,j] :=0

кц

кц

П_Г:=1

П_В:=1

ПОСТАВ_І_ВПРАВО П_В:= П_В+1

поки П_Г<>0

пц поки ( не ПРАВИЛЬНА_КЛІТИНКА ) і (П_Г < n+1)

пц

П_В:=П_В+1

кц

якщо П_В < n+1

то ПОСТАВ_І_ВПРАВО

інакше ЗНІМИ_І_ВЛІВО

все

якщо П_Г =n+1

то ВИВЕДЕННЯ

ВЛІВО

все

кц

до П_Г=0

кін