Игра на доске 10x10

[lel0lel]

vicvolf в сообщении #1679527 писал(а):

Просто хотел сказать, что на части шахматной доски 2х10 числа могут быть расположены в виде "змейки", а на другой части 8х10 они могут быть расположены по-другому. Тогда у короля может быть маршрут с суммой меньше 500

Может, но это не является проблемой. Ведь нужно было показать, что всегда найдется путь стоимостью не выше 500.

Сможете показать, что в любой таблице 10×10 всегда найдется полоса с суммой всех чисел не превосходящей 1010? Это требуется, чтобы завершить доказательство)

[vicvolf]

lel0lel в сообщении #1679603 писал(а):

Сможете показать, что в любой таблице 10×10 всегда найдется полоса с суммой всех чисел не превосходящей 1010? Это требуется, чтобы завершить доказательство)

Здесь же сумма чисел на доске всегда 5050, поэтому среднее по строке - 505. А стратегия "змейка" в каждой строке и дает 505. Она соответствует принципу Дирихле.

[Alex Krylov]

Выше вот нечто такое мной было написано:

Цитата:

Условия непрерывности траекторий (вроде такое имеет смысл):
$\\ \sum\limits_{i=1}^{N-1}(Y_{i,j+1}+Y_{i+1,j})+\sum\limits_{i=1}^{N-1}(Y_{i+1,j+1}+Y_{i,j})+\sum\limits_{i=1}^{N}(Y_{i,j}+Y_{i,j+1})=2 \\ \forall j =1,\dots,N-1 $

Это туфта. "Условия непрерывности траекторий" относительно переменных $Y_{i,j}$ невыпуклы, а значит тот подход, о котором говорилось выше (взяли, релаксировали булевы ограничения на $Y_{i,j}$, как единственные невыпуклые ограничения), утрачивает основания.

[mihaild]

vicvolf в сообщении #1679657 писал(а):

Здесь же сумма чисел на доске всегда 5050, поэтому среднее по строке - 505.

Но нам же нужна не просто пара строк, в которых сумма будет 1010, а пара соседних таких строк.

[Alex Krylov]

Вот кстати для случая $4$\times$4$ оптимальная матрица не имеющая конфигурацию "змейка":

Используется синтаксис Matlab M

   
    9    4   13   7
   10    3   14   8
   12    2   16   6
   11    1   15   5

[Alex Krylov]

Кстати говоря... В посте от 19.03.2025, 17:19 было сказано:

Цитата:

Вообще не мешало бы переформулировать изначальную задачу в виде некоей хоть сколько-нибудь обозримой оптимизационной задачи...

...и далее "путем явного перечисления" исходная задача была переформулирована в замкнутой (относительно переменных $X_{i,j},\;t$) форме (на "проклятие размерности" не обращаем внимание ).

Если теперь в этой задаче булевы ограничения на переменные $X_{i,j}$ линейно релаксировать, а затем решить соотв. линейную программу, то оптимальное значение целевой функции будет равно $\frac{\sum\limits_{i=1}^{N^2}i}{N}$, где $N$-размерность задачи. Т.е. имеем ненулевой integrality gap!

Касательно поиска непосредственно целочисленных решений... Для случая $N=4$ MILP-решатель достаточно быстро находит оптимальное (целочисленное) решение и дальше некоторое количество времени тратится на то, чтобы оценка оптимума снизу сошлась к оценке оптимума сверху. А вот уже для случая $N=6$ все гораздо хуже: $101\leqslant\dots\leqslant111$ Дальнейшего сужения интервала ждать не стал...

[Alex Krylov]

В сообщении от 24.03.2025, 16:33 мной было сказано:

Цитата:

Это туфта. "Условия непрерывности траекторий" относительно переменных $Y_{i,j}$ невыпуклы, а значит тот подход, о котором говорилось выше (взяли, релаксировали булевы ограничения на $Y_{i,j}$, как единственные невыпуклые ограничения), утрачивает основания.

Это несколько поспешное утверждение, сделанное "на скорую руку"! То, что было названо туфтой, действительно туфтой и является. В остальном же утверждение не соответсвует действительности, и "условия непрерывности траекторий" могут быть формализованы в достаточно простой и удобоваримой форме. Чтобы это сделать, необходимо следующее логическое условие непрерывности:

Цитата:

$\boldsymbol{[} \boldsymbol{Y_{i,j}}\Rightarrow (Y_{i-1,j+1} \wedge \neg Y_{i,j+1} \wedge \neg Y_{i+1,j+1}) \vee (\neg Y_{i-1,j+1} \wedge Y_{i,j+1} \wedge \neg Y_{i+1,j+1}) \vee (\neg Y_{i-1,j+1} \wedge \neg Y_{i,j+1} \wedge Y_{i+1,j+1})\boldsymbol{]}\wedge\boldsymbol{[}\boldsymbol{\neg Y_{i,j}}\Rightarrow (\neg Y_{i-1,j+1} \wedge \neg Y_{i,j+1} \wedge \neg Y_{i+1,j+1}) \vee (Y_{i-1,j+1} \wedge \neg Y_{i,j+1} \wedge \neg Y_{i+1,j+1}) \vee (\neg Y_{i-1,j+1} \wedge Y_{i,j+1} \wedge \neg Y_{i+1,j+1}) \vee (\neg Y_{i-1,j+1} \wedge \neg Y_{i,j+1} \wedge Y_{i+1,j+1})\boldsymbol{]}$

переформулировать в удобоваримой алгебраической форме, т.е. в форме линейных равенств/неравенств.

Для этого для приведенного выше логического выражения нужно получить Конъюнктивную Нормальную Форму (КНФ). С помощью пакета Logic программы Maple (функция Canonicalize) это делается в автоматизированном режиме. Вот КНФ:

Цитата:

(A or B or C or not Y)and (A or Y or not B or not C)and(A or not B or not C or not Y)and(B or Y or not A or not C)and(B or not A or not C or not Y)and(C or Y or not A or not B)and(C or not A or not B or not Y)and(Y or not A or not B or not C)and not (A and B and C and Y)

Здесь $Y=Y_{i,j},\quad A=Y_{i-1,j+1},\quad B=Y_{i,j+1},\quad C=Y_{i+1,j+1}$

Далее каждый дизъюнкт КНФ переписывается в форме линейного неравенства:

$\\ (1-Y)+A+B+C \geqslant 1 \\ Y+A+(1-B)+(1-C)\geqslant 1 \\ (1-Y)+A+(1-B)+(1-C) \geqslant 1 \\ Y+(1-A)+B+(1-C)\geqslant 1 \\ (1-Y)+(1-A)+B+(1-C)\geqslant 1 \\ Y+(1-A)+(1-B)+C \geqslant 1 \\ (1-Y)+(1-A)+(1-B)+C \geqslant 1 \\ Y+(1-A)+(1-B)+(1-C) \geqslant 1 \\ (1-Y)+(1-A)+(1-B)+(1-C) \geqslant 1$

Для 1-й и последней строк выражения будут проще.

Собственно, вот это общий подход.

[Alex Krylov]

Вот простенькая программка (Matlab, парсер Yalmip), которая для заданной матрицы весов $c$ (с расстановкой весов "змейкой") решает линейно релаксированную задачу поиска пути с наименьшей суммой:

Используется синтаксис Matlab M

N = 4;%размерность задачи
c = zeros(N);%матрица весов
Y = sdpvar(N,N,'full');%оптимизируемые переменные
%Y = binvar(N,N,'full');

%Заполнение матрицы весов c
cnt = 1;
for i = 1:N
    if (rem(i,2)>0)
        for j=1:N
            c(j,i) = cnt;
            cnt = cnt + 1;
        end
    else
        for j=N:-1:1
            c(j,i) = cnt;
            cnt = cnt + 1;
        end
        
    end
end

%ограничения
constr =[0<=Y(:), sum(Y,1)==1];
%constr =[sum(Y,1)==1];

for j = 1:N-1
%ограничения для крайних нижней и верхней строчек матрицы 
        constr = [constr, 1 - Y(1,j) + Y(1,j+1) + Y(2,j+1) >= 1, 1 - Y(N,j) + Y(N,j+1) + Y(N-1,j+1) >= 1];
end 

for i = 2:N-1
    for j = 1:N-1
        constr = [constr, 1 - Y(i,j) + Y(i-1,j+1) + Y(i,j+1) + Y(i+1,j+1) >= 1];   
    end    
end

obj = trace(c'*Y);
optimize(constr, obj);%запускаем решение оптимизационной задачи
value(obj)%значение целевой функции в оптимуме
value(Y)%значения оптимизируемых переменных после оптимизации
 

При решении указанной релаксированной задачи продемонстрированные ранее достаточно сложные ограничения

Цитата:

$\boldsymbol{[} \boldsymbol{Y_{i,j}}\Rightarrow (Y_{i-1,j+1} \wedge \neg Y_{i,j+1} \wedge \neg Y_{i+1,j+1}) \vee (\neg Y_{i-1,j+1} \wedge Y_{i,j+1} \wedge \neg Y_{i+1,j+1}) \vee (\neg Y_{i-1,j+1} \wedge \neg Y_{i,j+1} \wedge Y_{i+1,j+1})\boldsymbol{]}\wedge\boldsymbol{[}\boldsymbol{\neg Y_{i,j}}\Rightarrow (\neg Y_{i-1,j+1} \wedge \neg Y_{i,j+1} \wedge \neg Y_{i+1,j+1}) \vee (Y_{i-1,j+1} \wedge \neg Y_{i,j+1} \wedge \neg Y_{i+1,j+1}) \vee (\neg Y_{i-1,j+1} \wedge Y_{i,j+1} \wedge \neg Y_{i+1,j+1}) \vee (\neg Y_{i-1,j+1} \wedge \neg Y_{i,j+1} \wedge Y_{i+1,j+1})\boldsymbol{]}$

не дают никакого выигрыша по сравнению с гораздо более простыми условиями:

Цитата:

$\boldsymbol{Y_{i,j}}\Rightarrow Y_{i-1,j+1} \vee Y_{i,j+1} \vee Y_{i+1,j+1}$

Более того, с учетом дополнительных ограничений

Используется синтаксис Matlab M

constr =[0<=Y(:), sum(Y,1)==1];

указанные системы ограничений эквивалентны.

При решении двоичной оптимизационной задачи (без какой-либо релаксации) ограничения

Используется синтаксис Matlab M

sum(Y,1)==1

делают указанные выше огранчиния сложногого вида заведомо излишними. И, как уже было сказано выше, при решении релаксированной задачи также выигрыша не дают, так как эквиваленты более простым.

Оптимальное решение для матрицы 4x4:

Используется синтаксис Matlab M

value(obj) =
31.25

value(Y) =
    0.5   0.0   0.25   0
    0.5   0.5   0.25   0.25
    0.0   0.0   0.5    0.00
    0.0   0.5   0.0    0.75

[vicvolf]

Alex Krylov в сообщении #1681112 писал(а):

Вот простенькая программка (Matlab, парсер Yalmip), которая для заданной матрицы весов $c$ (с расстановкой весов "змейкой") решает линейно релаксированную задачу поиска пути с наименьшей суммой:

Для "змейки" это не имеет смысла. Там в каждой строке равные суммы и оптимальная стратегия движения короля легко определяется. Вот в случае расстановки чисел на доске в общем случае выбор оптимального пути значительно сложнее, но тут тоже не надо изобретать велосипед. Это с успехом делается методом динамического программирования.

[Alex Krylov]

Цитата:

тут тоже не надо изобретать велосипед

Это чисто для демонстрации некоей единообразной методики трансформации логических ограничений в алгебраические. А основная проблема тут состоит в том, что изначально та часть задачи, которая стоит под знаком $\min\limits_{}\left\lbrace \dots \right\rbrace$ в минимаксной задаче, была сформулирована не так, как надо. Ее надо формулировать как задачу о наикратчайшем пути (известная решаемая задача комбинаторной оптимизации) относительно другого набора переменных (связанных не с вершинами графа, как выше, а с его ребрами). Тогда для соотв. линейно релаксированной задачи отсутствует integrality gap.

Вот текст соотв. Matlab-программы (линейно релаксированная версия задачи о наикратчайшем пути):

Используется синтаксис Matlab M

N = 4;
c = zeros(N);
M = N^2+2;
BIG = N^2*(1 + N^2);

L = repmat(BIG, M);
Y = sdpvar(M,M,'full');
%Y = binvar(M,M,'full');


cnt = 1;
for i = 1:N
    if (rem(i,2)>0)
        for j=1:N
            c(j,i) = cnt;
            cnt = cnt + 1;
        end
    else
        for j=N:-1:1
            c(j,i) = cnt;
            cnt = cnt + 1;
        end
        
    end
end

for i = 1:N
    L(1, 2+(i-1)*N) = c(i, 1);    
    L(1+N+(i-1)*N, end) = 0;
end

for i = 1:N
    for j=1:N-1
        
        for i_temp = i-1:1:i+1
            if ((i_temp>=1)&&(i_temp<=N))
        
                L(1+j+(i-1)*N, 1+(j+1)+(i_temp-1)*N) = c(i_temp,j+1);
            end
        end
        
    end
end


constr = [0<=Y(:), sum(Y(1,:))==1, sum(Y(:,1))==0, sum(Y(end,:))==0, sum(Y(:,end))==1];
%constr = [sum(Y(1,:))==1, sum(Y(:,1))==0, sum(Y(end,:))==0, sum(Y(:,end))==1];
for i = 2:M-1 
    constr = [constr, sum(Y(i,:)) - sum(Y(:,i))==0]; 
end

obj = trace(L'*Y);
optimize(constr, obj);
value(obj)
value(Y)
 

P.S. Интересный, кстати говоря, феномен... Одна и та же задача, но сформулированная относительно разных наборов переменных, при линейной релаксации в одном случае может давать integrality gap, а в другом - нет.

[Alex Krylov]

Цитата:

Вот текст соотв. Matlab-программы (линейно релаксированная версия задачи о наикратчайшем пути):

Относительно того, что там за переменные $Y$ в этой программе:

Видно, что помимо узлов, отвечающих ячейкам исходной весовой матрицы $c$, было введено два дополнительных узла - узел-источник (№1 на рис.) и узел-сток (№18 на рис.). Если путь пролегает от узла $i$ к узлу $j$, то $Y_{i,j}=1$, в противном случае - 0. На переменные $Y_{i,j}$ наложены регулярные (по своей структуре) ограничения, а невозможность перехода между какими-то узлами (и в каком-то направлении) котролируется помещением большого числа $BIG$ в соответсвующее поле матрицы весов $L$.

Ну то есть $Y$ - стандартный набор переменных, используемый в задаче о наикратчайшем пути.

[Alex Krylov]

Цитата:

P.S. Интересный, кстати говоря, феномен... Одна и та же задача, но сформулированная относительно разных наборов переменных, при линейной релаксации в одном случае может давать integrality gap, а в другом - нет.

А "феномен" этот объясняется просто и об этом уже упоминалось в сообщении от 22.03.2025, 02:18. Если при линейной релаксации исходной целочисленной задачи получается, что выпуклый многогранник, внутри которого ищется решение релаксированной задачи, оказывается натянут на все множество корректных целочисленных решений, то будет нулевой integrality gap.

Если же при релаксации получается многогранник, у которого наличествуют вершины, отличные от корректных целочисленных решений, то возможен ненулевой integrality gap (если минимум целевой функциии лежит на одной (или нескольких) из этих вершин).

Т.е. что имеет место быть... Имеется классическая задача о наикратчайшем пути, которая будучи сформулированной относительно классического (и правильного!) набора переменных, обладает замечательными свойствами (в частности, свойстовом давать нулевой integrality gap при линейной релаксации). А при "неправильном" наборе переменных (с дополнительными неравенствами впридачу) эти замечательные свойства утрачиваются, а взамен приобретаются свойства дурные...

[vicvolf]

Alex Krylov в сообщении #1680899 писал(а):

Вот кстати для случая $4$\times$4$ оптимальная матрица не имеющая конфигурацию "змейка":

Используется синтаксис Matlab M

   
    9    4   13   7
   10    3   14   8
   12    2   16   6
   11    1   15   5

Проверил, действительно оптимальное.

[vicvolf]

vicvolf в сообщении #1681335 писал(а):

Проверил, действительно оптимальное.

Каким методом решали?

Alex Krylov в сообщении #1681230 писал(а):

Это чисто для демонстрации некоей единообразной методики трансформации логических ограничений в алгебраические. А основная проблема тут состоит в том, что изначально та часть задачи, которая стоит под знаком $\min\limits_{}\left\lbrace \dots \right\rbrace$ в минимаксной задаче, надо формулировать как задачу о наикратчайшем пути (известная решаемая задача комбинаторной оптимизации) относительно другого набора переменных (связанных не с вершинами графа, как выше, а с его ребрами). Тогда для соотв. линейно релаксированной задачи отсутствует integrality gap..

Выше я уже говорил, что задача о нахождении наикратчайшего пути хорошо решается методом динамического программирования и ради нее не стоит копья ломать. Гораздо больший интерес представляет задача оптимального расположения чисел на доске, которая является более трудоемкой и включает в себя задачу нахождения наикратчайшего пути.

[Alex Krylov]

Ну вот... Совсем крохотная модификация предыдушей программы приводит к следующему коду линейно релаксированной min-max-задачи. Переменные Y по-прежнему соответствуют задаче о наикратчайшем пути, а новые переменные X отвечают за конфигурацию чисел на доске (задача о назначениях).

Используется синтаксис Matlab M

N = 4;
c0 = (1:N^2)';
c = zeros(N);
M = N^2+2;
BIG = N^2*(1 + N^2);

X = sdpvar(N^2,N^2,'full');
Y = sdpvar(M,M,'full');

%Небольшой трюк с заполнением матрицы L, чтобы она была класса sdpvar, а не
%double
L_ = zeros(M);
L_(1, 2) = 1;
L = repmat(BIG, M) + L_*(X(1,:)*c0);
%--

cnt = 1;
for i = 1:N
    if (rem(i,2)>0)
        for j=1:N
            c(j,i) = cnt;
            cnt = cnt + 1;
        end
    else
        for j=N:-1:1
            c(j,i) = cnt;
            cnt = cnt + 1;
        end
        
    end
end

%c(i,j) = X(j + N*(i-1),:)*c0;
for i = 1:N
    L(1, 2+(i-1)*N) = X(1 + N*(i-1),:)*c0;    
    L(1+N+(i-1)*N, end) = 0;
end

for i = 1:N
    for j=1:N-1
        
        for i_temp = i-1:1:i+1
            if ((i_temp>=1)&&(i_temp<=N))
        
                L(1+j+(i-1)*N, 1+(j+1)+(i_temp-1)*N) = X(j + 1 + N*(i_temp-1),:)*c0;
            end
        end
        
    end
end

constr_X = [0<=X(:)<=1, sum(X,1)==1, sum(X,2)==1, uncertain(X)];

constr_Y = [0<=Y(:), sum(Y(1,:))==1, sum(Y(:,1))==0, sum(Y(end,:))==0, sum(Y(:,end))==1];
for i = 2:M-1 
    constr_Y = [constr_Y, sum(Y(i,:)) - sum(Y(:,i))==0]; 
end

obj = trace(L'*Y);

[rconstr, robj] = robustmodel([constr_X, constr_Y], obj, sdpsettings('robust.lplp','duality'));
optimize(rconstr, robj);
value(robj)%Выводим значение целевой функции

Для доски размером 4x4 значение целевой функции релаксированной min-max-задачи: 34