【摘要】：很多搜索问题都可以转化为图搜索问题。如何通过这个图找出一条从初始状态到目标状态的路径，就是图搜索问题。为了提高搜索效率，图搜索并不是先生成所有状态的连接图再进行搜索，而是边搜索边生成图，直到找到一个符合条件的解，即路径为止。在搜索的过程中，生成的无用状态越少，即非路径上的状态越少，搜索的效率就越高，所对应的搜索策略就越好。
很多搜索问题都可以转化为图搜索问题。比如传教士与野人问题：有3个传教士和3个野人来到河边准备渡河，河岸有一条船，每次至多可供2人乘渡。为了安全起见，传教士应如何规划摆渡方案，使任何时刻在河的两岸以及船上的野人数目总是不超过传教士的数目（但允许在河的某一岸或者船上只有野人而没有传教士）。
假设初始状态传教士、野人和船均在河的左岸，目标是在满足问题的约束条件下到达河的右岸。如果用在河的左岸的传教士、野人人数以及船是否在左岸表示一个状态，则该问题任何时刻的状态都可以用一个三元组表示（M，C，B），其中M、C分别表示在左岸的传教士、野人人数，B表示船是否在左岸，B＝1表示船在左岸，B＝0表示船在右岸。则该问题的初始状态为（3，3，1），目标状态为（0，0，0）。所有满足约束条件的状态之间，构成了如图4－1所示的状态图。
如何通过这个图找出一条从初始状态（3，3，1）到目标状态（0，0，0）的路径，就是图搜索问题。所谓的路径，就是给出一个状态序列，序列的第一个状态是初始状态，最后一个状态是目标状态，序列中任意两个相邻的状态之间通过一个连线连接。 为了提高搜索效率，图搜索并不是先生成所有状态的连接图再进行搜索，而是边搜索边生成图，直到找到一个符合条件的解，即路径为止。在搜索的过程中，生成的无用状态越少，即非路径上的状态越少，搜索的效率就越高，所对应的搜索策略就越好。(www.xing528.com)
图4-1 传教士与野人问题状态图
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
