使用递归创建贪婪算法

Question

对于一个赋值，我必须使用递归函数编写一个Greedy算法，但我似乎不知道如何做到这一点。

任务是制定一条从一个城市到另一个城市的路线，每次都去他们之间距离最小的城市，但不能多次访问城市。

现在我有下面的代码，当然还远远没有完成，因为它甚至没有任何递归，也没有给出正确的结果。如果这段代码不太正确，我也不会感到惊讶。我得到的结果是[1，2，1，1]，这意味着路线将从城市0到1，到2，到1，再到1。答案应该是[1,2,3]。

我已经尝试这个代码太久了，似乎就是想不通。我知道我必须做什么：取最低距离的索引，检查该索引是否已经在列表v中，如果是，取第二低距离，然后再次检查。但我不知道如何将其放入代码中并包含递归。

有人能给我一些提示来帮助我或链接我的示例代码吗？

PS我不允许使用任何导入函数，这项任务是为了在我的大学上一门相对简单(尽管对我来说并不简单(的编程课程

v = []
def append_list_with_nearest_unvisited(visited, distances):                  
city = 0
for n in range(len(distances)):
if city in v:
i = min(j for j in distances[n] if j > 0) #take lowest distance
h = min(k for k in distances[n] if k > i) #take second lowest distance because the true lowest distance is a visited city
city = distances[n].index(h) #city visited is the index of the lowest distance
v.append(city)

else:
i = min(j for j in distances[n] if j > 0) #take lowest distance
city = distances[n].index(i)
v.append(city)
print(v)
append_list_with_nearest_unvisited(v, [[0,2,3,4],[2,0,4,5],[3,4,0,6],[4,5,6,0]])

Answer 1

我想你要问的是类似的问题

nodes = [0,1,2,3]
distanceMat = [
[0,2,3,4],
[2,0,4,5],
[3,4,0,6],
[4,5,6,0]
]
route = []
distance = []
startNode_ = 0
destinationNode_ = 3

def findRoute(currentNode, destinationNode):
if currentNode not in route:
route.append(currentNode)
if currentNode == destinationNode:
return
else:
shortestDistance = min(j for j in distanceMat[currentNode] if j > 0)
nextNode = distanceMat[currentNode].index(shortestDistance)
while nextNode in route:
shortestDistance = min(k for k in distanceMat[currentNode] if k > shortestDistance)
nextNode = distanceMat[currentNode].index(shortestDistance)
route.append(nextNode)
distance.append(shortestDistance)
findRoute(nextNode, destinationNode)

findRoute(startNode_, destinationNode_)
print('Route: ', route, 'nDistance: ', distance)

Answer 2

很酷的问题，你可以做smth。像这样：

def f(visited, dist):
if visited == []:
current_node = 0
else:
current_node = visited[-1]
distances = dist[current_node]
# find node with shortest path
c=-1
while True:
smallest_item = min(j for j in distances if j > c)
next_node = distances.index(smallest_item)
if  next_node != 0 and next_node not in visited:
break
else:
c = smallest_item

visited.append(next_node)
# check whether we seen all nodes:
if len(visited) == len(dist)-1:
return visited
else:
return f(visited, dist)

route = f([], [[0,2,3,4], [2,0,4,5],[3,4,0,6], [4,5,6,0]])
print(route)