深度優先搜索發現最簡潔的路徑，但不是最短在蟒蛇

我尋找執導深度優先搜索，並找到最簡潔的路徑（用最少的節點）本次測試情況下小圖的權重，但不能以最短路徑TotalDistance和OutdoorDistance。該地圖是：其中節點給出a-> b（weight1，weight2）weight1 =節點之間的總距離，weight2 =節點之間的OutdoorDistance。目標是在保持低於maxTotalDist和maxDistOutdoors限制的同時找到最短路徑。深度優先搜索發現最簡潔的路徑，但不是最短在蟒蛇

1->2 (5.0, 2.0) 
3->5 (6.0, 3.0) 
2->3 (20.0, 10.0) 
2->4 (10.0, 5.0) 
4->3 (2.0, 1.0) 
4->5 (20.0, 10.0)

測試是：

def testSP4(): 
    nodes = [] 
    for name in range(1,6): 
     nodes.append(Node(str(name))) 
    g = WeightedDigraph() 
    for n in nodes: 
     g.addNode(n) 
    g.addEdge(WeightedEdge(nodes[0],nodes[1], 5.0, 2.0)) 
    g.addEdge(WeightedEdge(nodes[2],nodes[4], 6.0, 3.0)) 
    g.addEdge(WeightedEdge(nodes[1],nodes[2], 20.0, 10.0)) 
    g.addEdge(WeightedEdge(nodes[1],nodes[3], 10.0, 5.0)) 
    g.addEdge(WeightedEdge(nodes[3],nodes[2], 2.0, 1.0)) 
    g.addEdge(WeightedEdge(nodes[3],nodes[4], 20.0, 10.0)) 

    sp = directedDFS(g, '4', '5', 21, 11) 

    print sp 

    path = [] 

    for node in sp: 
     path.append(Node(node)) 

    print sumTotDistance(g, path), sumDistOutdoors(g, path)

而搜索算法本質：

def DFSShortest(digraph, start, end, maxTotalDist, maxDistOutdoors, dist1 = 0, dist2 = 0, path = [], shortest = None): 
    #assumes digraph is a WeightedDigraph 
    #assumes start and end are nodes in digraph 
    path = path + [Node(start)] 

    if Node(start) == Node(end): 
     if dist1 <= maxTotalDist and dist2 <= maxDistOutdoors: 
      return path 
    for [node, (weight1, weight2)] in digraph.edges[Node(start)]: 
     if node not in path: #avoid cycles 
      if shortest == None or (sumTotDistance(digraph, path) < sumTotDistance(digraph, shortest) \ 
      and sumDistOutdoors(digraph, path) < sumDistOutdoors(digraph, shortest)): 
       newPath = DFSShortest(digraph,node,end, maxTotalDist, maxDistOutdoors, dist1+weight1, dist2+weight2, path, shortest) 
       if newPath != None: 
        shortest = newPath 
    return shortest

測試testSP4（）給出了路徑SP = [ '4'， '5' ]與距離20，10，但給定的最短溶液是路徑[「4」，「3」，「5」]其中的距離是8，4.深度優先搜索是基於文本的書版本，但我已經介紹了權重約束條件。我已經嘗試了各種不同的條件安排（例如將<更改爲>），但這會使其他測試用例不正確。有人可以幫忙嗎？提前致謝。

來源

2016-04-21 Berwhale

如果您想要最短路徑，爲什麼要使用深度優先搜索？深度優先搜索不會給出最短路徑，並且沒有好的方法來調整它以提供最短路徑。 – user2357112

不幸的是這是一個任務，我們希望使用深度優先搜索。 – Berwhale

然後分配是錯誤的，或者你錯過了一個關鍵的細節。也許你的輸入圖有一些特殊的屬性，或者你應該在你的任務的中途切換算法，當你閱讀你的任務文本時掩蓋了這個問題。 – user2357112

好吧，我終於找到了（使用Bing！？）用的，實際工作條件下位置差了類似的基礎算法。我曾嘗試過這種變化，但在遞歸調用DFSShortest之前，我並沒有刪除if條件。搜索和條件的組合實際上正確地滿足了我們給定的測試用例。感謝幫助。

def DFSShortest(digraph, start, end, maxTotalDist, maxDistOutdoors, dist1 = 0, dist2 = 0, path = [], shortest = None): 
    #assumes digraph is a WeightedDigraph 
    #assumes start and end are nodes in digraph 

    path = path + [Node(start)] 

    if Node(start) == Node(end): 
     if (dist1 <= maxTotalDist and dist2 <= maxDistOutdoors): 
      return path 

    for [node, (weight1, weight2)] in digraph.edges[Node(start)]: 
     if node not in path: #avoid cycles 
      newPath = DFSShortest(digraph,node,end, maxTotalDist, maxDistOutdoors, dist1+weight1, dist2+weight2, path, shortest) 
      if newPath: 
       if not shortest or (sumTotDistance(digraph, newPath) < sumTotDistance(digraph, shortest)\ 
       and sumDistOutdoors(digraph, newPath) < sumDistOutdoors(digraph, shortest)): 
        shortest = newPath 

    return shortest

來源

2016-04-22 03:09:59 Berwhale

深度優先搜索發現最簡潔的路徑，但不是最短在蟒蛇

回答

相關問題