写给妹妹的编程札记 6 - 搜索实战: 单词博弈

        最近，CSDN上的在线编程比赛中，有一道题目《单词博弈》。这道题目是一个很好的可以使用搜索来解决的例子。

题目详情
本第一次在线编程大赛由文思海辉冠名，题目如下：
甲乙两个人用一个英语单词玩游戏。两个人轮流进行，每个人每次从中删掉任意一个字母，如果剩余的字母序列是严格单调递增的（按字典序a < b < c <....<z)，则这个人胜利。两个人都足够聪明（即如果有赢的方案，都不会选输的方案 ），甲先开始，问他能赢么？
输入： 一连串英文小写字母，长度不超过15,保证最开始的状态不是一个严格单增的序列。
输出：1表示甲可以赢，0表示甲不能赢。
例如: 输入 bad， 则甲可以删掉b或者a,剩余的是ad或者bd，他就赢了，输出1。
又如: 输入 aaa， 则甲只能删掉1个a，乙删掉一个a,剩余1个a，乙获胜，输出0。

        有别于以往的搜索问题，在这个问题中，有两个角色，为游戏双方 - 甲和乙。 但，需要说明的是， 这个题目比平常的围棋象棋简单很多，一个是问题的搜索空间很小， 另一个是任意一个状态对甲乙来说是一样的。比如，甲乙面对字符串bad的输赢情况是一样的。 不难看出，对于一个状态，要么先玩的选手赢，要么先玩的选手输，只有这两种可能。题目已经假设最开始的状态不是一个严格单增的序列，并且如果一个选手通过删除掉一个字母到达一个单增序列的话就可以胜利。那么，我们有下面的发现：

        1. 如果一个字母序列X是单增的， 那么，对于这个序列来说， 先行者输

        2. 否则，一个长度为k的字母序列X, 删除一个字母后， 可以得到k个字母序列(删除其中的第1,2,...,k个字母分别得到字母序列Y_1, Y_2, ..., Y_k )

            a. 如果这k个字母序列中任意一个是先行者输， 那么X是先行者赢

                为什么？ 假设Y_i是先行者输，那么对于字母序列X来说， 作为先行者，我们只要删除字母i，到达Y_i， 下一个选手就输了。

            b. 如果这k个字母序列中任意一个都不是先行者输， 也就是说所有k个字母序列都是先行者赢， 那么X是先行者输

                为什么？ 因为对于X这个字母序列来说， 不管我们删除哪个字母，到达的k个字母序列都是先行者赢。 也就是下一个选手会赢。

        有了上面的这些观察， 让我们来看看整棵博弈搜索树是怎样的？ 拿“bdca”为例吧 (图中W表示先行者赢， L表示先行者输)

        对于字母序列"bdca"，首先搜索第一个分支"_dca"，当搜索完分支"_dca"之后，发现"_dca"是一个先行者输的状态，也就是说我们如果删除字母b，到达字母序列"_dca"的话，下一个选手不管怎么走都是输，也就是说"bdca"是先行者赢的，我们的取胜策略是删除第一个字母。 后面的三个分支没有必要计算了。

        到这里为止，应该不难写出一个搜索程序来了。需要注意的地方是， 像往常一样， 搜索树上有很多节点是重复的，比如上面"___a", "__c_"等。 搜索时候如何避免这些重复状态将直接影响整个程序的效率。

        考虑下，搜索树中可能的字母序列数目是多少呢？ 如果输入字母序列长度为k， 那么可能的字母序列为2^k  (序列中每个字母都可能被删除了或者还没有被删除)。 题目中限制输入的字母序列长度不超过15，所以搜索树中可能的字母序列不超过2^15， 是一个很小的数目。比如，"bdca"可以用15表示 (2^4 - 1), 4个bit， 每个bit都是1. “_dca”可以用14表示，除了第一个bit其他bit都是1. 我们可以申请一个空间v[], v[i]记录i对应的字母序列是先行者赢还是先行者输。 搜索的伪代码如下:

char search(int state)
{// 检查state是否已经计算过，避免重复计算if (v[state] != '') {return v[state];}// 检查state是否是单增序列， 如果是单增序列，返回"L"if (单增序列) {return 'L';}// 尝试删除每一个字母，看是否能找到先行者输的字母序列for (int i = 0; i < k; i++) {next_state = 删除字母i之后得到的新的字母序列if (search(next_state) == 'L') return 'W';}return 'L';
}

        由于搜索的整个空间很少， 下面是一个遍历所有可能字母序列的程序， 没有按上面伪代码这样编写常规的递归搜索程序。 一个不足的地方在于，可能计算了一些字母序列，但这些字母序列根本没有必要计算。 比如上图中，经过剪枝， 需要计算的字母序列数目非常少。好处当然是图方便编写简单。 至于，为什么从小到大开始计算呢？ 因为每一个字母序列x，删除其中任意一个字母后得到新的字母序列y， 那么x对应的整数一定比y对应的整数大。 从小到大遍历一遍所有可能的字母序列可以保证在计算x对应的字母序列时，该字母序列通过删除字母得到的字母序列肯定都已经计算过了。

int who(const char* word)
{int   n = strlen(word);int   nState = (1<<n);int   k, nextK, i;char* v = (char*)malloc(sizeof(char) * nState);memset(v, 0, sizeof(char) * nState);for(k = 1; k < nState; k++) {// 检查是否单增字母序列int isFinished = 1;char prevChar = 'a' - 1;for(i = 0; i < n; i++) {if ((k & (1<<i)) > 0) {if (word[i] <= prevChar) {isFinished = 0; break;} else {prevChar = word[i];}}}// 1. 如果单增序列 - 先行者输if (isFinished) {v[k] = 'L';}else{// 2. 如果不是单增序列，检查可能的子节点，当找到先行者输节点时可以提前终止int canWin = 0;for(i = 0; i < n; i++) {if ((k & (1<<i)) > 0) {nextK = k ^ (1<<i);if (v[nextK] == 'L') { canWin = 1; break;}}}if (canWin) v[k] = 'W'; else v[k] = 'L';}}int win = (v[nState - 1] == 'W') ? 1 : 0;free(v);if (win) return 1; else return 0;
}