Игра на доске 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