Мне нравится этот вопрос - это интересно.
Я не уверен, как бы я это написал, но это всего лишь мысли из головы.
По сути, вы имеете дело с Манхэттенским расстоянием здесь, поскольку вы не используете диагонали. Таким образом, вам нужно знать кратчайший путь и извлечь из него. Если ваша конкретная стоимость меньше расстояния до Манхэттена, путь невозможен. Если он равен, идеальный путь - это ваш кратчайший путь.
Как только вы выходите за рамки этого, все становится немного сложнее, потому что у вас есть несколько решений вашей проблемы. Возможно, вам удастся получить грубый ответ, но я не знаю, есть ли не наивный способ сделать это. (Обратите внимание, что это всего лишь мысли из головы, так что ...)
Также обратите внимание, что для некоторых ситуаций не будет решения, потому что вы используете расстояние Манхэттен! Например, если у вас есть сетка 6x6 с начальной точкой в одном углу и конечной точкой в противоположном углу, вы можете закончить конечную точку за 10 шагов, но не за 11 (потому что вам нужно удвоиться на себя). Уверен, в этом есть правило, но я должен его вывести. (Опять же, в макушке моей головы.) ( РЕДАКТИРОВАТЬ: Я понял это - это на самом деле не правило как таковое, но ваши конкретные затраты не могут находиться между кратчайшим расстоянием пути и вторым кратчайшим расстояние пути. Второй кратчайший путь в манхэттенской сетке должен быть n + 2, я полагаю.)
Так что в принципе ... я думаю, что можно написать что-то вроде этого, но я не думаю, что вы можете легко вычислить это, не проверяя множество возможностей. Вы можете оптимизировать конкретные случаи с помощью правил, но как только вы это сделаете, я думаю, что вы застряли.
Впрочем, попробуйте. Звучит довольно интересно!
ВТОРОЕ РЕДАКТИРОВАНИЕ: Я только что понял ... Ваши затраты на путь всегда будут увеличиваться на два (опять же, из-за расстояния Манхэттена). Это означает, что вы можете оптимизировать немного больше, если вы знаете свое кратчайшее расстояние; Ваша конкретная стоимость должна быть кратна 2 плюс кратчайшее расстояние. В алгоритмическом выражении у вас будет определенная стоимость = 2n + кратчайшее расстояние.
Однако после этого вам придется перебрать его.
Надеюсь, это поможет.
ТРЕТЬЕ РЕДАКТИРОВАНИЕ (и, надеюсь, последнее): Я, наверное, немного педантичен здесь (и я, наверное, выясняю, что другие разобрались со мной до меня), но вот сделка. Если вы знаете свою конкретную стоимость и знаете кратчайшее расстояние пути, вы можете фактически взять разницу между ними и разделить на два, чтобы выяснить, сколько петель вам нужно на вашем пути. Циклы могут «складываться» (и я имею в виду, что вы можете запустить цикл и продолжить его на расстоянии; это «удвоение назад»), поэтому вы можете оптимизировать даже дальше , проверяя только пути, которые иметь определенное количество петель. Однако к этому времени вы в значительной степени нашли возможный путь к конечному узлу (при условии, что препятствия не блокируют все возможные пути, которые вы нашли). Таким образом, грубое принуждение будет необходимо только для того, чтобы избежать каких-либо препятствий. Я надеюсь, что это имело смысл.