两个不同算法的计数器阵列的结果相同 [英] Same result for two arrays of counters of different algorithms

问题描述

我正在尝试建立一个程序，比较15个游戏中算法BFS，DFS，A *（有两个启发式）的笔画数。

我的计数器对BFS和DFS的两个计数器阵列以及两个A *计数相同的结果。然而，我正在使用实际使用main（类Project）中的四个不同数组，并且我为这些笔划分配了四个不同的变量。

代码的一部分在我看来，不正确的是一个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真的是一个相似的（）。* b
$ b

  while（！frontier.isEmpty（））{
 number_of_strokes_DFS + = 1; 
 if（System.currentTimeMillis（） -  startTime> 10000）break; 
 //我们从边界
 current_state = frontier.pop（）中移除当前状态; 
 //我们从当前状态获得所有可能的操作
 actions = current_state.getActions（）; 
 //我们将当前状态添加到已经探索过的节点
 explored_nodes.add（current_state）; 
 //System.out.println(current_state）; 
 path.add（current_state）; 
 
 //我们发现目标
 if（goal_test（current_state））{
 / * for（State visited：path）{
 System.out.println（访问）; 
} * / 
 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; 
} 
 
 //我们为每个孩子创建
（行动：行动）{
 //System.out.println（action：+ action） ; 
 //我们从执行current_state 
 State child = current_state.execute（action）获得一个孩子; 
 //System.out.println（我们执行了动作）; 
 if（！explored_nodes.contains（child）&&！frontier.contains（child））{
 //这个孩子还没有被探索过，也没有在边界我们将它添加到最后一个
 frontier.push（孩子）; 
} 
} 
 
} 
 array_number_of_strokes_dfs.add（-1）; 
 
返回finalState; 
 
} 
  

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

  array_number_of_strokes_dfs.add（0）; 
  

我确实看到了差异......

<你有什么想法吗？

结果如下：

 笔画BFS：[3， 27,27,26,26,2631,7] 
笔画DFS [3,27,27,26,26,2631,7] 
  

解决方案

如果 frontier 是 Stack 或类似的东西，比 add 类似于 push ，所以你的 BFS 实际上也在进行深度优先搜索。如果你真的想在开头插入（如果你在每次迭代时 pop 元素，你想要做的事情），你想要调用 .add（ 0，elem）（注意 0 - 要插入的索引）而不是 .add（elem） ，因此它实际上是在开头插入的。

I'm trying to build up a program comparing number of strokes of algorithms BFS, DFS, A* (which has two heuristics) on a game of fifteen.

My counter count the same result for the two arrays of counters of BFS and DFS and both A*. Yet, I'm using actually using four different arrays from a main (class Project) and I'm assigning four different variables for those strokes.

The part of the code that isn't right is, to my mind, a while loop which explores the son of a vertice as far as possible (for BFS) or discovering each following nodes (for BFS). The difference, which is of the utmost importance, is the last line of code which is either frontier.push(child);, for DFS, or frontier.add(child); for BFS.

Each time we enter the loop, the number of strokes is incremented

number_of_strokes_DFS+=1;

or

number_of_strokes_BFS+=1;

When we find the final state we add the result to the array of the number of strokes:

array_number_of_strokes_dfs.add(number_of_strokes_DFS);

or

array_number_of_strokes_bfs.add(number_of_strokes_BFS);

Here is the guilty code finally (actually only DFS as far as BFS is really a lookalike except the last line).

 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;

}

Here is the actual problem as far as when I let array_number_of_strokes_dfs.add(number_of_strokes_DFS);, for instance, I always get the same result as BFS in the array. It might happen once, but not every time!!! Whereas if I add a zero

array_number_of_strokes_dfs.add(0);

I do see the difference...

Do you have any ideas?

Here are the result:

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

解决方案

If frontier is a Stack or something similar, than add is analogous to push, so your BFS is in fact also doing a depth-first search. If you actually want to insert at the beginning (something you want to do if you pop elements on each iteration), you want to call .add(0, elem) (note the 0 -- the index at which to insert) instead of .add(elem), so that it is actually inserted at the beginning.

这篇关于两个不同算法的计数器阵列的结果相同的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！