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

Розв’язок практичних задач в деяких випадках може вимагати перебору всіх можливих варіантів розв’язку. Такими є задачі з області «штучного інтелекту». Тут потрібно будувати алгоритми, що  знаходять рішення певної задачі не за фіксованими правилами обчислення, а методом спроб і помилок.

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

Розглянемо добре відомий приклад - задачу про хід коня.

Дано дошку n´n, що містить n2 полів. Кінь, що ходить відповідно до шахових правил, міститься на полі з початковими координатами (x0, y0). Потрібно покрити всю дошку ходами коня, тобто знайти обхід дошки, якщо він існує, з n2-1 ходів, такий, що кожне поле відвідувалось рівно один раз.

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

Умовно спробу ходу можна описати таким чином:

Procedure  спроба_наступного_ходу;

Begin

ініціація_вибірки_ходів:

repeat

вибір_наступного_можливого_ходу_з_

списку_чергових_ходів;

if хід_прийнятний then

  begin

   запис_ходу;

  if дошка_не_заповнена then

  begin

  спроба_наступного_ходу;

  if невдача then стирання_попереднього_ходу;

  end;

  end;

until (хід_є_вдалим) or (немає_інших_можливих_ходів);

End;

Щоб точно описати цей алгоритм, необхідно  вибрати зручне подання даних. Дошку представимо у виді матриці, індексованої за обома координатами числами від 1до n:

type index=1..n;

var h: array  [index, index] of  integer;

Кожен хід будемо  відзначати в матриці його порядковим номером. В такому випадку заповнення матриці буде мати такий вигляд:

h [x,y]=0;  поле з координатами (x,y) не відвідувалося,

h [x,y]=i;  поле з координатами (x,y)  відвідувалося на i-ому ході  (1£i£n2).

Тоді у випадку позитивного результату наприкінці природним чином роздрукується  вся матриця ходів. Початкові умови для наступного ходу задаються координатами поля (x,y), з якого робиться хід з номером ходу i. Для визначення вдалості ходу будемо користуватися логічним параметром–результатом: q=true  означає удачу (можливість наступного ходу), q=false - невдачу.

Спробуємо зробити ще кілька уточнень. «Дошка_не_заповнена» можна виразити у вигляді умови  i<n2. «Хід_прийнятний» означає наступне: якщо позначити через  u і v координати можливого наступного ходу, то необхідно, щоб поле з цими координатами знаходилося на дошці і раніше не відвідувалося. Очевидно, з кожної клітини є вісім варіантів вибору наступного ходу. Нові координати зручно задавати через відповідні прирости поточних координат. Однак слід врахувати, що не завжди клітина з новими координатами може бути на дошці.

Програма, що реалізує даний алгоритм, матиме такий вигляд:

program knightstour; 

uses dos,crt; 

const

n=5;

nsq=n*n; 

type index=1..n; 

var

i,j:index;

q:boolean;

s:set of index;

a,b:array[1..8] of integer;

h:array[index,index] of integer;

x1,y1:index;

t1,t2,t3,t4,t5,t6,t7,t8:word;

h1,h2:longint;

sec,sec1,min,msec:integer; 

procedure try(i:integer;x,y:index;var q:boolean);

{процедура визначення можливості ходу}

var

k,u,v:integer;

q1:boolean; 

begin

k:=0;

repeat

k:=k+1;

q1:=false;

u:=x+a[k];

v:=y+b[k];

if (u>0) and (v>0) and (u in s) and (v in s ) and (h[u,v]=0)

then begin

  h[u,v]:=i;

  if i<nsq

  then begin

  try(i+1,u,v,q1);

  if not(q1) then h[u,v]:=0;

  end

else q1:=true

end

until q1 or (k=8);

q:=q1; 

end; 

begin 

{ 

*******************************************

  О с н о в н а п р о г р а м а 

******************************************* 

}

s:=[1..n];

a[1]:=2;  b[1]:=1;

a[2]:=1;  b[2]:=2;

a[3]:=-1;  b[3]:=2;

a[4]:=-2;  b[4]:=1;

a[5]:=-2;  b[5]:=-1;

a[6]:=-1;  b[6]:=-2;

a[7]:=1;  b[7]:=-2;

a[8]:=2;  b[8]:=-1;

for i:=1 to n do

  for j:=1 to n do h[i,j]:=0;

clrscr;

write(’Введіть індекси початкової клітини :’);

read(x1,y1);

clrscr;

h[x1,y1]:=1;

gettime(t1,t2,t3,t4);

try(2,x1,y1,q);

gettime(t5,t6,t7,t8);

writeln;

writeln;

if q then

for i:=1 to n do

begin

  for j:=1 to n do

  write(h[i,j]:4);

  writeln

end

else writeln(’немає розв”язку’);

h1:=(t2*60+t3)*100+t4;

h2:=(t6*60+t7)*100+t8;

sec1:=(h2-h1) div 100;

msec:=(h2-h1) mod 100;

min:=sec1 div 60;

sec:=sec1 mod 60;

writeln;

writeln(Час роботи програми ',min,' мин ',sec,' сек ',msec,'  мсек');

repeat until keypressed;

end.

Для дошки розмірності 5х5 за умови початкової клітини з координатами (1,1) обхід буде мати такий вигляд:

  1  6  15  10  21

  14  9  20  5  16

  19  2  7  22  11

  8  13  24  17  4

  25  18  3  12  23

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