Вы можете сформулировать это как целочисленную линейную программу, а затем решить ее с помощью такого инструмента, как PuLP или Pyomo.
Идея состоит в том, что вам нужно выбрать неотрицательные целые числа up1, down1, up2 и down2 такие, что up1*d1 - down1*d1 + up2*d2 - down2*d2 == p.Кроме того, вы хотите выбрать значения для этих переменных, которые минимизируют общее количество шагов up1 + down1 + up2 + down2.
Вот пример использования PuLP (в общих чертах этого урока ):
from pulp import *
def position(k, d1, d2, p):
prob = LpProblem("Minimum Steps", LpMinimize)
# define decision variables (values to be chosen by solver)
up1 = LpVariable('up1', lowBound=0, cat='Integer')
down1 = LpVariable('down1', lowBound=0, cat='Integer')
up2 = LpVariable('up2', lowBound=0, cat='Integer')
down2 = LpVariable('down2', lowBound=0, cat='Integer')
# define objective function (expression to minimize)
num_steps = up1 + down1 + up2 + down2
prob += num_steps
# define main constraint (rule to enforce)
prob += (k + up1*d1 - down1*d1 + up2*d2 - down2*d2 == p)
# solve with a time limit, because otherwise CBC may search forever
prob.solve(PULP_CBC_CMD(maxSeconds=2))
# if you have CPLEX installed, it can detect infeasibility immediately
# prob.solve(CPLEX_CMD())
status = LpStatus[prob.status]
solution = [str(k)]
if status == 'Optimal':
# report steps
steps = [
(1, up1, 'd1'), (-1, down1, 'd1'),
(1, up2, 'd2'), (-1, down2, 'd2')
]
for (sign, v, step) in steps:
if v.varValue > 0:
solution.append('-' if sign < 0 else '+')
solution.append('{} * {}'.format(int(v.varValue), step))
solution.extend(['=', str(p)])
print(' '.join(solution))
return int(num_steps.value())
elif status in {'Infeasible', 'Not Solved', 'Undefined'}:
# infeasible or timed out (probably infeasible)
return -1
else:
raise RuntimeError("Problem status was {}".format(status))
print(position(10, 4, 6, 8))
# 10 + 1 * d1 - 1 * d2 = 8
# 2
print(position(10, 4, 6, 9))
# -1
print(position(10, 171, 53, 8))
# 10 - 9 * d1 + 29 * d2 = 8
# 38
print(position(10, 3, 4, 1000000001))
# 10 + 1 * d1 + 250000000 * d2 = 1000000001
# 250000001
Целочисленные линейные программные решатели используют метод ветвей и границ.Сначала они находят лучшее решение с дробными значениями для переменных (количество шагов), затем последовательно разделяют разрешенную область на более мелкие участки с целочисленными ребрами и, в конце концов, останавливаются, когда находят лучшее решение на ребре.
Для небольших значений k, d1, d2 и p это должно найти решение очень быстро (как и рекурсивное решение методом перебора).Но для неосуществимых проблем наивный подход может продолжаться вечно (как и рекурсивное решение методом грубой силы).Коммерческие решатели (например, CPLEX или Gurobi) могут идентифицировать эту невозможность и быстро вернуться, но решатели с открытым исходным кодом (CBC или GLPK) могут работать очень долго или навсегда (я ждал несколько минут и сдался).
Я решил эту проблему здесь, используя ограничение времени для решателя и предположив, что проблема невозможна, если до этого предела не было найдено решение.Вы можете сделать что-то подобное в своем рекурсивном подходе, например, установить ограничение на количество шагов, которые нужно предпринять.Даже если вам нужны тысячи или миллионы шагов, подход линейного программирования имеет тенденцию работать хорошо (см. Последний пример), потому что он быстро приближается к правильному решению, а затем уточняется, чтобы получить точное соответствие.Я предполагаю, что рекурсивный подход займет слишком много времени в этом случае.Но, возможно, вам удастся разработать случаи, когда подход линейного программирования не может найти решение в установленные сроки, даже если решение существует.
... После дальнейшей проверки я обнаружил, что решатель CBCне работает хорошо, когда проблема численно плохо определена или требует много ответвлений.Например, это время ожидания, хотя ответ возможен: position(10, 100000, 100001, 10000000).И это сообщает о неверном ответе: position(10, 10000000, 10000001, 10000000) (счастлив использовать почти правдивый ответ 10 + 1 * d2 = 10000000).С другой стороны, эти случаи также могут быть очень трудно решить с помощью метода грубой силы.Так что, возможно, более глубокое понимание природы проблемы поможет.(Я постараюсь сделать это позже, но я уже слишком долго болтал!)