lec5问题的解空间课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,如何求解问题？,如何求解问题？,1,如果我们真正地理解了问题，就会自然而然得到答案，因为答案和问题总是分不开的。,-克里希纳幕尔蒂企鹅读本,如果我们真正地理解了问题，就会自然而然得到答案，因为答案,2,搜索问题,从某种角度来看，所有问题都可以表述为搜索问题。,解答一个问题不就是搜索这个问题的解吗？,当然，搜索的空间就是解的空间，而搜索就是在解的空间找出需要的一个。,搜索问题从某种角度来看，所有问题都可以表述为搜索问题。,3,复杂问题常常有很多的可能解，这些,可能解构成了问题的解空间,。解空间也就是进行穷举的搜索空间，所以，解空间中应该包括所有的可能解。确定正确的解空间很重要，如果没有确定正确的解空间就开始搜索，可能会增加很多重复解，或者根本就搜索不到正确的解。,问题的解空间,复杂问题常常有很多的可能解，这些可能解构成了,4,(a)二维搜索空间无解 (b)三维搜索空间的解,图8.1 错误的解空间将不能搜索到正确答案,例如：桌子上有6根火柴棒，要求以这6根火柴棒为边搭建4个等边三角形。,(a)二维搜索空间无解,5,对于任何一个问题，解空间的大小与解的表达方式有关，可能解的,表示方式,和它相应的,解释,隐含了解空间及其大小。,例如，对于有,n,个物品的0/1背包问题，其可能解的表示方式可以有以下两种：,（1）可能解由一个,不等长向量,组成，当物品,i,(1,i,n,)装入背包时，解向量中包含分量,i,，否则，解向量中不包含分量,i,，当,n,=3时，其解空间是：,(),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3),（2）可能解由一个,等长向量,x,1,x,2,xn,组成，其中,xi,=1(1,i,n,)表示物品,i,装入背包，,xi,=0表示物品,i,没有装入背包，当,n,=3时，其解空间是：,(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1),对于任何一个问题，解空间的大小与解的表达方式,6,如何将解空间组织成能高效搜索的方式比较麻烦，目前人们提供了一些有用的想法：比如可以将搜索空间组织成一棵树，即,解空间树,（Solution Space Trees,也称状态空间树）。完整解就在树的叶子上。沿着树的每一个分枝经过一系列的步骤来构造完整解。,树的根结点位于第1层，表示搜索的初始状态，第2层的结点表示对解向量的第一个分量做出选择后到达的状态，第1层到第2层的边上标出对第一个分量选择的结果，依此类推，从树的,根结点到叶子结点的路径,就构成了,解空间的一个可能解,。,如何将解空间组织成能高效搜索的方式比较麻烦，,7,对于,n,=3,的,0/1,背包问题，其解空间树如图所示，树中的,8,个叶子结点分别代表该问题的,8,个可能解。,对物品1的选择,对物品3的选择,对物品2的选择,1,1,1,1,1,1,0,0,0,0,0,0,0,1,1,2,3,4,5,7,8,11,12,14,15,3,10,6,9,对于n=3的0/1背包问题，其解空间树如图所示，树中的8个叶,8,对于,n,=4,的,TSP,问题，其解空间树如图所示，树中的,24,个叶子结点分别代表该问题的,24,个可能解，例如结点,5,代表一个可能解，路径为,1,2,3,4,1,，长度为各边代价之和。,2,4,3,4,2,2,3,4,3,4,1,3,1,4,2,4,1,2,1,2,3,3,1,2,1,3,4,1,3,1,3,1,2,3,2,1,2,1,4,2,4,1,4,3,4,3,2,2,4,3,4,1,2,3,1,2,4,1,3,4,n=4的TSP问题的解空间树,5,7,10,12,15,17,21,23,26,28,31,33,37,39,42,44,47,49,52,54,57,59,62,64,4,6,9,11,14,16,20,22,25,27,30,32,36,38,41,43,46,48,51,53,56,58,61,63,3,8,13,19,24,29,35,40,45,50,55,60,2,18,34,24,1,1,2,3,4,3,4,对于n=4的TSP问题，其解空间树如图所示，树中的2,9,对于大部分问题来说，其解空间的规模为输入规模的,指数函数,甚至更高。,显然，在如此巨大的解空间,实施穷举,将是费时费力、,低效率,的。,因此，寻找更加有效的搜索手段就是算法不断推进的源动力。,后面要介绍的分治思想、动态规划思想、贪婪选择思想和随机化思想都采用了各种巧妙的手段成功地,避开了“指数魔咒”,把搜索空间的规模缩小到多项式级内。,对于大部分问题来说，其解空间的规模为输入规模的指数函数甚至更,10,实际问题难以求解的原因（一）,搜索空间中可能解的数目太多；,问题如此复杂以至于为得到任何解答，不得不采用问题的简化模型；,求解问题过程：问题,模型解,无论何时求解一个实际问题，都要先建立一个模型。例：抛球轨迹是什么？抛物线？,实际问题难以求解的原因（一）搜索空间中可能解的数目太多；,11,例：握手问题,（爱丁堡大学Peter Ross提出）,史密斯先生和太太请四对夫妻来参加晚会。每个人来的时候，房间里的一些人会和另外一些人握手。当然，每个人都不会与自己的配偶握手，也不会跟同一个人握手两次。,之后，史密斯先生问每个人和别人握了几次手，他们的答案都不一样。,那么，史密斯太太和别人握了几次手呢？,例：握手问题（爱丁堡大学Peter Ross提出）史密斯先生,12,lec5问题的解空间课件,13,lec5问题的解空间课件,14,lec5问题的解空间课件,15,lec5问题的解空间课件,16,lec5问题的解空间课件,17,实际问题难以求解的原因（二）,实际问题往往随时间而变；,实际问题往往存在很多约束条件；,如排课表,实际问题难以求解的原因（二）实际问题往往随时间而变；,18,思考：五个颜色各异的房子里住着5个不同国籍的人，他们所养的宠物、,喜欢的饮料、拥有的汽车各不相同,（1）英国人住在红房子里；,（2）西班牙人养狗；,（3）居住在绿房子里的人喜欢喝可乐；,（4）乌克兰人喜欢喝蛋酒；,（5）住在绿房子里的人是住在象牙色房子里人的右邻；,（6）拥有老爷车的人养蜗牛；,（7）拥有福特车的人住在黄房子里；,（8）住在中间房子里的人喝牛奶；,（9）挪威人住在最左边房子里；,（10）拥有雪佛莱汽车的人与养狐狸的人是邻居；,（11）拥有福特汽车的人与养马的人是邻居；,（12）拥有奔驰汽车的人爱喝橙汁；,（13）日本人开大众；,（14)挪威人的邻居住在兰房子里,问：斑马属于谁？谁爱喝矿泉水？,思考：五个颜色各异的房子里住着5个不同国籍的人，他们所养的宠,19,（,1）英国人住在红房子里；,（2）西班牙人养狗；,（3）居住在绿房子里的人喜欢喝可乐；,（4）乌克兰人喜欢喝蛋酒；,（5）住在绿房子里的人是住在象牙色房子人的右邻；,（6）拥有老爷车的人养蜗牛；（7）拥有福特车的人住在黄房子里；,（8）住在中间房子里的人喝牛奶；（9）挪威人住在最左边房子里；,（10）拥有雪佛莱汽车的人与养狐狸的人是邻居；,（11）拥有福特汽车的人与养马的人是邻居；,（12）拥有奔驰汽车的人爱喝橙汁；（13）日本人开大众；,（14)挪威人的邻居住在兰房子里,房子,1,2,3,4,5,颜色,国籍,小车,饮料,宠物,（1）英国人住在红房子里；,20,（,1）英国人住在红房子里；,（2）西班牙人养狗；,（3）居住在绿房子里的人喜欢喝可乐；,（4）乌克兰人喜欢喝蛋酒；,（5）住在绿房子里的人是住在象牙色房子人的右邻；,（6）拥有老爷车的人养蜗牛；（7）拥有福特车的人住在黄房子里；,（8）住在中间房子里的人喝牛奶；（9）,挪威人住在最左边房子里；,（10）拥有雪佛莱汽车的人与养狐狸的人是邻居；,（11）拥有福特汽车的人与养马的人是邻居；,（12）拥有奔驰汽车的人爱喝橙汁；（13）日本人开大众；,（14)挪威人的邻居住在兰房子里,房子,1,2,3,4,5,颜色,国籍,挪威,小车,饮料,宠物,（1）英国人住在红房子里；,21,（,1）英国人住在红房子里；,（2）西班牙人养狗；,（3）居住在绿房子里的人喜欢喝可乐；,（4）乌克兰人喜欢喝蛋酒；,（5）住在绿房子里的人是住在象牙色房子人的右邻；,（6）拥有老爷车的人养蜗牛；（7）拥有福特车的人住在黄房子里；,（8）,住在中间房子里的人喝牛奶；,（9）,挪威人住在最左边房子里；,（10）拥有雪佛莱汽车的人与养狐狸的人是邻居；,（11）拥有福特汽车的人与养马的人是邻居；,（12）拥有奔驰汽车的人爱喝橙汁；（13）日本人开大众；,（14)挪威人的邻居住在蓝房子里,房子,1,2,3,4,5,颜色,国籍,挪威,小车,饮料,牛奶,宠物,（1）英国人住在红房子里；,22,（,1）英国人住在红房子里；,（2）西班牙人养狗；,（3）居住在绿房子里的人喜欢喝可乐；,（4）乌克兰人喜欢喝蛋酒；,（5）住在绿房子里的人是住在象牙色房子人的右邻；,（6）拥有老爷车的人养蜗牛；（7）拥有福特车的人住在黄房子里；,（8）,住在中间房子里的人喝牛奶；（9）挪威人住在最左边房子里；,（10）拥有雪佛莱汽车的人与养狐狸的人是邻居；,（11）拥有福特汽车的人与养马的人是邻居；,（12）拥有奔驰汽车的人爱喝橙汁；（13）日本人开大众；,（14),挪威人的邻居住在蓝房子里,房子,1,2,3,4,5,颜色,蓝色,国籍,挪威,小车,饮料,牛奶,宠物,红，绿，象牙，黄，蓝,（1）英国人住在红房子里；,23,（,1）英国人住在红房子里；,（2）西班牙人养狗；,（3）居住在绿房子里的人喜欢喝可乐；,（4）乌克兰人喜欢喝蛋酒；,（5）住在绿房子里的人是住在象牙色房子人的右邻；,（6）拥有老爷车的人养蜗牛；（7）拥有福特车的人住在黄房子里；,（8）,住在中间房子里的人喝牛奶；（9）挪威人住在最左边房子里；,（10）拥有雪佛莱汽车的人与养狐狸的人是邻居；,（11）拥有福特汽车的人与养马的人是邻居；,（12）拥有奔驰汽车的人爱喝橙汁；（13）日本人开大众；,（14),挪威人的邻居住在蓝房子里,房子,1,2,3,4,5,颜色,？,蓝色,国籍,挪威,小车,饮料,牛奶,宠物,红，绿，象牙，黄，蓝,（1）英国人住在红房子里；,24,（,1）,英国人住在红房子里；,（2）西班牙人养狗；,（3）居住在绿房子里的人喜欢喝可乐；,（4）乌克兰人喜欢喝蛋酒；,（5）,住在绿房子里的人是住在象牙色房子人的右邻；,（6）拥有老爷车的人养蜗牛；（7）拥有福特车的人住在黄房子里；,（8）,住在中间房子里的人喝牛奶；（9）挪威人住在最左边房子里；,（10）拥有雪佛莱汽车的人与养狐狸的人是邻居；,（11）拥有福特汽车的人与养马的人是邻居；,（12）拥有奔驰汽车的人爱喝橙汁；（13）日本人开大众；,（14),挪威人的邻居住在蓝房子里,房子,1,2,3,4,5,颜色,？,蓝色,国籍,挪威,小车,饮料,牛奶,宠物,红,，,绿,，,象牙,，黄，,蓝,（1）英国人住在红房子里；,25,（1）英国人住在红房子里；,（2）西班牙人养狗；,（3）居住在绿房子里的人喜欢喝可乐；,（4）乌克兰人喜欢喝蛋酒；,（5）住在绿房子里的人是住在象牙色房子人的右邻；,（6）拥有老爷车的人养蜗牛；（7）拥有福特车的人住在黄房子里；,（8）住在中间房子里的人喝牛奶；（9）挪威人住在最左边房子里；,（10）拥有雪佛莱汽车的人与养狐狸的人是邻居；,（11）拥有福特汽车的人与养马的人是邻居；,（12）拥有奔驰汽车的人爱喝橙汁；（13）日本人开大众；,（14),挪威人的邻居住在蓝房子里,房子,1,2,3,4,5,颜色,黄色,蓝色,国籍,挪威,小车,饮料,牛奶,宠物,红,，,绿,，,象牙,，黄，,蓝,（1）英国人住在红房子里；,26