IQCar的实现II——解题思路

核心提示：上文简单介绍了IQCar游戏，接下来将描述用计算机如何求出它的解法，IQCar的实现II——解题思路，学过数据结构的，第一感觉就是用“深度优先搜索”或者是“广度优先算法”，由于各连线的长默认都是1，Dijkstra算法其实就是广度优先算法，就是不停的尝试每一种可能，直到到达解

上文简单介绍了IQCar游戏。接下来将描述用计算机如何求出它的解法。

　　学过数据结构的，第一感觉就是用“深度优先搜索”或者是“广度优先算法”。就是不停的尝试每一种可能，直到到达解。然后将尝试的过程输出即可。

　　仔细观察上文的图片，发现，每一辆车的可能性位置可能性非常少（由于车子只能前后移动，故长度为3的车子只有4种可能，长度为2的车子有五种可能）。那么，则这些车子排列的可能性就不会多（原因是，如果车子多，则彼此之间的限制会很多，因为两辆车不能挤在一个格子里，如果车子少，虽然限制少但是车子少，必然总数少）。这样，一般的题目，把所有的车子排列构成一个集合的话，这个集合中的元素不会很多（实际情况是，一般的题目，这个集合的元素在1200左右）。

　　想到这，我想到用图论的方法求解。

　　所有的车子的一个位置排列，成为图中的一个点，两点之间的连线表示能从一个排列移动一个位置到另一个排列。题目中的初始状态为图中的一个点，达到解题条件的为另一个点（这样的点可能不止一个），问题就转化为在图中从一个点找到到另一个点的通路。

　　这个求通路的有一个非常有名的算法，Dijkstra算法（最短路径算法）。

　　那么本问题就转化为两个步骤

　　1、根据输入的初始状态，生成一个集合，所有车子的一个位置排列为集合中的一个元素。并且为每一个元素建立他们之间的关系（有连线则表示能从一个排列移动一个位置到另一个排列，反之则无连线）。

　　2、用Dijkstra算法求出一条通路，这条通路也是最短通路，也就是最优解

　　注：写完程序后，细细想来，在本题中，由于各连线的长默认都是1，Dijkstra算法其实就是广度优先算法。

　　后文将具体的描述各个模块的实现。