Я пытаюсь решить проблему, состоящую из n действий (n> = 8). Путь состоит из k (пока k == 4) действий. Я хотел бы проверить, существует ли какой-либо путь, который удовлетворяет определенному мною ограничению.
Я сделал две попытки решить эту проблему:
Попытка 1 : Грубая сила, попробуйте все перестановки
Попытка 2 : закодируйте матрицу выбора пути M [k x n], чтобы каждая строка содержала один и только один элемент больше 0, а все остальные элементы равны в 0.
Например, если k == 2, n == 2, M = [[0.9, 0], [0, 0.7]] представляет сначала выполнение действия 1, затем действие 2.
Затем мой переход состояния был закодирован как:
S1 = a2(a1(S0, M[1][1]), M[1][2]) = a2(a1(S0, 0.9), 0)
S2 = a2(a1(S1, M[2][1]), M[2][2]) = a2(a1(S1, 0), 0.7)
Примечание: я убедился, что S == a(S,0), так что на каждом шаге выполняется только одно действие.
Затем ограничения были проверены на S2
Я надеялся, что это быть быстрее, чем способ перестановки сделать это. К сожалению, это оказывается медленнее. Просто интересно, есть ли лучший способ решить эту проблему?
Код:
_path = [[Real(f'step_{_i}_action_{_j}') for _j in range(len(actions))] for _i in range(number_of_steps)]
_states: List[State] = [self.s0]
for _i in range(number_of_steps):
_new_state = copy.deepcopy(_states[-1])
for _a, _p in zip(actions, _path[_i]):
self.solver.add(_a.constraints(_states[-1], _p))
_new_state = _a.execute(_new_state, _p)
_states.append(_new_state)