[内容有误] A * 页面例题 「八数码」参考代码有误

[PlanariaIce]

请选择：

• 我正在着手修复这个问题

我正在访问这个页面

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

我发现页面有这样的问题

我认为参考代码中有两处错误。

第一，函数 $h$ 设计错误。原文为「 $h$ 函数可以定义为，不在应该在的位置的数字个数。」，但这显然不满足上文 $h\leq h*$ 的要求。比如说，当「不在应该在的位置的数字个数」为 2 时，可能仅需 1 步操作即可达到目标状态。

第二，未将初始状态放入集合 s 中（代码第 55 行）。这将导致初始状态会在之后的搜索中被认为是新出现的状态，可能使结果偏大。

容易解决第二个问题。但对于第一个问题，我认为需要重新设计 $h$ 函数。将 $h$ 函数定义为「不在应该在的位置的棋子个数」，这相当于忽略了空格。注意到每个棋子只能和空格交换位置，最好的情况就是这些「不在应该在的位置的棋子」与空格一一交换后达到目标状态。可以将原代码中的函数 h 改为如下形式:

int h(matrix a) {
  int ret = 0;
  for (int i = 1; i <= 3; i++)
    for (int j = 1; j <= 3; j++)
      if (a.a[i][j] != st.a[i][j]
          && a.a[i][j] != 0) ret++; // here
  return ret;
}

至于原代码在洛谷中为什么能通过，大概是以上两个错误，加之数据较水共同作用的结果。事实上，可以构造 Hack 数据：

输入：763508241
输出：24
错误答案：26

输入：521748360
输出：26
错误答案：28