Java-深度优先搜索 [英] Java - Depth first search

问题描述

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

I have implemented two algorithms in Java and when testing depth first search it seems to be taking an incredible amount of time when there are 12 nodes, when using A* it completes it in seconds, I was just wondering if this is to be expected or am I doing something wrong? Its running the search in the background now as I type this and has been going for a few minutes. I wouldnt normally mind but ive got to test up to 500 nodes which could take days at this rate, is this something I should expect or am I doing something wrong?

谢谢！

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);
                }
            }
        }

    }

}

推荐答案

您没有正确更新selectedRoute；您总是将具有相同值的 firstNode添加到您的arraylist中，我认为您应该添加被访问的节点。
我会稍后再检查

you are not updating chosenRoute correctly; you always add "firstNode" with the same value to your arraylist, I think you should add the visited node. I will try to check that later

这篇关于Java-深度优先搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！