找到您可以访问的顶点的最大数量的算法，给定一个起始点和您可以行进的最大距离

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问题也可以解决。这意味着你的问题很难在多项式时间内解决。