题目描述
给出一个排列，要将其排序。 排序方法为选取连续若干元素，按原顺序插入某一位置 例如 $1\ 2\ 6\ 3\ 4\ 5$，选取 $3\ 4\ 5$，插入 $2$ 后面，得到 $1\ 2\ 3\ 4\ 5\ 6$ 求最少几次操作将序列变为升序，如果 $5$ 次操作内无法让序列变为升序，输出 "Error"
$n \leq 15$
题解
启发式搜索，特征明显。
其实这题的数据可以加强到 $n \leq 30$，使用双向 A* 即可。
但是这题范围较小，单向 IDA* 足以。
考虑估价函数：
此题的估价函数直接想比较难想，不妨考虑间接地，设 $\varphi(x)$ 为当前状态的 混乱程度，然后我们记 $y$ 为：每次操作最多减少的 混乱程度，然后，估价函数 $h(x) = \lceil \frac{\varphi(x)}{y} \rceil$
那么，如何设 $\varphi(x)$ 呢？
观察一下这个数列
$1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9$
$1\ 6\ 7\ 2\ 3\ 4\ 5\ 8\ 9$
有哪里发生了改变？
如果考虑 $1$ 到 $9$ 的位置的话，估价会非常劣。所以考虑每个数 前面的数。记数列 $y$ 为 当前状态 每个数前面的数，记数列 $z$ 为 目标状态 每个数前面的数，则
$\varphi(x) = \sum\limits_{i = 1}^n[\;x_i \neq y_i\;]$
然后考虑 $h(x)$：
因为每次操作最多改变 $3$ 个位置的 前面的数，所以
$h(x) = \lceil\frac{\varphi(x)}3\rceil$