APIO'09 归来

嗯，200分压线金牌。第二题输出没排序，就把本来的28分骗分送人了。不过貌似所有200分的第二题都是0，所以也没什么遗憾了。

zouxun考的很囧，第一题用了一种比我麻烦的代码搞了200多行结果WA不少，只得了65分，最后获得银牌，不免有些郁闷。

不过最终大家玩得还是很开心的。

这几天还是抽空写写总结。先把那个 A* 的小结写完，再把答应的某模拟赛题目出出来，最后再写个 APIO'09 总结。嗯，过两天回家再把 APIO'09 的题目加到 RQNOJ 上吧，第二题还是很不错的。第一题和第三题对基本功的考察也还是很不错的。

就写这么多。

A*算法浅谈(60% finished)

嗯，答应的事情的确有太多没有做好，现在就一点一点去补偿吧。

A*可以看成BFS的加强版，或者说BFS就是A*的特殊情况。这里我们在BFS的基础上来逐步介绍A*。我们只考虑路经寻找问题，即寻找从初始状态到目标状态的一条最短路径。我们定义 D[u] 为初始状态到状态 u 的最短路径长度，w[u, v] 为状态 u 到状态 v 的路径长度。

首先我们回顾BFS的过程，我们需要一个队列 queue 保存待扩展节点，一个 hash 表保存待扩展和已经扩展的节点，BFS 过程可以表示如下：

1. 将初始状态加入 queue 和 hash 中
2. while (queue 非空)
3.　　 取出 queue 尾状态 u
4.　　 若 u 是目标状态，则 D[u] 为答案，结束算法
5.　　 枚举每个从状态 u 出发可以到达的状态 v
6.　　　　 若从 D[u] + w[u, v] < D[v] 则
7.　　　　　　更新 D[v] = D[u] + w[u, v]
8.　　　　　　　 若 v 不再 hash 中
9.　　　　　　　　　 v 入队并加入 hash
10.　　不存在所需的路径

不难发现，这个过程与 SPFA 很像。

但是这个算法的效率是很低的，特别对于很多状态空间是无限的问题，BFS可能会迟迟找不到解。究其原因，我们发现，BFS过程完全是按照入队列的顺序扩展状态的，也就是说，如果把状态空间看作一个层次图，BFS 每次只遍历这个层次图的一层，然而每个层次中的大部分状态都是没有用的，可不可以不要去碰这些状态呢？另一方面，对于一些特定的问题，从某个状态出发，往往很容易看出一些后继状态是明显没有“前途”的，那么能不能尽量把这些状态延迟取出，以便加速求解（目标状态可能在这些状态开始扩展之前就到达了，这样就省去了扩展这些节点的操作）？

综合以上两种思路，我们考虑为每个状态 u 设计一个函数 h[u]（通常叫做这个算法的启发函数），表示我们估计从 u 状态到目标状态的最短路径还有多长，设 h*[u] 表示 u 到目标状态的实际最短路径常数。如果我们能直接计算出任意的 h[u]=h*[u]，那么 h[初始状态]=h*[初始状态] 就是答案。但这在大部分的问题中都很难做到。于是我们考虑改进 BFS，每次扩展 h 值最小的状态。但是思考之后可以发现这显然是错的，因为大体上来说一个对于任意一个状态 u 的后继状态 v，一般有 h[u] > h[v]，这样算法就很可能朝着一条路径一直搜索下去，即使找到了目标状态也还是不能保证解的最优性。所以我们考虑“经过状态 u 的最短路径的估计函数”f[u]（同上设最短路径长度的实际值为 f*[u]）。设 g[u]=g*[u] 表示从初始状态到状态 u 的最短路径长度，这可以准确得出，则有：f[u] = g[u] + h[u]。于是算法改为：每次扩展 f 值最小的状态。

但是我们又发现，这样仍然不能保证获得最优解，由于对 h* 估计的不确定性，仍然不能保证第一次找到目标状态时的路径就是最短路径（因为最短路径上的某个状态 u 可能由于错误估计的较大 f[u](h[u]) 值而迟迟得不到扩展），于是我们需要对 h 函数加一些限制，使它能更客观真实地反映一个状态的优劣程度。我们要求对任意状态 u，h[u] 必须满足 h[u] <= h*[u]，即 h[u] 是最短路径的下界。

乍一看找不到反例了，但是这种算法的确能保证第一次遇到的解是最优解吗？答案是肯定的，这种算法正是大名鼎鼎的 A* 算法。首先我们将整个算法流程重新描述如下：

算法正确性的证明分为两步（我的数学很烂，不很会严格证明，大家如果想看严格证明可以自己尝试或者参考《人工智能导论》中的相关章节）：

定理 1. 如果存在一条从初始状态到目标状态的路径，A* 算法一定可以找到这条路径。

说明：容易看出，A* 算法退化到极致之后就是朴素的 BFS，所以只要 BFS 可以找到解，A* 就一定可以找到解（当然，这种证明对于状态空间是无限的问题来说还是有些牵强，不过勉强还能说得过去吧）。

定理 2. 设最优解为 F*。A* 算法未完成时，队列 queue 中一定存在 F[u] <= F* 的状态 u。

说明：在一条最短路径（s、v₁、v₂、……、v_k、t）上的状态 u 显然满足：

f[u] = g[u] + h[u] <= g*[u] + h*[u] = f*[u] = F*

即 u 的估计价值 f[u] 不超过 F*。所以若 A* 算法未完成，则最短路径上的状态就没有全部被扩展，所以一定在这样的状态 u。

定理 3. A* 算法找到的解一定是最优解。

说明：首先根据定理 1，A* 算法一定可以找到解。又根据定理 2，只要 A* 算法未完成，总有 f[u] <= F* 的状态 u，所以 A* 算法每次扩展的状态 u 总有 f[u] <= F*，因而扩展到目标状态时，仍然有 f[t] <= F*，而 F* 为最优解，既有 f[t] = F*，定理得证。

8数码 A*

终于初步学会了A*，也把这个一直留着的8数码AC掉了。
A*的速度的确很快很强大。。。写得这么丑的代码都那么快。。。

PS：我用的启发函数是每个数字当前位置到目标位置的曼哈顿距离之和。

过两天有空写个 A* 的详细解释，也算对这几天研究的一个总结。

program number8;
const
　maxState = 100000;
　Mask: array [0..9] of Longint = (1000000000, 100000000, 10000000, 1000000, 100000, 10000, 1000, 100, 10, 1);
　Ori: array [1..8, 1..2] of Longint = ((1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (2, 1));

type
　TOpenState = record
　　P, F, G: Longint
　end;
　
　TClosedState = record
　　State, P: Longint
　end;

var
　State: array [1..3, 1..3] of Longint;
　i, j: Longint;
　a, b: Longint;
　OpenCount, CloseCount: Longint;
　Open: array [1..maxState] of TOpenState;
　Closed: array [1..maxState] of TClosedState;
　Current, CurrentG: Longint;
　
procedure Swap(a, b: Longint);
var
　T: TOpenState;
　
begin
　T := Open[a];
　Open[a] := Open[b];
　Open[b] := T;
　Closed[Open[a].P].P := a;
　Closed[Open[b].P].P := b
end;

procedure Decrease_Key(t, dstF, dstG: Longint);
var
　u: Longint;
　
begin
　u := t;
　Open[u].F := dstF;
　Open[u].G := dstG;
　while (u > 1) and (Open[u div 2].F > Open[u].F) do
　　begin
　　　Swap(u, u div 2);
　　　u := u div 2
　　end
end;

function Extract_Min: Longint;
var
　u: Longint;
　
begin
　Closed[Open[1].P].P := 0;
　Current := Closed[Open[1].P].State;
　Extract_Min := Open[1].G;
　Open[1] := Open[OpenCount];
　dec(OpenCount);
　u := 1;
　while True do
　　if (u * 2 <= OpenCount) and (Open[u * 2].F < Open[u].F) then
　　　begin
　　　　Swap(u, u * 2);
　　　　u := u * 2
　　　end
　　else if (u * 2 + 1 <= OpenCount) and (Open[u * 2 + 1].F < Open[u].F) then
　　　begin
　　　　Swap(u, u * 2 + 1);
　　　　u := u * 2 + 1
　　　end
　　else
　　　break
end;

function CalculateH: Longint;
var
　i, j: Longint;
　
begin
　CalculateH := 0;
　for i := 1 to 3 do
　　for j := 1 to 3 do
　　　if State[i, j] <> 0 then
　　　　inc(CalculateH, abs(i - Ori[State[i, j], 1]) + abs(j - Ori[State[i, j], 2]))
end;

procedure Expand(a, b, da, db: Longint);
var
　i, j: Longint;
　NowF, NowState: Longint;
　Flag: Boolean;
　
begin
　State[a, b] := State[da, db];
　State[da, db] := 0;
　Flag := False;
　NowState := 0;
　for i := 1 to 3 do
　　for j := 1 to 3 do
　　　inc(NowState, State[i, j] * Mask[(i - 1) * 3 + j]);
　NowF := CurrentG + 1 + CalculateH;
　for i := 1 to CloseCount do
　　if Closed[i].State = NowState then
　　　begin
　　　　Flag := True;
　　　　if (Closed[i].P <> 0) and (NowF <= Open[Closed[i].P].F) then
　　　　　Decrease_Key(Closed[i].P, NowF, CurrentG + 1)
　　　end;
　if not Flag then
　　begin
　　　inc(CloseCount);
　　　inc(OpenCount);
　　　Closed[CloseCount].State := NowState;
　　　Closed[CloseCount].P := OpenCount;
　　　Open[OpenCount].P := CloseCount;
　　　Open[OpenCount].F := MaxLongint;
　　　Decrease_Key(OpenCount, NowF, CurrentG + 1)
　　end;
　State[da, db] := State[a, b];
　State[a, b] := 0
end;

begin
　fillchar(Open, sizeof(Open), 0);
　fillchar(Closed, sizeof(Closed), 0);
　OpenCount := 1;
　CloseCount := 1;
　readln(Closed[1].State);
　Closed[1].P := 1;
　Open[1].G := 0;
　Open[1].P := 1;
　while OpenCount > 0 do
　　begin
　　　CurrentG := Extract_Min;
　　　if Current = 123804765 then
　　　　begin
　　　　　writeln(CurrentG);
　　　　　halt
　　　　end;
　　　for i := 1 to 3 do
　　　　for j := 1 to 3 do
　　　　　begin
　　　　　　State[i, j] := Current mod Mask[(i - 1) * 3 + j - 1] div Mask[(i - 1) * 3 + j];
　　　　　　if State[i, j] = 0 then
　　　　　　　begin
　　　　　　　　a := i;
　　　　　　　　b := j
　　　　　　　end
　　　　　end;
　　　if a > 1 then
　　　　Expand(a, b, a - 1, b);
　　　if a < 3 then
　　　　Expand(a, b, a + 1, b);
　　　if b > 1 then
　　　　Expand(a, b, a, b - 1);
　　　if b < 3 then
　　　　Expand(a, b, a, b + 1)
　　end
end.

省选归来,一切正常,期待APIO'09

省选归来已经是一个星期之前的事情了，考的分数还是很让人郁闷的：不过半的280分。有的时候别人问我靠怎么样，我还可以炫耀一下：与第一名只差20分。殊不知，我与第三名只差10分。- -||

今年是我OI生涯最后一年了（如果拿不到金牌的话……）。所谓成也OI，败也OI。期望越大，失望越大。不过正常发挥就可以了吧。

这两天貌似很多事情都变了很多。QQ 好友数目呈指数爆炸式增长，五一的 RQNOJ 群变得异常火热。终于认识了传说中带狗牛，看到了 RQ 照片，大家还在 IPSC'09 组了队 ~^_^~（话说register添年龄的时候发现我们三的年龄恰成等差数列）。这样给了今年的 APIO 不少期待。虽然估计这次要考差，但见识到这么多传说中的牛人，也不虚此行吧。

怎么说着说着废话又连篇了。- -|| 就到这里吧，期待 APIO'09，大家共同加油！