Добавьте границы к индексам ограничений в AMPL

Я пытаюсь решить проблему оптимизации шахматной доски, и одно из моих ограничений проверяет, заняты ли соседние ячейки:

subject to attack_each_cell {i in 1..n,j in 1..n}:

    P[i,j]+P[i-1,j+2]+P[i-1,j-2]+P[i+1,j+2]+P[i+1,j-2]+P[i-2,j+1]+P[i-2,j-1]+P[i+2,j+1]+P[i+2,j-1]>=1

Проблема с приведенным выше ограничением заключается в том, что для граничных ячеек я получаю ошибку за пределами границ, поэтому мой второй подход был оператором if-else для (i,j) индексов:

P[i,j]
+ if i>1   and j<n-2 then P[i-1,j+2] 
+ if i>1   and j>2   then P[i-1,j-2] 
+ if i<n-1 and j<n-2 then P[i+1,j+2] 
+ if i<n-1 and j>2   then P[i+1,j-2] 
+ if i>2   and j<n-1 then P[i-2,j+1] 
+ if i>2   and j>1   then P[i-2,j-1] 
+ if i<n-2 and j<n-1 then P[i+2,j+1] 
+ if i<n-2 and j>1   then P[i+2,j-1]
>=1

Это не работает, потому что кажется, что операторы вложены друг в друга, а не выполняются последовательно. Любое предложение о том, как исправить код?


optimization ampl
person Benjamín J Barros G    schedule 03.11.2017    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Вариант 1: добавьте скобки, чтобы зафиксировать порядок оценки.

Вариант 2: переформулируйте ограничение. Вместо того, чтобы проверять позиции хода конем относительно эталонной ячейки, а затем иметь дело с выходом за пределы игровой площадки, проверьте все позиции на доске и примите те, которые являются ходом коня из эталонной ячейки:

subject to attack_each_cell {i in 1..n,j in 1..n}: 
  P[i,j] 
+ sum{i1 in 1..n, j1 in 1..n: abs(i-i1) = 2 and abs(j-j1) = 1} P[i1,j1]
+ sum{i1 in 1..n, j1 in 1..n: abs(i-i1) = 1 and abs(j-j1) = 2} P[i1,j1]
>= 1;

Вариант 3: как указано выше, но начните с создания набора, определяющего допустимые ходы, а затем определите ограничение, ссылаясь на этот набор:

set KnightMoves := {(i,j) in 
  ({-1,1} cross {-2,2})
  union 
  ({-2,2} cross {-1,1})
  }; # this defines the set of moves {(-1,-2),(-1,2), ... (2,1)}

subject to attack_each_cell {i in 1..n,j in 1..n}: 
  P[i,j] + sum{i1 in 1..n, j1 in 1..n: (i-i1,j-j1) in KnightMoves} P[i1,j1]
>= 1;

Мне больше всего нравится № 3, потому что он отделяет логику «как ходят рыцари» от ограничения «любой клетке, в которой нет рыцаря, должен угрожать рыцарь». Это немного упрощает настройку, например. если вам нужно решить задачу для другого типа фигур, и она аккуратно распространяется на задачи с более чем одним типом фигур:

subject to attack_each_cell {i in 1..n,j in 1..n}: 
  P[i,j] 
+ sum{i1 in 1..n, j1 in 1..n: (i-i1,j-j1) in KnightMoves} Knights[i1,j1]
+ sum{i1 in 1..n, j1 in 1..n: (i-i1,j-j1) in BishopMoves} Bishops[i1,j1]
+ sum{i1 in 1..n, j1 in 1..n: (i-i1,j-j1) in Pawn} Pawns[i1,j1]
+ ...
>= 1;

(редактировать: ну, это так, если вы игнорируете проблему блокировки непрыгающих фигур другими.)

person Geoffrey Brent    schedule 04.11.2017
comment
Вариант 1 работал отлично, а два других очень элегантны и масштабируемы. Спасибо! - person Benjamín J Barros G; 06.11.2017
comment
@BenjamínBarros добавить больше квадратных скобок сразу после проверки точек с запятой в моем контрольном списке отладки ;-) Если вас устраивает этот ответ, не забудьте отметить его как ответ, чтобы другие авторы знали, что им не нужно помогать. - person Geoffrey Brent; 08.11.2017