狮子过河问题.ppt

狮子过河问题 一个忆起但不全的例子 问题 有三对母子狮子Aa、Bb与Cc，其中ABC为母狮，abc为小狮。要过一条河，河边只有一条船，狮子自己划船，船每次只能载两只狮子。 生存准则：一只小狮如果没有母亲的保护，则会被其它母狮吃掉。母狮之间、小狮之间是安全的。 问题：如何安全过河？ 狮子数字化 对6只狮子进行编码： 0：A 1：a 2：B 3：b 4：C 5：c 状态数字化 将每只狮子是否已过河以及船的位置做为划船前后的一个状态。 每只狮子的状态：0：未过河/此岸，1：已过河/对岸。 船的状态：0：此岸，1：对岸。 使用数组[7]，有7个元素，每个取值0或1，映射某一时刻的总状态。依次为A、a、B、b、C、c、船。 状态作用 可以计算安全性。 状态集共有7个元素，每个有2个取值，故状态总数为27 = 128 ，它是有限的。 初始状态：所有元素为0。 结束状态：所有元素为1。 问题演变为：找到一个状态变化序列，使得能从初始态到结束态？相邻的状态变化符合划船要求。 动作数字化 动作：每次划船动作，或状态之间的演变方式，即参与划船的狮子编号。由于最多两只狮子过河，故用两个数来表示过河的狮子号码，当两个数相等时表示只有一个狮子过河。 为避免重复动作，实际动作时要求第2数=第1数。 动作顺序：00、01、02、03、04、05、11、12、13、14、15、22、23、24、25、33、34、35、44、45、55。 动作初始化：0与-1。 历史跟踪 历史：对从初始状态到当前状态的状态序列以及每次划船的动作进行跟踪。 历史是不能重演的。 历史是可以回溯的，当历史无路可走时，允许历史回到过去，选择新的动作，继续历史的演变。 历史记录 由于最多只有128个状态，故历史最多只有128深。 历史使用数组记录。 状态本身也使用数组。 状态的历史使用二维数组，第一维表历史，第二维表状态与动作。 变量定义 int a[128][9]; 第一维[128]表历史，最深128步。 第二维的[0]~[5]表狮子状态，[6]表船的位置，[7]~[8]表到下一状态采取的动作。 int curr; 当前历史位置，即a数组第一维从0演变到curr。 初始化 a[0][0] ~ a[0][6]取值0。初始状态。 a[0][7]=0,a[0][8]=-1第一步动作的前期。 curr=0;当前为第一步。 * * * * *