这一次让偶仍然用拿手的穷举法来写一个自动解推箱子问题的机器人吧。
偶使用了yzwykkldczsh同志写的状态机模板以及该模板的配套算法“万用智能超级无穷迭代动态规划递归算法”（为纪念友人Jornathan Ding,此算法又称为H>D算法）。它的基本原理是：
1.将每一步的人和箱子的数据放到一个记录里，此记录表示当前状态
2.设置当前状态为已访问
3.遍历下面的每一个子状态。若所有子状态都已访问或无解，则当前步也无解
4.若子状态有解，则恢复此状态为未访问。
对所有子状态，重复1-4步。
此算法可解很多智力题，比如倒酒问题、过河问题，等等。
偶的测试程序里写死了地图。实际应用中应当从文件中载入。下面帖出测试程序代码：
ACIter.h源码
/*
* CACIter：用于记录结点访问状态的辅助模板类。TNodeKey为唯一确定当前状态的哈希值类型，应当是一个struct。
* 三种状态是：nsNone:无或不在结点访问状态表中；nsVisiting:正在访问；nsDead:已死亡
*/
#pragma once
#include <map>
enum NodeStatus {
nsNone,
nsVisiting,
nsDead
};
template<typename _Ty>
class CMemLessTempl
: public std::binary_function<_Ty, _Ty, bool>
{
public:
bool operator()(const _Ty& _Left, const _Ty& _Right) const
{
/* 对于两个struct的比较，用内存逐byte比较即可。
要注意的是struct如果不是按字节对齐的话，需要在初始化时memset为全0，否则可能有干扰数据 */
unsigned char *p1 = (unsigned char *)&_Left, *p2 = (unsigned char *)&_Right;
return memcmp(p1, p2, sizeof(_Ty)) < 0;
}
};
template<typename TNodeKey>
class CACIter
{
private:
typedef std::map<TNodeKey, enum NodeStatus, CMemLessTempl<TNodeKey> > NODESTATUSMAP;
/* 结点访问状态记录树 */
NODESTATUSMAP m_NodeStatus;
public:
/* 获取当前结点访问状态。找不到也返回nsNone */
virtual enum NodeStatus GetStatus(TNodeKey key)
{
NODESTATUSMAP::iterator it = m_NodeStatus.find(key);
if ( it == m_NodeStatus.end() ) return nsNone;
return it->second;
}
/* 设置当前结点访问状态。如果设为nsNone，则可删除这个结点 */
virtual void SetStatus(TNodeKey key, enum NodeStatus status)
{
if (status == nsNone)
{
NODESTATUSMAP::iterator it = m_NodeStatus.find(key);
if ( it == m_NodeStatus.end() ) return;
m_NodeStatus.erase(it);
return;
}
m_NodeStatus[key] = status;
}
public:
CACIter(void) {}
~CACIter(void) {}
};
主程序源码（偶是用VS2003的console app写的测试程序）
// PushBoxRobot.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "conio.h"
#include "ACIter.h"
#include <map>
#include <vector>
/* 地图最大宽度和高度 */
#define MAXMAPWIDTH 40
#define MAXMAPHEIGHT 40
/* 假定最多有6个箱子 */
#define MAXBOXCOUNT 6
/* 地图上几种元素：空格表示空地，X表示阻挡物，?表示箱子移动的目的地，O表示箱子的起始位置，*表示人的起始位置 */
#define MAP_EMPTY ' '
#define MAP_BLOCK 'X'
#define MAP_HOLE '?' // target position
#define MAP_BOX 'O' // box start position(internal use)
#define MAP_MAN '*' // man start position(internal use)
/* 当前状态。x,y为人的位置，boxx[],boxy[]为箱子的位置。假定最多有6个箱子 */
struct _PushStatus
{
// man pos
char x, y;
char boxx[MAXBOXCOUNT], boxy[MAXBOXCOUNT];
};
enum TryResult
{
trFailed,
trUnknown,
trSuccess
};
/* 工作类 */
class CPushBoxAI : public CACIter<struct _PushStatus>
{
public:
/* 记录当前工作路径的数组，记录最短成功路径的数组 */
std::vector<struct _PushStatus> m_vStepLog, m_vSuccLog;
/* 地图，其中不包含人和箱子 */
char m_Map[MAXMAPWIDTH][MAXMAPHEIGHT];
/* 地图宽高、箱子数量、最短成功路径 */
int m_nWidth, m_nHeight, m_nBoxCount, m_nMinSteps;
/* 初始化地图和初始状态 */
void Init(struct _PushStatus& status);
/* 尝试下一个方向。status是当前状态，level是下一个方向的深度（步数），dx,dy指出下一个方向 */
enum TryResult TryDir(struct _PushStatus status, int level, int dx, int dy);
/* 求解 */
bool Execute(void);
/* 打印当前状态下的地图 */
void DumpMaze(struct _PushStatus status);
};
void CPushBoxAI::Init(struct _PushStatus& status)
{
/* 写死的一个地图，实际应用中应替换成从文件中读入。略。 */
char *map = {
" XXXXX"
" X *X"
"XXX XOO X"
"X?X X O X"
"X?XXX XX "
"X? XX "
"X X XX"
"XXXX XX"
" XXXXX "
};
char *p = map;
m_nHeight = 9;
m_nWidth = 9;
m_nBoxCount = 0;
for ( int j = 0; j < 9; j++ )
for ( int i = 0; i < 9; i++, p++ )
{
switch(*p)
{
case ' ': m_Map[i][j] = MAP_EMPTY; break;
case 'X': m_Map[i][j] = MAP_BLOCK; break;
case '?': m_Map[i][j] = MAP_HOLE; break;
case '*': status.x = i; status.y = j; m_Map[i][j] = MAP_EMPTY; break;
default: // O
status.boxx[m_nBoxCount] = i;
status.boxy[m_nBoxCount] = j;
m_Map[i][j] = MAP_EMPTY;
m_nBoxCount++;
break;
}
}
}
enum TryResult CPushBoxAI::TryDir(struct _PushStatus status, int level, int dx, int dy)
{
int x = status.x + dx;
int y = status.y + dy;
/* 超出地图范围？失败 */
if ( x < 0 || x >= m_nWidth || y < 0 || y >= m_nHeight ) return trFailed;
/* 碰到阻挡？失败 */
if ( m_Map[x][y] == MAP_BLOCK ) return trFailed;
int nLeft = m_nBoxCount;
status.x = x;
status.y = y;
for ( int i = 0; i < m_nBoxCount; i++ )
{
if ( x == status.boxx[i] && y == status.boxy[i] )
{
// 碰到了箱子。尝试推动它
int m = status.boxx[i] + dx;
int n = status.boxy[i] + dy;
// 尝试推动箱子出地图？失败
if ( m < 0 || m >= m_nWidth || n < 0 || n >= m_nHeight ) return trFailed;
// 箱子碰到阻挡？失败
if ( m_Map[m][n] == MAP_BLOCK ) return trFailed;
// 箱子碰到其它箱子？失败
for ( int j = 0; j < m_nBoxCount; j++ )
if ( j != i && m == status.boxx[j] && n == status.boxy[j] )
return trFailed;// crash
status.boxx[i] = m;
status.boxy[i] = n;
}
// 箱子到达目的地？
if ( m_Map[status.boxx[i]][status.boxy[i]] == MAP_HOLE ) nLeft--;
}
/* 超出现有最短步数？失败 */
if (level >= m_nMinSteps) return trUnknown;
// 当前状态如果已经失败或者已经访问，则此步也失败
if (GetStatus(status) != nsNone) return trFailed;
// 记录当前路径
if ( (int)m_vStepLog.size() == level ) m_vStepLog.push_back(status);
else if ( (int)m_vStepLog.size() > level ) m_vStepLog[level] = status;
// 所有箱子都到达了目的地
if (nLeft == 0)
{
m_nMinSteps = level;
// 将当前路径拷贝到成功路径中，并且更新最小步数变量
m_vSuccLog.clear();
std::insert_iterator< std::vector<struct _PushStatus> > iter( m_vSuccLog, m_vSuccLog.end() );
copy( m_vStepLog.begin(), m_vStepLog.end(), iter );
// 返回成功
return trSuccess; // success
}
// 设置当前状态为正在访问，并且访问下面的状态
SetStatus(status, nsVisiting);
int n = 0;
enum TryResult tr;
bool bSucc = false;
tr = TryDir(status, level + 1, -1, 0);
if ( tr != trFailed ) n++;
if ( tr == trSuccess ) bSucc = true;
tr = TryDir(status, level + 1, 1, 0);
if ( tr != trFailed ) n++;
if ( tr == trSuccess ) bSucc = true;
tr = TryDir(status, level + 1, 0, -1);
if ( tr != trFailed ) n++;
if ( tr == trSuccess ) bSucc = true;
tr = TryDir(status, level + 1, 0, 1);
if ( tr != trFailed ) n++;
if ( tr == trSuccess ) bSucc = true;
// 如果后续状态都无法访问或不成功，则当前状态也死亡。否则恢复当前状态为未访问。
if ( n == 0 ) SetStatus(status, nsDead);
else SetStatus(status, nsNone);
if ( bSucc ) return trSuccess;
else if ( n > 0 ) return trUnknown;
else return trFailed;
}
bool CPushBoxAI::Execute(void)
{
m_nMinSteps = 1000;
int n = 0;
struct _PushStatus status;
// 一定要初始化为全0
memset(&status, 0, sizeof(struct _PushStatus));
// 初始化地图和开始时的状态
Init(status);
// 开始访问相邻四个方向
if ( TryDir(status, 0, -1, 0) == trSuccess ) n++;
if ( TryDir(status, 0, 1, 0) == trSuccess ) n++;
if ( TryDir(status, 0, 0, -1) == trSuccess ) n++;
if ( TryDir(status, 0, 0, 1) == trSuccess ) n++;
return n > 0;
}
void CPushBoxAI::DumpMaze(struct _PushStatus status)
{
for ( int j = 0; j < m_nHeight; j++ )
{
for ( int i = 0; i < m_nWidth; i++ )
{
char c = m_Map[i][j];
for ( int k = 0; k < m_nBoxCount; k++ )
if ( i == status.boxx[k] && j == status.boxy[k] )
{
c = 'O';
break;
}
if ( i == status.x && j == status.y ) c = '*';
printf("%c", c);
}
printf("/n");
}
}
int _tmain(int argc, _TCHAR* argv[])
{
CPushBoxAI pbai;
if (pbai.Execute())
{
// 成功，打印成功路径。
for ( int i = 0; i < pbai.m_nMinSteps + 1; i++ )
pbai.DumpMaze(pbai.m_vSuccLog[i]);
printf("OK");
}
else printf("NO RESULT"); // 无解
getch();
return 0;
}
06/6/30: 发现原算法有些问题，当超过规定步数时也会把当前状态置为Dead，会引起误判，造成不能算出最优解。做了一些改动。每步尝试将返回3种类型中的一种：失败、成功或未知。如下一步是未知，则不修改状态。（遗憾的是算法又慢鸟大概2秒钟 -___-||| ）
PS: 地盘上很凉快啊~~~