推箱子的求解

　　经过两周的折腾，白了头发无数，终于能算一些简单的地图了。15x15以内的地图基本上不超过5秒钟能有近似最优解。超过20x20的地图，10分钟之内没有结果，我也没耐心等下去。
　　整个算法看起来是这样的：首先选择可以移动的箱子的集合，选择一个深度优先遍历，当发现下一步有重复时，选择较短的路径；当树的深度超过一个限度时，把叶子节点送入一个链表；只要那个链表不空，那么设定新的最大深度，回到第一步。为了判定初始的深度，需要对箱子与目标点作一次匹配（我选择的是最大代价匹配）。
　　为了实现A*算法，使用了许多类来作支撑，比如：
　　　clsShortestPath　　　　　 专门求迷宫的最短路径，翻译自高中时候的程序
　　　clsGraph_MostMatching　　 二部图最大匹配
　　　clsMapData　　　　　　　　跟地图有关的操作在这里
　　　clsMapStatus　　　　　　　跟地图状态有关的操作在这里
　　　clsSolution　　　　　　　 求解的主程序，根据一个基本clsSolutionNode作为树根，展开所有解
　　　clsSolutionNode　　　　　 解的内容、保存下一个解的链状结构，当树的深度超过给定值时会调用制定的函数保存状态
　　　clsSolutionNodeHistory　　纪录解的历史，在重复的解中选择路径比较短的解

　　如果有人说这样写效率会不会很低？我认为不会，我没有使用virtual，不算真正的OO，在静态绑定的作用下，效率不会很低。
　　代码总共33k，没办法把源代码贴出来。下面是程序到目前为止的5个版本的What's New，从中可以说明一些问题。

V1
● 用链表实现广度优先
● 计算下一级时，回收上一级内存

V2
● 改进的内存回收，能快速回收同一层的内存
● 阻止嵌入角落
● 修改了过程保存的方式（不再是string），减小了内存使用
● 防止重复上一次的步骤的反过程（比如上一次是向左，那么这一次不会向右），用list实现


V3
● 下定决心，把广度优先改成深度优先，用树实现，保存下一步的是list
● 新建clsSolutionNodeHistory，加强了重复路径搜索能力，杜绝重复的搜索
● 明确了地图clsMap、地图数据clsMapData的不同（前者只有地形数据），减小了内存占用和构造时间
● 修正了图形显示的小Bug（箱子、目标位置的标记不能通过单次循环完成）
● 新增了一个小的地图编辑器（VB）

V4
● 地图优化：自动判定不能放置箱子的区域（不需要再在地图编辑器中作弊了）
● 改进的clsSolutionNodeHistory：情况相同时，如果上一次失败了，那么取消现在的尝试；如果上一个记录还没有计算过，那么选择路径比较短的一次
● 进一步改进了状态的保存，clsMapData改名为clsMapStatus、clsMap改名为clsMapData
● 追加了一个看似十分垃圾的评价函数，以箱子与目标的距离作为判定依据，这样就形成了一个简化的A*算法
● 强制限定了运算深度，由于不能自动追加深度，还不能看作是IDA*算法
● 为了得到初始的运算深度，用网络流实现了二部图的最优匹配
● 为了提供最优匹配的原始数据（目前是每个箱子到每个目标的距离），编写了最短路经搜索代码，代码用的是高中时写的VB程序，算法名字不记得了，只知道空间复杂度O(n^4)，时间复杂度O(n^2)

V5
● 题解程序将步数溢出的节点压入一个链表，IDA*得以实现
● 最优匹配从自小代价改为最大代价（也就是说，假定编地图的人让玩家总是把箱子推到最远的目标点，真是无语了）