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

[vicvolf]

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

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

Вы себе противоречите:

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

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

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

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

Оптимальное значение 32, аналогичное "змейке".

[Alex Krylov]

Цитата:

Вы себе противоречите:

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

[vicvolf]

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

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

Вы не ответили на вопрос?

[Alex Krylov]

В сообщении от 03.04.2025, 05:15 написано:

Цитата:

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

Вот так!