找到您可以訪問的頂點的最大數量的算法，給定一個起始點和您可以行進的最大距離

Question

我有一個具有正邊權重的無向圖。我得到了一個起點和我可以旅行的最大距離，最後，我必須回到起點。什麼樣的算法可以爲我做到這一點，並給我的結果？

我很瞭解java，所以如果可以的話，請讓代碼示例看起來類似於java。

Answer 1

就像我說的DFS應該做的伎倆，這個示例代碼給出了這個想法。 但要注意，此示例代碼不處理循環引用，你將不得不做

public class Answer { 

    private static final int MAX_WEIGHT = 11; 

    public static void main(String[] args) { 

     Node node1 = new Node("node 1"); 
     Node node1_1 = new Node("node 1-1"); 
     Node node1_1_1 = new Node("node 1-1-1"); 
     Node node1_2 = new Node("node 1-2"); 
     Node node1_2_1 = new Node("node 1-2-1"); 
     Node node1_2_1_1 = new Node("node 1-2-1-1"); 

     node1.addNeighbour(node1_1, 1); 
     node1_1.addNeighbour(node1_1_1, 2); 

     node1.addNeighbour(node1_2, 1); 
     node1_2.addNeighbour(node1_2_1, 2); 
     node1_2_1.addNeighbour(node1_2_1_1, 3); 

     System.out.println("max of nodes = " + travel(node1, 0)); 

    } 

    private static int travel(Node node, int totalWeight) { 
     int maxNodes = 1; 

     for (Map.Entry<Node, Integer> entry : node.neighbours.entrySet()) { 
      Integer weight = entry.getValue(); 

      int nodes = 1; 
      if ((totalWeight + weight) * 2 <= MAX_WEIGHT) { 
       nodes += travel(entry.getKey(), totalWeight + weight); 
      } 

      if (nodes > maxNodes) { 
       maxNodes = nodes; 
      } 
     } 

     return maxNodes; 
    } 

} 

class Node { 

    String id; 
    Map<Node, Integer> neighbours; 

    public Node(String id) { 
     this.id = id; 
     neighbours = new HashMap<Node, Integer>(); 
    } 

    public void addNeighbour(Node node, int weight) { 
     neighbours.put(node, weight); 
    } 

    @Override 
    public String toString() { 
     final StringBuilder sb = new StringBuilder("Node{"); 
     sb.append("id='").append(id).append('\''); 
     sb.append(", neighbours=").append(neighbours); 
     sb.append('}'); 
     return sb.toString(); 
    } 
} 

Answer 2

我現在意識到這仍然是NP難的，即使頂點可以參觀不止一次：Hamiltonian Path是NP-hard甚至在未加權的圖表上，所以我們可以自由地使用任意選擇的權重來創建問題的一個實例。具體來說，給定哈密頓路徑的實例（G =（V，E），k），我們可以創建一個實例（G'=（V'，E'），w，s，d），其中：

• V '= V，再加上一個新的頂點，S
• E'= E，加在V中的邊緣（S，U）爲每一個頂點u
• 每條邊的權重w（e）中E'中的e是1
• 起點是s
• 最大總行程距離是| V | +1。

如果解決這個實例| V | +1不同的頂點，那麼顯然它包含G」的每個頂點恰好一次，所以去除週期的頂點旨意通過所有剩餘的頂點離開的路徑即在原始圖G中的哈密爾頓路徑。如果該實例的解小於| V | +1，則G中不存在哈密爾頓路徑 - 因爲如果有的話，我們確實已經得到| V | +1。因此，如果您的問題可以在多項式時間內解決，那麼NP-complete問題也可以解決。這意味着你的問題很難在多項式時間內解決。