第三章与或图搜索问题-问题归约法3.0 引言l归约(Reduction)例1 问题1：现有煤气灶、水龙头、水壶和火柴，你怎样烧水？答：向水壶中注满水，把水壶放在煤气灶上，擦火柴点燃煤气灶。问题2：问题1中其他情况不变，只是水壶中已经灌满了水，你怎样烧水？答：把水壶放在煤气灶上，擦火柴点燃煤气灶或擦火柴点燃煤气灶，把水壶放在煤气灶上。例2 在边长为2的正方形内，任意放置5个点，求证其中必存在两个点，它们之间的距离不大于2。.问题可转化为：.在四个单位正方形内，.任意放置5个点，至少.有两个点在同一正方形内。IIIII123I例3假定我们已经会求矩形的面积，现在要求如图所示的五边形的面积。求解步骤：求五边形面积求 1面积求 2面积求 3面积求 I面积求 II面积求 III面积求面积求面积求面积123IIIIIIl本原问题可直接得到答案的问题称为本原问题l例1中的原始的烧水问题l例2中根据鸽巢原理直接可回答的问题l例3中求矩形面积的问题l归约法把原问题转化(分解)为一个或几个子问题，对子问题再归约，直至成为可以直接求解的本原问题。3.1问题空间及与或图表示l梵塔难题的两种解法状态空间法l初始
