Почему мой код рекурсивного рыцаря на Python запускает только первый стек?
Таким образом, код заключается в том, чтобы найти наименьшее количество раундов, которое потребуется коню в шахматах, чтобы пройти от начала до цели. А также код должен быть рекурсивным. У меня проблема с этим кодом. . Моя проблема в том, что он проходит не через все стеки, а только через один «путь» возможных ходов, а затем доставляет количество раундов, необходимое для этого пути.
Например, с помощью print(knight([1,1], [5,2], [])) он возвращает 17 вместо 3
moves = ([1,2],[2,1],[-1,2],[-1,-2],[1,-2],[2,-1],[-2,1],[-2,-1])
def knight(start, goal, visited):
if start == goal:
return 0
else:
visited.append(start)
possibles =[]
makeable= []
for x in range(8):
possibles.append([start[0] + moves[x][0],start[1] + moves[x][1]])
for i in range(8):
if possibles[i] not in visited and possibles[i][0]<9 and possibles[i][1]<9 and possibles[i][0]>0 and possibles[i][1]>0:
makeable.append(knight(possibles[i],goal,visited))
if makeable:
return min(makeable)+1
else:
return 99
print(knight([1,1], [5,2], []))
спасибо, я сделал. Надеюсь, это поможет понять это
Ответы 1
Я предполагаю, что ваш besucht хранит путь. Я не понимаю его использования, так как он нигде в коде не используется. В любом случае, я перестану притворяться, что я на CodeReview, и отвечу на ваш вопрос.
Причина ошибки в том, что вы передаете список besucht по кругу. Когда вы передаете списки в качестве аргументов функции, они передаются как ссылка/указатель вместо копии списка. В результате более поздние вызовы функций будут изменять исходный besucht, вызывая ошибки в if possibles[i] in besucht.
Чтобы исправить это, вместо этого передайте копию пути. (Очевидно, что это не самый эффективный способ, но здесь он работает). См. код.
# python
moves = ([1,2],[2,1],[-1,2],[-1,-2],[1,-2],[2,-1],[-2,1],[-2,-1])
def springerzug(start, end, path, sofar = 0):
if start == end:
return 0
# Terminate if path is too long
if len(path) > 9:
return 999
# omit the else
possibles = []
ergebnisse = [98] # default value
for x in range(8):
possibles.append([start[0] + moves[x][0], start[1] + moves[x][1]])
for i in range(8):
if 0 < possibles[i][0] < 9 and 0 < possibles[i][1] < 9 \
and possibles[i] not in path:
ergebnisse.append(springerzug(possibles[i], end, path.copy() + [possibles[i]]))
return min(ergebnisse)+1
print(springerzug([1,1], [5,2], []))
(Примечание: ваш код, использующий DFS для кратчайшего пути, крайне неэффективен. Пожалуйста, поищите Breath-First Search, чтобы другие люди в stackoverflow не критиковали вас за ваш неэффективный код.)
спасибо, чувак, я знаю, что это неэффективно, но это задача в моем классе информатики
@unsympathisch Было бы здорово принять ответ :)
Я думаю, что больше людей хотели бы помочь вам, если бы вы объяснили немного больше, что этот код должен делать и как он должен работать в вашем понимании. Кроме того, всем легче понять код, если он написан на английском языке.