一、目的: 熟悉和掌握对某个问题的状态空间描述,学会组织状态空间图,用搜索图来求解问题。
二、原理
从某个初始状态开始,每次加一次操作符,递增地建立起操作符的试验序列,直到达到目标状态止。寻找状态空间的全部过程包括从旧的状态描述产生新的状态描述,以及此后检验这些新的状态描述,看其是否描述了该目标状态。
bst
三、问题实现
- 总数据库是到目前为止所访问过的城市表。初始数据库被描述为表(A)。我们不允许目录表中任一城市出现多于一次,只有城市A例外,但也只有当所有其它城市均已出现之后,才能再次出现A。
- 规则对应于决策:(a)下一步走向城市A;(b)下一步走向城市B;…;(e)下一步走向城市E。一条规则除非能够把某个数据库变为一合法数据库,否则就不适用于这个数据库。例如,应用“下一步走向城市A”这条规则就不使用于尚未出现所有其它城市的任一数据库。
- 任一以A为起点和终点,并出现所有其它城市的总数据库,都满足终止条件。我们可以使用距离图表来计算任一旅程的总距离。提出作为解答的任一旅程,必须是具有最短距离的旅程。
- 用图搜索控制方式求解该问题时可能生成的部分搜索树。树枝旁边的数字是应用相应规则时加到旅程上的距离增量。
- 规约图
四、运行界面:
五、程序实现
- 开发平台 :本程序使用VC++6.0开发。
- 部分源程序清单:
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;
}