IQCar的实现II——解题思路

1/6/2010来源:ASP技巧人气:2621

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

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

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

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

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

  这个求通路的有一个非常有名的算法,Dijkstra算法(最短路径算法)。

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

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

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

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

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