汽车4S店怎么做网络营销.ppt

第四章搜索技术
状态空间法
问题归约法
博弈树搜索
局部搜索
How to find the best path in game ?
迷宫问题
s-----s s s s
s s-----s-----s-----s
s-----s-----s-----s s
s s s s s
s-----s-----s-----s-----s
S0
Sg
搜索的挑战—组合爆炸
魔方问题
博弈问题
皇后问题
行商问题
排课问题(调度问题)
背包问题
…………
数码问题
1
2
3
8
4
5
6
7
1
2
3
8
4
5
6
7
(目标状态)
(初始状态)
八数码难题(8-puzzle problem)
4
2
6
1
8
3
5
7
状态图概念
状态图的概念
状态图(状态空间图)实际上是一类问题的抽象表示。
许多智力问题(八数码问题、梵塔问题、旅行商问题、八皇后问题、农夫过河问题等)。
实际问题(如路径规划、定理证明、演绎推理、机器人行动规划等)都可以归结为在某一状态图中寻找目标或路径的问题。
农夫过河问题
有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管,则狼要吃羊,羊要吃白菜。但是船很小,只够农夫带一样东西过河。问农夫该如何解此难题?
农夫过河问题状态空间法表示
以向量(人,狼,羊,菜)表示状态,其中每个变元可取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)。
状态空间法
问题的状态空间表示(状态图表示)
状态空间的三元组(S, O, G)表示.
S:初始状态集合; O: 操作集合;
G:目标状态集合
状态空间的搜索策略(状态图搜索)
广度优先搜索, 深度优先搜索, 启发式搜索