广度优先搜索算法 JAVA 8 拼图

Question

我试图为8益智游戏实现广度优先算法。我知道这不是一个新案例，网络上有很多解决方案，但我想按照我的思维方式做到这一点。

此代码已找到节点结果，即

123
456
780

但是需要350,000步才能做到！

任何想法将不胜感激！=)

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

Answer 1

您可以确保不会向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，后者则不然。

---

如果这没有帮助，您可以尝试使用 A* 算法，该算法涉及为每个节点添加一个启发式函数，即到目标的距离 - 这允许我们首先探索更接近目标的节点，通常会导致到达那里的步骤更少。

一个好的启发式函数可能是每个图块与其目标位置之间的曼哈顿距离之和。

请注意，这将涉及对当前代码的大量更改。

Answer 2

根据维基百科，这个谜题有9!/2 = 181440种可能的可解决的组合。如果您检查每个节点中的每一个组合（您没有，但它使计算更容易），它会进行大约(9!/2) * 9 = 1,632,960步骤。因此，如果它将您的算法350,000步骤，我认为没有问题，因为计算机可以非常快速地完成这些步骤。