我正在尝试建立一个程序，比较算法bfs和两个不同的a*（有两个启发式）在一个15的游戏中的笔划数。
我的问题是计数器计数BFS和A*的三个计数器数组的结果相同然而，我实际上使用了一个main（类项目）中的三个不同数组，并为这些笔划分配了三个不同的变量。
我认为问题来自于一个*对于他们中的每一个，我先从父亲开始，然后计算其启发性，并将他添加到边界。
虽然边界不是空的，但我看看初始状态是否是15的游戏的最终状态，否则我将其从边界移除，然后我们寻找他的儿子。我为他们所有人设置了g值，我计算了他们的启发式算法，最后得到了他们的f值如果他们还不在边境，我就把他们加进去。然后比较边界上的第一个F值和边界内的每个F值，并将具有最佳F值的F值实例化为当前状态。
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*表示Manhatan距离这可能出现一次，但并不总是！啊！
我认为问题在于a*的函数，而不是用来计算其启发式的函数。前面是第二个A*的代码，他看起来像第一个用错了位置的瓷砖启发的代码。
第二个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]
工具书类
这个问题与this one answered by Ishamael类似，但在实现bfs和dfs方面有所不同
更新：尝试从实际的当前位置到目标获取启发
以实玛利对我的启发是正确的因此，我试图修改启发式计算方法，以参考当前状态，而不是永远不会改变的东西。下面是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
实际上，我们不是按数字来做测试，而是按字符来做，还有一些空格！
最佳答案
首先，让我们考虑一下如果您的a*没有使用任何启发式（因为，如果getFValue刚刚返回getValueG，会发生什么）。注意，当算法启动时，它在frontier中只有一个节点，因此将选择它在每一个连续的迭代中，边界中的值将按cost的降序排序（如果你在纸上画了几个例子，你可以用归纳法证明它），并且边界中第一个元素的成本将等于最后一个元素的成本或更大的一个元素的成本现在，当您运行选择state的循环时，您将始终选择最后一个元素，因为它将具有最小的FValue，并且在这些元素中，您总是选择最后一个元素。换言之，如果启发式没有到位，那么您的A*行为将与您的BFS完全相同（BFS已经选择了最后一个元素）。
现在假设你的启发式只是一个常数，例如你的getFValue被实现为return getValueG + constant。您可以再次表明，它的行为就像是bfs一样，遵循与上面非常相似的逻辑——如果您将常量添加到您比较的值中，它们将以相同的方式进行比较。
最后，很容易证明两个启发式方法总是返回相同的值。注意，它们只依赖于常数puzzle。他们决不取决于特工的当前位置曼哈顿距离启发法应该把曼哈顿距离从当前位置加起来到地图上的所有目标位置（或者更确切地说，仅仅是最接近的位置作为启发法更有意义）相反，它计算的东西根本不依赖于当前的位置，这是错误的由于它返回的值总是相同的，所以它的行为类似于BFS，这是由于我在上面提供的原因。