不同算法的两个计数器数组的结果相同

Question

我正在尝试构建一个程序来比较算法 BFS、DFS、A*（具有两个启发式算法）在十五人游戏中的笔画数。

我的计数器对 BFS 和 DFS 的两个计数器数组以及两个 A* 计数相同的结果。然而，我实际上使用了来自主（class 项目）的四个不同的数组，并且我为这些笔画分配了四个不同的变量。

在我看来，代码中不正确的部分是 while 循环，它尽可能探索顶点的子节点（对于 BFS）或发现每个后续节点（对于 BFS）。最重要的区别是代码的最后一行是 frontier.push(child);，对于 DFS，或 frontier.add(child);对于 BFS。

每次进入循环，笔画数都会递增

number_of_strokes_DFS+=1;

或

number_of_strokes_BFS+=1;

当我们找到最终状态时，我们将结果添加到笔画数数组中：

array_number_of_strokes_dfs.add(number_of_strokes_DFS);

或

array_number_of_strokes_bfs.add(number_of_strokes_BFS);

最后是有罪的代码（实际上只有 DFS 就 BFS 来说真的很像，除了最后一行）。

 while(!frontier.isEmpty()){
        number_of_strokes_DFS+=1;
     if(System.currentTimeMillis()-startTime>10000)break;
     // We remove the current state from the frontier
     current_state = frontier.pop();
     // We get all possible actions from the current state
     actions = current_state.getActions();
     // We add the current state to already explored nodes
     explored_nodes.add(current_state);
     //System.out.println(current_state);
     path.add(current_state);

     // we found the goal
     if(goal_test(current_state)){
         /*for(State visited :path){
         System.out.println(visited);
     }*/
            array_number_of_strokes_dfs.add(number_of_strokes_DFS);
         System.out.println("nombres de coups DFS"+number_of_strokes_DFS);
         number_of_strokes_DFS=0;
         return current_state;
     }

     // We create every child
     for (Action action : actions){
         //System.out.println("action : " + action);
         // we get a child from the execution of the current_state
         State child = current_state.execute(action);
         //System.out.println("we executed the action");
         if(!explored_nodes.contains(child)&&!frontier.contains(child)){
             // This child not being already explored nor int the frontier we add it to the last one
             frontier.push(child);
         }
     }

 }
    array_number_of_strokes_dfs.add(-1);

    return finalState;

}

就我让 array_number_of_strokes_dfs.add(number_of_strokes_DFS); 而言，这是实际问题，例如，我总是得到与数组中 BFS 相同的结果。它可能会发生一次，但不会每次都发生！！！而如果我添加一个零

array_number_of_strokes_dfs.add(0);

我确实看到了区别...

你有什么想法吗？

结果如下：

strokes BFS : [3, 27, 27, 26, 26, 2631, 7]
strokes DFS[3, 27, 27, 26, 26, 2631, 7]

Answer 1

如果 frontier 是 Stack 或类似的东西，那么 add 类似于 push，所以你的 BFS 实际上也在做深度优先搜索。如果你真的想在开头插入（如果你在每次迭代中 pop 元素你想做的事情），你想调用 .add(0, elem) （注意 0 - 的索引which to insert) 而不是 .add(elem)，这样它实际上是在开头插入的。

不同算法的两个计数器数组的结果相同

Same result for two arrays of counters of different algorithms

java

arrays

algorithm

breadth-first-search

depth-first-search