estpathingame?迷宫问题s-----ssssss-----s-----s-----ss-----s-----s-----ssssssss-----s-----s-----s-----sS0Sg搜索的挑战—组合爆炸魔方问题博弈问题皇后问题行商问题排课问题(调度问题)背包问题…………数码问题1238456712384567(目标状态)(初始状态)八数码难题(8-puzzleproblem)426183574.1状态图概念状态图的概念状态图(状态空间图)实际上是一类问题的抽象表示。许多智力问题(八数码问题、梵塔问题、旅行商问题、八皇后问题、农夫过河问题等)。实际问题(如路径规划、定理证明、演绎推理、机器人行动规划等)都可以归结为在某一状态图中寻找目标或路径的问题。农夫过河问题有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管,则狼要吃羊,羊要吃白菜。但是船很小,只够农夫带一样东西过河。问农夫该如何解此难题?农夫过河问题状态空间法表示以向量(人,狼,羊,菜)表示状态,其中每个变元可取0或1,取0表示在左岸(出发点),取1表示在右岸初态是:(0,0,0,0)终态是:(1,1,1,1)非法中间状态有:(0,0,1,1),(0,1,1,0),(0,1,1,1),?(1,1,0,0),(1,0,0,1),(1,0,0,0)。(1,0,0,1)(0,0,0,0)(1,0,1,0)(1,1,0,0)(0,0,1,0)(1,1,1,0)(1,0,1,1)(0,1,1,0)(0,0,1,1)(人,狼,羊,菜)(0,0,0,1)(1,1,0,1)(0,1,0,1)(1,1,1,1)4.2状态空间法问题的状态空间表示(状态图表示)状态空间的三元组(S,O,G)表示.S:初始状态集合;O:操作集合;G:目标状态集合状态空间的搜索策略(状态图搜索)广度优先搜索,深度优先搜索,启发式搜索
全文预览
