java - 广度优先搜索算法JAVA 8-puzzle

我试图实现8益智游戏的宽度优先算法。我知道这不是一个新的案例，网络上有很多解决方案，但我想用我的思维方式去做。
此代码已经找到节点结果，即

123
456
780

但要走35万步！
任何想法都将不胜感激！
=）

    //This method receives a Collection of `Nodo` objects, each one will be checked and compare with the finalGoal

     public void percorreNodos(Collection<Nodo> nodosBase)
            {
                //In this class a have an array that has all the IDs os nodes that already has been checked
                //The ID of a Node, is the representation: 123456780, 354126870 , etc..
                System.out.println("idsPercorrido.size() = " + idsPercorridos.size());
                //Check if the collection nodosBase contains the finalGoal
                Iterator<Nodo> iterator =  nodosBase.iterator();
                while( iterator.hasNext() )
                {
                    Nodo nodoBase = (Nodo) iterator.next();
                    //If this current node has already been checked, we dont have to check it again
                    idsPercorridos.add( nodoBase.getId() );
                            //Just print the node (sysout)
                    nodoBase.print();
                    contPassos++;
                    System.out.println( "\n" + contPassos + " STEPS(number of nodes checked)..." );
                    //Check if this node is the final goal
                    if( nodoBase.isObjetivoFinal() )
                    {
                                    //set the variable indicating that the result has been found
                        encontrouObjetivo = true;
                        System.out.println( "Resultado alcancado EM " + contPassos + " PASSOS..." );
                        nodoBase.print();
                        break;
                    }
                }

                // Now that we know that no one Node of nosoBase collection is the final goal, we are going to generate the next children to be checked, and call this function recursively
                //Just confirm that we didnt find the goal
                if(encontrouObjetivo == false)
                {
                            //Creates the next frontier
                    Collection<Nodo> novaFronteira = new HashSet<Nodo>();

                    for(Nodo nodoPai : nodosBase)
                    {
                                    //Generate each Node its childrens and add to a collection called "novaFronteira"
                        Collection<Nodo> filhos = nodoPai.gerarFilhos();
                        for(Nodo filho : filhos)
                        {
//idsPercorridos is a collection<String> which contains all the nodes ids that we checked, we dont want to check a node more than one time !
                            if( idsPercorridos.contains( filho.getId() ) == false )
                            {
                                novaFronteira.add( filho );

                            }
                        }
                    }
                    this.percorreNodos( novaFronteira );
                }

            }

最佳答案

您可以确保不向novaFronteira添加重复的元素。
没有什么可以阻止此代码：

for(Nodo nodoPai : nodosBase)
{
    Collection<Nodo> filhos = nodoPai.gerarFilhos();
    for(Nodo filho : filhos)
    {
        if( idsPercorridos.contains( filho.getId() ) == false )
        {
            novaFronteira.add( filho );
        }
    }
}

从添加多个重复节点到novaFronteira。
如果您要添加到If语句中的idsPercorridos，这将防止这种情况发生，并减少步骤，不过，根据您的数据和数据结构的具体情况，添加的此调用的运行时间实际上可能会使它比原来花费的时间更长。
如果问题是运行时间，则应确保idsPercorridos是TreeSet或HashSet，因为这允许高效的contains调用，而不是ArrayList或LinkedList，后者不允许。
如果这没有帮助，您可以尝试使用the A* algorithm来代替，这涉及到向每个节点添加一个启发式函数，即到目标的距离-这允许我们首先探索离目标更近的节点，通常会减少到达目标的步骤。
一个好的启发式函数可能是每个分块与其目标位置之间的Manhattan distances之和。
注意，这将涉及到对当前代码的一些更改。