【题解】 P1379 八数码难题

2018-06-06 21:09:41


使用 $IDA*$

说说 $IDA*$ 吧。 其实这种算法就是 $A*$ 的 $Dfs$ 版。

我们先枚举最大深度(也就是最多能走的步数),然后依次 $Dfs$ 即可。

在 $Dfs$ 时,需要设计一个估价函数 $h()$ 。它的设计过程如下:

  • 首先,用 $dis[i][j]$ 表示从第i个到第j格的最少移动次数。这个就是曼哈顿距离。
  • 其次,用 $p[i]$ 表示i这个数的目前位置, $q[i]$ 表示第j个数的目前位置。
  • 最后, $h()$ 即为当前局面的偏移量之和。

最后回答一下判重的问题。

由于改成了深度优先的方式,与 $A*$ 比起来, $IDA*$ 更实用:1.不需要判重,不需要排序;2.空间需求减少。 ——百度百科

所以判重是完全不必要的。 这样顺便解决了本题最麻烦的问题。

如果还有什么问题评论或者发洛谷私信吧。

代码见蒟蒻的blog