我正在尝试为8拼图游戏实现广度优先算法。我知道这不是一个新问题，网上已经有很多解决方案，但我希望按照我自己的思路来实现它。

这段代码已经找到了节点结果，即

123456780

但它需要350,000步才能完成！

任何建议都将不胜感激!=)

    //这个方法接收一个`Nodo`对象的集合，每个对象都会被检查并与最终目标进行比较
    public void percorreNodos(Collection<Nodo> nodosBase)
    {
        //在这个类中，我有一个数组，包含所有已经检查过的节点的ID
        //节点的ID是其表示：123456780, 354126870，等等。
        System.out.println("idsPercorrido.size() = " + idsPercorridos.size());
        //检查nodosBase集合中是否包含最终目标
        Iterator<Nodo> iterator =  nodosBase.iterator();
        while( iterator.hasNext() )
        {
            Nodo nodoBase = (Nodo) iterator.next();
            //如果当前节点已经被检查过，我们就不需要再次检查它
            idsPercorridos.add( nodoBase.getId() );
            //只是打印节点（系统输出）
            nodoBase.print();
            contPassos++;
            System.out.println( "\n" + contPassos + " 步（检查的节点数）..." );
            //检查这个节点是否是最终目标
            if( nodoBase.isObjetivoFinal() )
            {
                //设置指示结果已找到的变量
                encontrouObjetivo = true;
                System.out.println( "结果在 " + contPassos + " 步内达到..." );
                nodoBase.print();
                break;
            }
        }
        //现在我们知道nodosBase集合中没有一个节点是最终目标，我们将生成下一个要检查的子节点，并递归调用此函数
        //只是确认我们没有找到目标
        if(encontrouObjetivo == false)
        {
            //创建下一层边界
            Collection<Nodo> novaFronteira = new HashSet<Nodo>();
            for(Nodo nodoPai : nodosBase)
            {
                //为每个节点生成其子节点并添加到名为"novaFronteira"的集合中
                Collection<Nodo> filhos = nodoPai.gerarFilhos();
                for(Nodo filho : filhos)
                {
                    //idsPercorridos是一个包含我们检查过的所有节点ID的集合<String>，我们不希望检查一个节点超过一次！
                    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则不然。

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

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

请注意，这将涉及对你当前代码进行相当多的更改。