相关疑难解决方法(0)

如果您不熟悉高峰时段,游戏包含一系列不同大小的汽车,水平或垂直设置在具有单个出口的NxM网格上.
只要另一辆车没有挡住它,每辆车都可以按照它设定的方向前进/后退.你永远不能改变汽车的方向.
有一辆特别的车,通常是红色的.它设置在出口所在的同一排,游戏的目标是找到一系列动作(移动 - 向前或向前移动N步),这将允许红色汽车驶出迷宫.

我一直在努力思考如何在计算上解决这个问题,我真的不能想到任何好的解决方案.
我想出了一些:

1. 回溯.这很简单 - 递归和更多递归,直到找到答案.然而,每辆车可以以几种不同的方式移动,并且在每个游戏状态中可以移动一些汽车,并且由此产生的游戏树将是巨大的.
2. 某种约束算法将考虑需要移动的内容,并以某种方式递归地工作.这是一个非常粗略的想法,但这是一个想法.
3. 图表？将游戏状态建模为图形并对着色算法应用某种变化来解决依赖关系？同样,这是一个非常粗略的想法.
4. 一位朋友提出了遗传算法.这有点可能但不容易.我想不出一个好的评估函数的方法,没有它我们什么都没有.

所以问题是 - 如何创建一个采用网格和车辆布局的程序,并输出一系列步骤来获得红色汽车？

次级问题:

1. 找到一些解决方案.
2. 寻找最佳解决方案(最小移动次数)
3. 评估当前状态的好坏程度

示例:如何在此设置中移动汽车,以便红色汽车可以通过右侧的出口"退出"迷宫？
http://scienceblogs.com/ethicsandscience/upload/2006/12/RushHour.jpg