A*

[Ir1d]

https://oi-wiki.org/search/astar/

[hjsjhn]

似乎八数码问题的代码交上去只能得90分了，会T在第31个点，不知道是不是改了数据。

[githubxiaogege]

并不会啊

[Ir1d]

@SysConKonn 尬…… 这里的代码似乎并不是 a* 谢谢提醒……

[hjsjhn]

@Ir1d
@SysConKonn 尬…… 这里的代码似乎并不是 a* 谢谢提醒……

剪枝可以过。
感觉代码是IDA* ?

[Ir1d]

@SysConKonn 也不是 IDA*，现在这个感觉仅用 h 函数来剪枝

[floatyun]

额，弱弱问一下，三角形不等式具体是指啥？是指下面这个吗？
a有一条到b的边，权值是w，然后需要满足不等式 h(a) <= h(b)+w吗？
$$h(a) \leq h(b)+w$$
还是指什么？

[hsfzLZH1]

@floatyun
额，弱弱问一下，三角形不等式具体是指啥？是指下面这个吗？
a有一条到b的边，权值是w，然后需要满足不等式 h(a) <= h(b)+w吗？
$$h(a) \leq h(b)+w$$
还是指什么？

@floatyun
额，弱弱问一下，三角形不等式具体是指啥？是指下面这个吗？
a有一条到b的边，权值是w，然后需要满足不等式 h(a) <= h(b)+w吗？
$$h(a) \leq h(b)+w$$
还是指什么？

就是松弛操作要满足的条件啊

[c2peng]

k短路好像也过不了了

[lucheng2]

h(x)是我们定义的点x到终点的预估代价函数，h*(x)是点x到终点的实际代价函数。

[Kzused]

想问一下八数码问题中为什么不能直接把输入点放入set集合中啊？

[cwf12138]

那里的h=0时，A*算法变为DFS是不是有点问题？不应该是Dijkstra吗？

[http600]

what is 最佳优先搜索？

[xiaonuo911teamo]

@Kzused
想问一下八数码问题中为什么不能直接把输入点放入set集合中啊？

应该是要放进去的，上面的代码遗漏了。

[ws-zzy]

放进去知会导致无法通过洛谷评测，评估函数本来就是一个预估值，很可能提前加入set导致找不到最优解

[xiaohaowudi]

当h=0 时，A*算法变为 DFS 似乎该说法不太准确，应该是变为朴素的迪杰特斯拉，因为估值还是存在的，只不过是某状态以当前的开销作为估值函数的数值，这个思路其实是迪杰特斯拉的贪心思路，并非DFS

[xiaohaowudi]

@cwf12138
那里的h=0时，A*算法变为DFS是不是有点问题？不应该是Dijkstra吗？

我也觉得应该是迪杰特斯拉，估计是写错了，应该是f=0时候，A*变为DFS

[Lotuses-robot]

@xiaohaowudi

@cwf12138
那里的h=0时，A*算法变为DFS是不是有点问题？不应该是Dijkstra吗？

我也觉得应该是迪杰特斯拉，估计是写错了，应该是f=0时候，A*变为DFS

嗯
https://zhuanlan.zhihu.com/p/54510444

[purple-vine]

建议把k短路的链接换成 https://www.luogu.com.cn/problem/P2901, 只找到一个不卡 A* 的k短路

[sky-bro]

这里h <= h似乎不成立，因为把0的位置不同算进去了，这样可能h为1，但是h为2

[Kirigiri123]

$h$ 函数可以定义为，不在应该在的位置的数字个数。

请问“不在应该在的位置的数字个数”是什么意思?

[iliyian]

即当前状态离目标的距离吧

[zhangjialin996]

关于八数码问题的疑问：
这道题直接暴力也能AC，问一个问题：这里说了A确保最优解需要保证h>=h，这里明显不对啊 比如初始是123804765，目标是123864705，2个位置不一样，但是真实开销只需要1，那么如何保证最优解的？

java AC代码：

import java.util.*;

public class P1379 {
    static String target = "123804765";
    static String src;
    static char[][] map = new char[3][3];
    static HashMap<String, Integer> resList = new HashMap<>();
    static Queue<String> queue = new LinkedList<>();
    public static void main(String... args){
      Scanner in = new Scanner(System.in);
      src = in.next();
      queue.offer(src);
      resList.put(src, 0);
      boolean flag = true;
      while(!queue.isEmpty()){
        // if( queue.isEmpty() || resList.containsKey(target)) return ;
        flag = false;
        String srcM = queue.poll();
        int times = resList.get(srcM);
        int[] zeroPos;
        getMap(srcM);
        zeroPos = getZeroPos();
        // 上
        if(zeroPos[0] - 1 >= 0) {
          switchNode(zeroPos[0], zeroPos[1], zeroPos[0] - 1, zeroPos[1]);
          String str = getMapString();
          if(!resList.containsKey(str)) {
            flag = true;
            queue.offer(str);
            resList.put(str, times + 1);
          }
        }
        // 下
        getMap(srcM);
        if(zeroPos[0] + 1 < 3) {
          switchNode(zeroPos[0], zeroPos[1], zeroPos[0] + 1, zeroPos[1]);
          String str = getMapString();
          if(!resList.containsKey(str)) {
            flag = true;
            queue.offer(str);
            resList.put(str, times + 1);
          }
        }
  
        // 左
        getMap(srcM);
        if(zeroPos[1] - 1 >= 0) {
          switchNode(zeroPos[0], zeroPos[1], zeroPos[0], zeroPos[1] - 1);
          String str = getMapString();
          if(!resList.containsKey(str)) {
            flag = true;
            queue.offer(str);
            resList.put(str, times + 1);
          }
        }
  
        // 右
        getMap(srcM);
        if(zeroPos[1] + 1 < 3) {
          switchNode(zeroPos[0], zeroPos[1], zeroPos[0], zeroPos[1] + 1);
          String str = getMapString();
          if(!resList.containsKey(str)) {
            flag = true;
            queue.offer(str);
            resList.put(str, times + 1);
          }
        }
      }
      // System.out.println(resList.size());
      System.out.println(resList.get(target));
      in.close();
    }
    public static void getMap(String str){
      for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++){
          map[i][j] = str.charAt(i * 3 + j);
        }
    }

    public static int[] getZeroPos(){
      int[] res = new int[2];
      for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
          if(map[i][j] == '0') {
            res[0] = i;
            res[1] = j;
          }
        }
      }
        
      return res;
    }

    public static void switchNode(int x1, int y1, int x2, int y2){
      char temp = map[x1][y1];
      map[x1][y1] = map[x2][y2];
      map[x2][y2] = temp;
    }

    public static String getMapString(){
      StringBuilder builder = new StringBuilder();
      for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++){
          builder.append(map[i][j]);
        }
      return builder.toString();
    }
}

[zhangjialin996]

需要确保h* >= h

[ksshen0000]

所有的搜索就是不断地把新的节点填入队列，各个算法不同取决于填入方式，dfs是先进后出，bfs是先进先出。
直觉上来说，A算法就是对节点队列进行排序，其中排序的键值为已经走过的路和未来的估计，而dijkstra算法和A唯一的区别在于dijkstra不看未来的估计，只针对已经走过的路径排序，所以可以认为是h函数为0。

[qwqAutomaton]

如果我没记错的话 $h>h^$ 的情况并不叫 A...? 好像就叫 A 来着