Об одном наблюдении.
Базовое распределение:
![$\begin{array}{l}
{\rm M_4:1}{\rm ,2},...,{\rm a[4]}{\rm ,} \\
{\rm M_3:a[4] + 1},...,{\rm a[4] + a[3]}{\rm ,} \\
{\rm M_2:a[4] + a[3] + 1},...,{\rm a[4] + a[3] + a[2]}{\rm ,} \\
{\rm M_1:a[4] + a[3] + a[2] + 1},...,{\rm a[4] + a[3] + a[2] + a[1]}{\rm ,} \\
{\rm M_0:a[4] + a[3] + a[2] + a[1] + 1},...,{\rm n}^{\rm 2} \\
\end{array}$](https://dxdy-04.korotkov.co.uk/f/b/c/0/bc09e99b66c792e1f8e03f4bf7543fb682.png "$\begin{array}{l}
{\rm M_4:1}{\rm ,2},...,{\rm a[4]}{\rm ,} \\
{\rm M_3:a[4] + 1},...,{\rm a[4] + a[3]}{\rm ,} \\
{\rm M_2:a[4] + a[3] + 1},...,{\rm a[4] + a[3] + a[2]}{\rm ,} \\
{\rm M_1:a[4] + a[3] + a[2] + 1},...,{\rm a[4] + a[3] + a[2] + a[1]}{\rm ,} \\
{\rm M_0:a[4] + a[3] + a[2] + a[1] + 1},...,{\rm n}^{\rm 2} \\
\end{array}$")
![$a[i]$](https://dxdy-02.korotkov.co.uk/f/d/6/d/d6d0390c8972c686de739378984c0d2b82.png "$a[i]$")
-количество клеток, через которые проходят
линий.
Базовому распределению соответствует оценка схемы
min.
Ищется распределение, которое должно иметь оценку
min+top.
При росте
top количество таких распределений быстро растет.
Я попробовал рассматривать только часть подобных распределений, а именно, только такие, которым соответствует не более одного обмена между соседними уровнями
u и
(u-1).
Запуск перебора:
set_top(top,1)Код:
procedure set_top(x,y:integer);
var k,u,v,i,j,b:integer;
begin
if x=0 then begin cop(m0,m);run;exit;end;
if y>4 then exit;
if opt then begin u:=y-1;v:=y end else begin u:=y;v:=y-1 end;
set_top(x,y+1);
for k:=1 to x do
for i:=0 to a[u]-1 do for j:=0 to a[v]-1 do
if (m0[v,j]-m0[u,i])=k then begin
b:=m0[v,j];m0[v,j]:=m0[u,i];m0[u,i]:=b;
set_top(x-k,y+1);
b:=m0[v,j];m0[v,j]:=m0[u,i];m0[u,i]:=b;
end;
end;
здесь:
m,m0 - рабочее и базовое распределения,
m[
u-уровень,
i-индекс от
0 до
a[u]-1].
cop(m0,m) - копирование распределения
m0 в распределение
m, которое затем обрабатывается процедурой поиска решения
run.
При поиске максимального решения используется та же процедура, только меняется базовое распределение
![$m0[i,j]=n^2+1-m0[i,j]$](https://dxdy-02.korotkov.co.uk/f/1/9/f/19f572ed4f90eb5c64239219fc655b7082.png "$m0[i,j]=n^2+1-m0[i,j]$")
и задается значение opt=true. Как видно из текста, рекурсия начинается с уровня 1 до 4. Я пробовал и обратное направление с уровня 4 до 1, но результат был печальным. При малых
top можно просмотреть все распределения и, поэтому, разницы нет. При больших
top число распределений может превышать несколько тысяч. Так вот, при рекурсии от 1 до 4, как показал эксперимент, хорошие распределения выдаются в начале перебора.
Дело за малым
- нужна хорошая процедура поиска решений
run.
если... там не будет Gerbicz.
