Курсовая работа: Перебор с возвратом

for i:=1 to N do for j:=1 to M do Solve(i,j,1);

writeln(‘число способов обхода конем доски’,N,’*’,M,’--’,t);

Изменим логику так, чтобы находился только один вариант обхода конем доски. При этом маршрут коня находится с использованием правила Варнсдорфа выбора очередного хода (предложено более 150 лет тому назад). Его суть - при обходе шахматной доски коня следует ставить на поле, из которого он может сделать минимальное количество перемещений на еще не занятые поля, если таких полей несколько, можно выбирать любое из них. В этом случае в первую очередь занимаются угловые поля и количество “возвратов” значительно уменьшается.

Вариант процедуры Solve для этого случая.

procedure Solve(x,y,l:integer);

varW:array[1..8] of integer;

xn,yn,i,j,m:integer;

begin

A[x,y]:=l;

if (l<N*N) then begin

for i:=1 to 8 do begin{формированиемассива W}

W[i]:=0;xn:=x+dx[i];yn:=y+dy[i];

if (A[xn,yn]=0) the begin

for j:=1 to 8 do

if (A[xn+dx[j],yn+dy[j]]=0) the Inc(W[i]);

end else W[i]:=-1;

end;

i:=1;

while (i<=8) dobegin

m:=1;{ищем клетку, из которой можно сделать наименьшее число перемещений}

for j:=2 to 8 do if W[j]<W[m] then m:=j;

if (W[m]>=0) and (W[m]<maxint)

then Solve(x+dx[m],y+dy[m],l+1);

W[m]:=maxint;{отмечаем использованную в переборе клетку}

Inc(i);

end;

end

else begin <выводрешения>;

halt;

К-во Просмотров: 454
Бесплатно скачать Курсовая работа: Перебор с возвратом