高中信息技术 浙教版选修5 3.2Prolog的工作机理(共13张PPT)

Prolog的工作机理 1 匹配与回溯方法 1.实例化 Prolog中称无值的变量为自由变量，有值的变量为约束变量。一个 变量取了某值就说该变量约束于某值，或者说该变量被某值实例化了。 例：mother(Who1,xiaoming).在Who1有值以前，它是自由变量， 如果(Who1=xiaozhang)，那么我们就说变量Who1约束于xiaozhang，或说Who1被xiaozhang实例化了。 2.匹配 如果两个谓词的名相同，参数的个数和类型对应相同，并且对应参数满足下面的条件之一，那么这两个谓词可以匹配(match)。 （1）如果两者都是常量，则必须完全相同。 （2）如果两者都是约束变量，则两个约束值必须相同。 （3）如果其中一个是常量，一个是约束变量则约束值与常量必须相同。 （4）当两者至少有一个是自由变量。 3 其实匹配是一种操作，这种操作为参加匹配的自由变量和常量，或者两个自由变量建立一种对应关系，将常量作为对应变量的约束值，使两个对应的自由变量始终保持一致。如果其中一个被某值实例化，那么另一个也被同一值实例化；反过来说，如果其中一个被解除约束，则另一个值的约束也被解除。 上面例子中每对谓词均可以匹配。对于含有自由变量的谓词表示，如Bame(X)，它与game(xijizhengba).匹配的结果是自由变量X被常量xijizhengba实例化。再如color(Y)与color(Z)，匹配的结果是，当自由变量Y和Z中的一个被某值约束，如Y被apple实例化，则Z也被apple实例化。 4 3.回溯 大家可能玩过走迷宫的游戏，在走迷官的过程中，我们就经常用到回溯。让我们通过个走迷官的例子来解释回溯这个概念。 迷宫如图所示，迷宫的左下角有一只的猴子，它想吃到迷宫右上角的香蕉。下面的图记录了猴子找到香蕉的过程。 5 在这里画的几幅图是搜索与回溯过程的示例。 由这组示意图可以看出，猴子通过搜索（例如按左手法则，沿左边的阻挡墙前进）和回溯（在碰壁时往回退）来完成寻找香蕉的过程。图中带有箭头的黑线是搜索路线，红色带箭头的线是回溯路线。 在Prolog中，回溯是在程序目标确定后，Prolog就会从上到下，从左到右地在程序中搜索能匹配的事