Java - 深度优先搜索

Question

我已经在Java中实现了两种算法，并且在测试深度优先搜索时，当有12个节点时，似乎需要花费大量的时间，当使用A *它在几秒钟内完成时，我只是想知道这是预期还是我做错了什么？它在我输入这个内容后在后台运行搜索并进行了几分钟。 我通常不介意，但我必须测试多达500个节点，这可能需要几天的时间，这是我应该期望的，还是我做错了什么？

谢谢！

---

import java.util.*; 


@SuppressWarnings({ "rawtypes", "unchecked" }) 

public class DepthFirstSearch { 

    Routes distances; 
    static Routes routes; 

    int firstNode; 
    String result = new String(); 

    ArrayList firstRoute, bestRoute; 
    int nodes = 0; 
    int routeCost = 0; 
    int bestCost = Integer.MAX_VALUE; 

    public DepthFirstSearch(Routes matrix, int firstNode) { //new instance 

     distances = matrix; 
     this.firstNode = firstNode; 
    } 


    public void run() { //run algorithm 
     long startTime = System.nanoTime(); 
     firstRoute = new ArrayList(); 
     firstRoute.add(firstNode); 
     bestRoute = new ArrayList(); 
     nodes++; 
     long endTime = System.nanoTime(); 

     System.out.println("Depth First Search\n"); 
     search(firstNode, firstRoute); 
     System.out.println(result); 
     System.out.println("Visited Nodes: "+nodes); 
     System.out.println("\nBest solution: "+bestRoute.toString() + "\nCost: "+bestCost); 
     System.out.println("\nElapsed Time: "+(endTime-startTime)+" ns\n"); 
    } 


    /** 
    * @param from node where we start the search. 
    * @param route followed route for arriving to node "from". 
    */ 
    public void search (int from, ArrayList chosenRoute) { 

     // we've found a new solution 
     if (chosenRoute.size() == distances.getCitiesCount()) { 

      chosenRoute.add(firstNode); 
      nodes++; 

      // update the route's cost 
      routeCost += distances.getCost(from, firstNode); 

      if (routeCost < bestCost) { 
       bestCost = routeCost; 
       bestRoute = (ArrayList)chosenRoute.clone(); 
      } 

      result += chosenRoute.toString() + " - Cost: "+routeCost + "\n"; 

      // update the route's cost (back to the previous value) 
      routeCost -= distances.getCost(from, firstNode); 
     } 
     else { 
      for (int to=0; to<distances.getCitiesCount(); to++){ 
       if (!chosenRoute.contains(to)) { 

        ArrayList increasedRoute = (ArrayList)chosenRoute.clone(); 
        increasedRoute.add(to); 
        nodes++; 

        // update the route's cost 
        routeCost += distances.getCost(from, to); 

        search(to, increasedRoute); 

        // update the route's cost (back to the previous value) 
        routeCost -= distances.getCost(from, to); 
       } 
      } 
     } 

    } 

} 

Answer 1

你没有正确更新chosenRoute;你总是添加“firstNode”与你的ArrayList具有相同的值，我想你应该添加访问节点。 我会尽力检查以后