一、目的:  熟悉和掌握对某个问题的状态空间描述，学会组织状态空间图，用搜索图来求解问题。

二、原理
从某个初始状态开始，每次加一次操作符，递增地建立起操作符的试验序列，直到达到目标状态止。寻找状态空间的全部过程包括从旧的状态描述产生新的状态描述，以及此后检验这些新的状态描述，看其是否描述了该目标状态。

三、问题实现

• 总数据库是到目前为止所访问过的城市表。初始数据库被描述为表(A)。我们不允许目录表中任一城市出现多于一次，只有城市A例外，但也只有当所有其它城市均已出现之后，才能再次出现A。
• 规则对应于决策：(a)下一步走向城市A；(b)下一步走向城市B；…；(e)下一步走向城市E。一条规则除非能够把某个数据库变为一合法数据库，否则就不适用于这个数据库。例如，应用“下一步走向城市A”这条规则就不使用于尚未出现所有其它城市的任一数据库。
• 任一以A为起点和终点，并出现所有其它城市的总数据库，都满足终止条件。我们可以使用距离图表来计算任一旅程的总距离。提出作为解答的任一旅程，必须是具有最短距离的旅程。
• 用图搜索控制方式求解该问题时可能生成的部分搜索树。树枝旁边的数字是应用相应规则时加到旅程上的距离增量。

1. 规约图

四、运行界面：

五、程序实现

1. 开发平台 ：本程序使用VC++6.0开发。

1. 部分源程序清单：

  class CAboutDlg : public CDialog
{
public:
CAboutDlg();

// Dialog Data
//{{AFX_DATA(CAboutDlg)
enum { IDD = IDD_ABOUTBOX };
//}}AFX_DATA

// ClassWizard generated virtual function overrides
//{{AFX_VIRTUAL(CAboutDlg)
protected:
virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support
//}}AFX_VIRTUAL

// Implementation
protected:
//{{AFX_MSG(CAboutDlg)
//}}AFX_MSG
DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
//{{AFX_DATA_INIT(CAboutDlg)
//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CAboutDlg)
//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
//{{AFX_MSG_MAP(CAboutDlg)
// No message handlers
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
// CTest2Dlg dialog

CTest2Dlg::CTest2Dlg(CWnd* pParent /*=NULL*/)
: CDialog(CTest2Dlg::IDD, pParent)
{
//{{AFX_DATA_INIT(CTest2Dlg)
// NOTE: the ClassWizard will add member initialization here
//}}AFX_DATA_INIT
// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
size=0;
for(int i=0;i<15;i++)
for (int j=0;j<15;j++)
a[i][j]=0;
}