BFS 的三个计数器阵列和两个具有不同启发式的 A* 的相同结果
Same result for three arrays of counters of BFS and two A* with different heuristics
我正在尝试建立一个程序来比较算法 BFS 和两个不同的 A*（有两个启发式）在十五人游戏中的笔画数。
我的问题是计数器对BFS和A*的三个计数器数组计数相同的结果。然而，我实际上使用了主（class 项目）中的三个不同数组，并且为这些笔画分配了三个不同的变量。
我认为问题来自A*。对于他们每个人，我从父亲开始，然后计算其启发式并将他添加到边界。
虽然边界不是空的，但我看看初始状态是否是十五人游戏的最终状态，否则我将其从边界中移除，然后我们搜索他的儿子。我为他们所有人设置他们的 g 值，我计算他们的每个启发式以最终得到他们的 f 值。如果他们还没有在边境，我就把他们加进去。然后我将边界中第一个的 F 值与边界内的每个值进行比较，并将具有最佳 F 值的一个实例化为 current_state.
int best_f_value=frontier.get(0).getFValue();
for(State s : frontier){
if(s.getFValue()<=best_f_value){
best_f_value=s.getFValue();
current_state=s;
}
}
然而，在寻找计数器时，我总是对 BFS 和 A* 具有相同的笔划数，其中启发式的错位图块数和 A* 具有曼哈顿距离的启发式。这可能会出现一次，但不会总是出现！！
我认为问题在于 A* 的函数，而不是用于计算其启发式的函数。因此这里是第二个 A* 的代码，他看起来很像第一个只是错位的 tiles heurisitc。
第二个A*码
public State aStar2(){
State child;
System.out.println("we entered A_star with Manhattan distance");
System.out.println("final:\n"+finalState);
/** current state of dfs algorithm **/
State current_state;
current_state = initialState;
current_state.computeHeuristic2();
current_state.computeValueF2();
//int best_f_value= current_state.getFValue();
int current_state_g_value = 0;
System.out.println(initialState);
// get alwhile(!frontier.isEmpty()){l possible actions from the given node
List<Action> actions = current_state.getActions();
//frontier is a Stack displaying not currently explored nodes
LinkedList<State> frontier = new LinkedList<State>();
// frontier already contains the first node
frontier.push(initialState);
// explored_nodes contains all explored nodes.
LinkedList<State> explored_nodes = new LinkedList<State>();
// this List is used to show the path
LinkedList<State> path = new LinkedList<State>();
while(!frontier.isEmpty()){
number_of_strokes_A2+=1;
// we found the goal
if(goal_test(current_state)){
for(State visited :path){
System.out.println(visited);
}
array_number_of_strokes_A2.add(number_of_strokes_A2);
System.out.println("nombre de coups A2 : " + number_of_strokes_A2);
number_of_strokes_A2=0;
System.out.println("on a réussi : \n" + current_state);
return current_state;
}
// We remove the current state from the frontier
// VERIFY THIS IS OKAY !!!
frontier.remove(current_state);
// 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);
current_state_g_value = current_state.getValueG();
// We create every child
for (Action action : actions){
// we get a child from the execution of the current_state
child = current_state.execute(action);
child.setValueG(current_state_g_value);
child.computeHeuristic2();
child.computeValueF2();
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.add(0,child);
}
}
int best_f_value=frontier.get(0).getFValue();
for(State s : frontier){
if(s.getFValue()<=best_f_value){
best_f_value=s.getFValue();
current_state=s;
}
}
}
return finalState;
}
问我是否需要第一个A*来比较。
下面是启发式方法。
启发式
它们在另一个文件中。我不认为他们有任何罪过。
public void computeValueF(){
// to be completed
f_value = getValueG() + getHeuristic();
}
public void computeValueF2(){
// to be completed
f_value = getValueG() + getHeuristic2();
}
public int getFValue(){
return f_value;
}
@Override
public int getFValue2(){
return f_value;
}
public int getHeuristic(){
return h_value;
}
public int getHeuristic2(){
//somme de la distance de Manhattan entre lemplacement couvrant de chaque case � sa position finale
int h2=0;
for(int i=0;i<9;i++){
h2+=Integer.valueOf(puzzle.charAt(i))%3-i%3+Integer.valueOf(puzzle.charAt(i))/3-i/3;
}
return h2;
// to be completed
}
@Override
public int compareTo(Searchable<Puzzle, PuzzleAction> o) {
// TODO Auto-generated method stub
if(this.getHeuristic()> o.getHeuristic());
return 0;
}
@Override
public void setValueG(int cost) {
// TODO Auto-generated method stub
g_value = cost+1;
}
@Override
public int getValueG() {
// TODO Auto-generated method stub
return g_value;
}
@Override
public void computeHeuristic() {
// TODO Auto-generated method stub
//nombre de cases mal placees
for(int i=0;i<9;i++){
if((Integer.valueOf(puzzle.charAt(i))-i)!=0){
h_value+=1;
}
}
}
@Override
public void computeHeuristic2() {
// TODO Auto-generated method stub
int h2=0;
for(int i=0;i<9;i++){
h2+=Integer.valueOf(Math.abs(puzzle.charAt(i))%3-i%3)+Math.abs(Integer.valueOf(puzzle.charAt(i))/3-i/3);
}
this.h2_value=h2;
}
结果
以下是笔划数的结果：
strokes BFS : [9, 7, 33, 33, 53, 53, 51]
strokes AStar1[9, 7, 33, 33, 53, 53, 51]
strokes AStar2[9, 7, 33, 33, 53, 53, 51]
参考资料
这个问题与 类似，但不同的是它在实现 BFS 和 DFS 方面的差异
更新：尝试从实际当前位置到目标进行启发
Ishmael 关于我保持不变的启发式方法是正确的。因此，我试图修改启发式计算方法，以便参考当前状态而不是永远不会改变的东西。这是Puzzle.java
中的方法
@Override
public void computeHeuristic1(String s) {
// TODO Auto-generated method stub
//nombre de cases mal placees
h1_value=0;
for(int i=0;i<9;i++){
if((Integer.valueOf(s.charAt(i))-i)!=0){
h1_value+=1;
}
}
}
我们将在 Problem.java
中使用
child.computeHeuristic1(child.toString());
如果需要，我可以添加更多代码。
我得到了那些启发式方法：
array_heuritics_1 : [9, 9, 9, 9, 9, 9, 9, 9
array_heuritics_2 : [130, 131, 131, 129, 129, 128, 1
最后一个是异常的，因为每个瓷砖最多可以带来 3+3 的启发值。因此，启发式 > 51 的东西是站不住脚的。
所以我试图展示测试在做什么，我发现了一些有趣的东西：
the child.toString :
1 2 5
3 4 .
6 7 8
the value :
i : 0 & s.charAt(i) : 1
i : 1 & s.charAt(i) : .
i : 2 & s.charAt(i) : 2
i : 3 & s.charAt(i) :
i : 4 & s.charAt(i) :
i : 5 & s.charAt(i) :
i : 6 & s.charAt(i) :
i : 7 & s.charAt(i) : 6
i : 8 & s.charAt(i) : 7
i : 0 & s.charAt(i) : 1
i : 1 & s.charAt(i) : .
i : 2 & s.charAt(i) : 2
i : 3 & s.charAt(i) :
i : 4 & s.charAt(i) :
i : 5 & s.charAt(i) :
i : 6 & s.charAt(i) :
i : 7 & s.charAt(i) : 6
i : 8 & s.charAt(i) : 7
实际上我们不是逐个数字进行测试，而是逐个字符进行测试，并且有一些空白 space!
首先，让我们考虑一下如果您的 A* 不使用任何启发式算法会发生什么（如果 getFValue 只是 returned getValueG）。请注意，当算法开始时，它在 frontier 中只有一个节点，因此它会被选中。在每次连续迭代中，边界中的值将按 cost 降序排序（如果你在纸上画几个例子，你可以通过归纳法证明），边界中第一个元素的成本将是要么等于最后一个的成本，要么更大。现在，当您 运行 选择 state 的循环时，您将始终选择最后一个元素，因为它将具有最小的 FValue，并且在这些元素中您总是选择最后一个.换句话说，如果没有启发式方法，您的 A* 将表现得与您的 BFS 完全一样（它已经选择了最后一个元素）。
现在假设您的启发式只是一个常量，例如您的 getFValue 被实现为 return getValueG + constant。您可以通过遵循与上述非常相似的逻辑再次证明它的行为就像只是 BFS 一样——如果您向比较的值添加一个常量，它们将以相同的方式进行比较。
最后，很容易证明你的启发式总是return相同的值。请注意，它们仅依赖于常量 puzzle。它们绝不取决于代理的当前位置。曼哈顿距离启发式应该是从 当前位置 到地图上所有目标位置的曼哈顿距离相加（或者更确切地说，只是到最近的一个，因为启发式会更有意义）。相反，它计算的东西根本不依赖于当前位置，这是错误的。由于它 returns 的值始终相同，因此由于我在上面提供的原因，它的行为类似于 BFS。
我正在尝试建立一个程序来比较算法 BFS 和两个不同的 A*（有两个启发式）在十五人游戏中的笔画数。
我的问题是计数器对BFS和A*的三个计数器数组计数相同的结果。然而，我实际上使用了主（class 项目）中的三个不同数组，并且为这些笔画分配了三个不同的变量。
我认为问题来自A*。对于他们每个人，我从父亲开始，然后计算其启发式并将他添加到边界。
虽然边界不是空的，但我看看初始状态是否是十五人游戏的最终状态，否则我将其从边界中移除，然后我们搜索他的儿子。我为他们所有人设置他们的 g 值，我计算他们的每个启发式以最终得到他们的 f 值。如果他们还没有在边境，我就把他们加进去。然后我将边界中第一个的 F 值与边界内的每个值进行比较，并将具有最佳 F 值的一个实例化为 current_state.
int best_f_value=frontier.get(0).getFValue();
for(State s : frontier){
if(s.getFValue()<=best_f_value){
best_f_value=s.getFValue();
current_state=s;
}
}
然而，在寻找计数器时，我总是对 BFS 和 A* 具有相同的笔划数，其中启发式的错位图块数和 A* 具有曼哈顿距离的启发式。这可能会出现一次，但不会总是出现！！
我认为问题在于 A* 的函数，而不是用于计算其启发式的函数。因此这里是第二个 A* 的代码，他看起来很像第一个只是错位的 tiles heurisitc。
第二个A*码
public State aStar2(){
State child;
System.out.println("we entered A_star with Manhattan distance");
System.out.println("final:\n"+finalState);
/** current state of dfs algorithm **/
State current_state;
current_state = initialState;
current_state.computeHeuristic2();
current_state.computeValueF2();
//int best_f_value= current_state.getFValue();
int current_state_g_value = 0;
System.out.println(initialState);
// get alwhile(!frontier.isEmpty()){l possible actions from the given node
List<Action> actions = current_state.getActions();
//frontier is a Stack displaying not currently explored nodes
LinkedList<State> frontier = new LinkedList<State>();
// frontier already contains the first node
frontier.push(initialState);
// explored_nodes contains all explored nodes.
LinkedList<State> explored_nodes = new LinkedList<State>();
// this List is used to show the path
LinkedList<State> path = new LinkedList<State>();
while(!frontier.isEmpty()){
number_of_strokes_A2+=1;
// we found the goal
if(goal_test(current_state)){
for(State visited :path){
System.out.println(visited);
}
array_number_of_strokes_A2.add(number_of_strokes_A2);
System.out.println("nombre de coups A2 : " + number_of_strokes_A2);
number_of_strokes_A2=0;
System.out.println("on a réussi : \n" + current_state);
return current_state;
}
// We remove the current state from the frontier
// VERIFY THIS IS OKAY !!!
frontier.remove(current_state);
// 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);
current_state_g_value = current_state.getValueG();
// We create every child
for (Action action : actions){
// we get a child from the execution of the current_state
child = current_state.execute(action);
child.setValueG(current_state_g_value);
child.computeHeuristic2();
child.computeValueF2();
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.add(0,child);
}
}
int best_f_value=frontier.get(0).getFValue();
for(State s : frontier){
if(s.getFValue()<=best_f_value){
best_f_value=s.getFValue();
current_state=s;
}
}
}
return finalState;
}
问我是否需要第一个A*来比较。 下面是启发式方法。
启发式
它们在另一个文件中。我不认为他们有任何罪过。
public void computeValueF(){
// to be completed
f_value = getValueG() + getHeuristic();
}
public void computeValueF2(){
// to be completed
f_value = getValueG() + getHeuristic2();
}
public int getFValue(){
return f_value;
}
@Override
public int getFValue2(){
return f_value;
}
public int getHeuristic(){
return h_value;
}
public int getHeuristic2(){
//somme de la distance de Manhattan entre lemplacement couvrant de chaque case � sa position finale
int h2=0;
for(int i=0;i<9;i++){
h2+=Integer.valueOf(puzzle.charAt(i))%3-i%3+Integer.valueOf(puzzle.charAt(i))/3-i/3;
}
return h2;
// to be completed
}
@Override
public int compareTo(Searchable<Puzzle, PuzzleAction> o) {
// TODO Auto-generated method stub
if(this.getHeuristic()> o.getHeuristic());
return 0;
}
@Override
public void setValueG(int cost) {
// TODO Auto-generated method stub
g_value = cost+1;
}
@Override
public int getValueG() {
// TODO Auto-generated method stub
return g_value;
}
@Override
public void computeHeuristic() {
// TODO Auto-generated method stub
//nombre de cases mal placees
for(int i=0;i<9;i++){
if((Integer.valueOf(puzzle.charAt(i))-i)!=0){
h_value+=1;
}
}
}
@Override
public void computeHeuristic2() {
// TODO Auto-generated method stub
int h2=0;
for(int i=0;i<9;i++){
h2+=Integer.valueOf(Math.abs(puzzle.charAt(i))%3-i%3)+Math.abs(Integer.valueOf(puzzle.charAt(i))/3-i/3);
}
this.h2_value=h2;
}
结果
以下是笔划数的结果：
strokes BFS : [9, 7, 33, 33, 53, 53, 51]
strokes AStar1[9, 7, 33, 33, 53, 53, 51]
strokes AStar2[9, 7, 33, 33, 53, 53, 51]
参考资料
这个问题与
更新：尝试从实际当前位置到目标进行启发
Ishmael 关于我保持不变的启发式方法是正确的。因此，我试图修改启发式计算方法，以便参考当前状态而不是永远不会改变的东西。这是Puzzle.java
中的方法@Override
public void computeHeuristic1(String s) {
// TODO Auto-generated method stub
//nombre de cases mal placees
h1_value=0;
for(int i=0;i<9;i++){
if((Integer.valueOf(s.charAt(i))-i)!=0){
h1_value+=1;
}
}
}
我们将在 Problem.java
中使用child.computeHeuristic1(child.toString());
如果需要，我可以添加更多代码。
我得到了那些启发式方法：
array_heuritics_1 : [9, 9, 9, 9, 9, 9, 9, 9
array_heuritics_2 : [130, 131, 131, 129, 129, 128, 1
最后一个是异常的，因为每个瓷砖最多可以带来 3+3 的启发值。因此，启发式 > 51 的东西是站不住脚的。
所以我试图展示测试在做什么，我发现了一些有趣的东西：
the child.toString :
1 2 5
3 4 .
6 7 8
the value :
i : 0 & s.charAt(i) : 1
i : 1 & s.charAt(i) : .
i : 2 & s.charAt(i) : 2
i : 3 & s.charAt(i) :
i : 4 & s.charAt(i) :
i : 5 & s.charAt(i) :
i : 6 & s.charAt(i) :
i : 7 & s.charAt(i) : 6
i : 8 & s.charAt(i) : 7
i : 0 & s.charAt(i) : 1
i : 1 & s.charAt(i) : .
i : 2 & s.charAt(i) : 2
i : 3 & s.charAt(i) :
i : 4 & s.charAt(i) :
i : 5 & s.charAt(i) :
i : 6 & s.charAt(i) :
i : 7 & s.charAt(i) : 6
i : 8 & s.charAt(i) : 7
实际上我们不是逐个数字进行测试，而是逐个字符进行测试，并且有一些空白 space!
首先，让我们考虑一下如果您的 A* 不使用任何启发式算法会发生什么（如果 getFValue 只是 returned getValueG）。请注意，当算法开始时，它在 frontier 中只有一个节点，因此它会被选中。在每次连续迭代中，边界中的值将按 cost 降序排序（如果你在纸上画几个例子，你可以通过归纳法证明），边界中第一个元素的成本将是要么等于最后一个的成本，要么更大。现在，当您 运行 选择 state 的循环时，您将始终选择最后一个元素，因为它将具有最小的 FValue，并且在这些元素中您总是选择最后一个.换句话说，如果没有启发式方法，您的 A* 将表现得与您的 BFS 完全一样（它已经选择了最后一个元素）。
现在假设您的启发式只是一个常量，例如您的 getFValue 被实现为 return getValueG + constant。您可以通过遵循与上述非常相似的逻辑再次证明它的行为就像只是 BFS 一样——如果您向比较的值添加一个常量，它们将以相同的方式进行比较。
最后，很容易证明你的启发式总是return相同的值。请注意，它们仅依赖于常量 puzzle。它们绝不取决于代理的当前位置。曼哈顿距离启发式应该是从 当前位置 到地图上所有目标位置的曼哈顿距离相加（或者更确切地说，只是到最近的一个，因为启发式会更有意义）。相反，它计算的东西根本不依赖于当前位置，这是错误的。由于它 returns 的值始终相同，因此由于我在上面提供的原因，它的行为类似于 BFS。