LogoElfin.cc

水排序算法

9/4/2022
Feature
算法

之前也写过类似扑克解谜类的解题算法，本质上都是启发式搜索（和A-Star非常相似）。解决这类问题是有一些相似的步骤的：

定义状态

首先要做的事情是定义状态，这类游戏的过程就是状态和状态之间的转换。以水排序为例，首先是分段数（即一瓶水可以被分割为多少份）。然后就是一个瓶子和水的数组：

type State = {
	segment: number;
	bottles: string[][];
}

这里瓶子中的水，我选string 类型，因为想要直接拿颜色代码来填充，方便后续做结果的呈现。实际上这个随便填，相同的字符串就认为是同一种颜色，debug的时候可以直接写成红黄蓝都行，字符串就是这样方便。

定义状态转换

第二步就是定义状态转换，即给定一种状态的输入，给出若干新的状态的输出。为了方便用户理解，还要给出这个新状态获得的操作信息。

type Transition = {
	parent: Transition | null;
	fromBottleIndex: number;
	toBottleIndex: number;
	doneState: State;
}

这里将Transition定义成类似单向链表的形式是为了将过程中的每一步衔接起来形成完整的结果。每一步Transition都是由上一步的Transition通过将编号为fromBottleIndex的瓶子中的水倒入toBottleIndex瓶子中。

状态编码

状态编码是为了解决这么几个问题：

  1. 消除对称性
  2. 提高状态比较的效率

消除对称性

游戏中任意两个状态，如果他们有相同的后续展开，那么我就认为这两个状态是对称的。拿水排序举个例子，比如我有8个瓶子，其中6个是有水的，有2个是空瓶子。那么假设有2个状态，他们的那6个有水的瓶子中水的组合都是一样的，只是2个空瓶子出现的位置不一样。那么我们应该认为这两个状态是对称的。如果我展开计算了其中一个状态，那么我就没有必要再展开计算另外一个了。对于水排序来说消除对称性，就是要消除空瓶子在不同位置的状态的差异。 消除对称性是必须的，一来可以大大提高算法的效率；二来可以避免计算过程陷入无限循环。

提高状态比较的效率

如果我们要比较两个状态的异同，最简单的方法就是写一个比较函数，把状态中的每个字段手动比对一次。但是我喜欢将状态转换为一个字符串，然后我们对比状态是否相同就直接比较字符串就可以了，通常比较字符串是更高效的。

编码方式

所以状态编码要满足以下的原则：

  1. 不同的状态编码一定不同
  2. 对称的状态编码要相同

以水排序为例，具体可以这么做：

  1. 将所有的瓶子按照水位从高到底的顺序排序
  2. 相同水位的瓶子，按照字符串比对的大小，从高位开始向下比，较小的排在前面
  3. 将排序后的瓶子，按照从高位到低位，依次输出自己的颜色字符串，瓶子和瓶子之间用某个分隔符分隔（比如用|）。

按照上面的逻辑，无论空瓶子在哪，由于排序都会把它安排在最后面。因此就消除了对称性。

启发式搜索

最后一点就是启发式搜索了，所谓启发式就是不是随机选择下一步的方向，而是根据一定的特征优先选择更有可能是正确答案的下一步，如果启发的方式得当，将可以大大提高搜索结果的效率。这里主要考虑两个因素（参考A-Star）：

  1. 从起始状态到当前状态的步数（对应 f(x) = g(x) + h(x) ）
  2. 从当前状态到最终状态的预估（对应 f(x) = g(x) + h(x) ）

其中第一点是直观且精确的，就是记录一下从起点到当前状态的步数就行了。第二点相对会复杂一些，以水排序为例，评估方式是计算当前状态的复杂度。 复杂度的定义如下：

  1. 如果一个状态是最终状态则其复杂度为0
  2. 如果一个状态离最终状态只差1步，则其复杂度为1
  3. 依次类推

这里有个问题，给出某个状态，我其实并不知道它离最终状态差几步，不过启发式其实不需要精确，只要预估就好。 所以我计算复杂度的方法是这样的：

  1. 状态复杂度 = 当前状态所有瓶子的复杂度之和
  2. 如果瓶子是空的，或者只有1种颜色的水，那么该瓶子的复杂度是0
  3. 如果瓶子中的水有2段颜色，则瓶子的复杂度为1，每多一段颜色复杂度+1

想想按照这样的逻辑，最终状态的瓶子要么是空的，要么是单一的某种颜色，所以整体复杂度肯定是0，然后颜色越混乱复杂度越高，也是符合直觉的。

在有了编码和启发式搜索的逻辑后，我们要稍稍修改一下Transition的定义：

type Transition = {
	parent: Transition | null;
	fromBottleIndex: number;
	toBottleIndex: number;
	doneState: State;
	stateHash: string; // 状态hash
	step: number; // 从最初状态到当前的步数
	complexity: number; // 复杂度
	f: number; // f = step + complexity
}

组装代码

好，到了这里，我们已经把解算的要点都讲了。最后就是组装所有代码的时候了。我并不打算贴非常具体的代码了，如果大家要写可以参考A-Star。 主体大概是这样的：

function solve(initState: State) {
	const open: Array<Transition> = [{
		parent: null,
		fromBottleIndex: -1,
		toBottleIndex: -1,
		doneState: initState,
		stateHash: calcHash(initState),
		step: 0,
		complexity: calcComplexity(initState),
		f: calcComplexity(initState)
	}];
	const close: Array<Transition> = [];
	
	while(open.length > 0) {
		open.sort(sortWithF); // 按照 f 排序；如果进一步追求高效可以把open换成堆，用小顶堆
		const min = open.shift();
		if (min.complexity === 0) { // 最终状态
			const ret: Array<Transition> = [];
			let p: Transition | undefined = min;
			while( p !=== undefined ) {
				ret.push(p);
				p = p.parent;
			}
			ret.reverse();
			return ret;
		}
		const opts = listOptions(min); // 输出可能的每一步
		opts.forEach(opt => {
			if (close.findIndex( v => v.stateHash === opt.stateHash) < 0) {
				// 该状态不在close列表中，未被探索过
				open.push(opt);
			}
		})
		close.push(min); // 将min标记为已探索
	}
	return []; // 无解
}