过河问题.ppt

问题：人，狗，鸡，米均要过河，船需要人划，另外至多,当人不在时，狗要吃鸡，鸡要吃米当一,例如向量(1,0,1,0),人狗鸡米过河问题,还能载一物鸡、米怎样安全过河？,物在南岸时，相应分量记为1，否则记为0表示人和鸡在南岸，狗和米在北岸，称为状态向量问人、狗、,将人、狗、鸡、米依次用四维向量中的四个分量表示，,机动 上页 下页 返回 结束,机动 上页 下页 返回 结束,1. 穷举法模型,由问题中的限制条件，有些状态是允许的，有些是不允许的.,船的一次运载也用向量表示,当一物在船上时相应分量记为1,,例如(1,1,0,0)表示人和狗在船上，即人带狗过河凡系统可以允许存在的状态称为可取状态所有可取状态向量为,下边5个状态正好是上边5个的相反状态否则记为0本系统的运算向量共有四个：,(1,0,1,0)、(1,1,0,0)、(1,0,0,1)、(1,0,0,0),0+0=0 , 1+0=0+1=1 , 1+1=0 一次过河就是一状态向量和一运算向量的二进制加法，即,渡河过程就是由(1,1,1,1)经过加法运算后到另一可取状态,,经过奇数次加法运算,最后到达(0,0,0,0) 状态。

总共,,机动 上页 下页 返回 结束,作法如下：（×表示不可取状态， ××为重复的可取状态）,①,,②,,③,,④,,④',,⑤,,,机动 上页 下页 返回 结束,⑤',,⑥,,⑦,,已出现状态(0,0,0,0),,说明经过7次运算，,人、狗、鸡、米已安全过河这种方法的优点在于使用计算机能求出所有转移过程，并比,较出最优者求出最优解另外，人、狗、鸡、米问题还可以用图论的方法求解机动 上页 下页 返回 结束,2. 图解法模型,将本系统的10个可取状态用10个点表示，,当且仅当可取状态A,经过某一运算向量后为可取状态B，就从A点向B点连一条线，,这样构成了一个图G,,,,,,,,,,,图G,从点(1,1,1,1)到(0,0,0,0)的最短路就是一个最优解.,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,共有两个最优解,,机动 上页 下页 返回 结束,§7 围棋中的数学模型,围棋是一项智力性很强的棋类项目，其起源说法很多，,关于,围棋棋盘的边数设置及胜负贴目规定也一直随着人们对围棋认,识的不断深入而逐渐变更着，,现在的围棋棋盘虽已确定每边19,道，,胜负贴目也基本有所公论，,但终缺一个令人信服的说明或,证明。

一、分析,问题：,方形棋盘每边设计多少道,线才是最佳的？,先手帖后手多少目才最为合理？,下围棋最先考虑的还是棋块的死活问题，,首先应考虑棋块在,哪一线成活速度最快，,即用最少的点来得到活棋定义 一棋块虽不是成活型棋块，,但当对方进攻此棋块时，,总可,以通过正确应对而最终成为活棋，则此块棋称为准活型棋块现在的棋盘是否还会变化？,,机动 上页 下页 返回 结束,准活型的概念显然有其现实意义因为开局时，对弈棋手双,方只是把棋走成大致的活型，,而并非耗费子力去真正把棋块做,成活型例如二、三、四线边线棋子形成准活型棋块所用最少子如下,用Ni（i为正自然数）表示第i线形成准活型所用的最少子数，,从上图看出,三线较二线、四线的成活速度要快，,容易验证，五线、六线,等其他线成准活型的速度也要慢于三线，,即,,因此,三线能最快成活，它是围棋盘上重要的一线机动 上页 下页 返回 结束,二、棋盘模型的建立,首先对围棋棋子的价值给出数学描述定义2,对于一块成活型棋块，用它的棋子数去除这些棋子所包,得到的商值称为此棋块的目效率，记为PE目效率表示单位棋子所占的目数，,即表示此棋块平均占有目,下面利用此概念对围棋棋盘问题建立模型。

围棋的棋盘由古时的每边11道增至现在的每边19道，,其间历,这种进化过程也显示着人们的认识逐渐接近真理含的目数，,数的能力经数千年围棋内部存在两种抗衡的力量，使先手即使先落子也无法取得,多大优势，,因此古人在不贴子的情形下仍可公平对弈围棋的攻守（攻为欲杀死对方，守为不被对方杀死）是不同,于其他棋类的比如象棋，必须进攻吃掉对方的将（或帅）才,算赢而围棋是比谁占的地盘大，可以不吃或少吃对方的子，,最后谁占的地盘大谁赢机动 上页 下页 返回 结束,首先，我们把围棋棋盘分为边部和中腹两个区域从做活和,边部因空间受阻而易受攻击，,占地两个方面看，,但可利用边部,成目快的特点迅速做活，,有根据地后再图发展而中腹则由于,四方皆可发展，不容易受到攻击，但做活比较困难前面已经指出三线有控制边,那么控制中腹的重,任无疑就落到了紧邻的四线上假设对弈双方一方控制三线，,另一方控制四线部的优势，,对于x =19线,棋盘图形如右设三、四线点,组成的棋块目效率分别为,PE3 , PE4 则数学模型为,,机动 上页 下页 返回 结束,,三、棋盘模型求解,设三线围成的边及四线围成的中腹都已成为实空，,对方无法,在其中做活。

则所有三线围成的目数为 8x -16 ,,由四线围成中腹的目数为,,,,∴E(x) 单调增加，,,,,方程 E(x)=0 至多有一个解模型,,机动 上页 下页 返回 结束,,,,由闭区间上连续函数的零点定理，方程 E(x)=0 在 (18,19) 有一,个解,,而且此唯一解非整数∴ 此模型的最优整数解为 x =19 这说明围棋盘设计为每边 19 线是合理的这是第一个问题的答案下面回答第二个问题：,问题二：先手帖后手多少目才最为合理？,模型,,机动 上页 下页 返回 结束,四. 胜负帖目的估计,围棋是一项竞技活动，从公平的意义上讲，,弈棋双方如果水,平棋力严格相同的话（尽管这在实际中不可能）,无论谁先手,下棋，其结果都是两方占地相同因此围棋对弈应该有和棋,,(实际比赛中几乎没有和棋)对围棋最终的结局必须有明确合,理的规定——先手贴后手几目——以保证弈棋双方的平等地位下面利用目效率对胜负贴目的可能目数做一估算19×19 的围棋棋盘中三线与四线的地位几乎相同，,即三线点,占边部实空与四线点占中腹实空的目效率近似相等当一方抢,占边角（三线点）时，另一方可用占中腹（四线点）相对抗。

从数学的角度抽象地看，目效率的概念也可使我们摆脱棋盘的,束缚，,不必考虑三、四线点数目的不同以及它们在特定棋盘上,的位置差异，,而把围棋直接视为三线点与四线点的阵营对抗由于四线点的目效率比三线点的目效率略高约0.09，,故假设先手,（前面已算出 x =19）,,机动 上页 下页 返回 结束,一方挑选四线而占之，,后手因为有足够的贴目补充抵消三线与,四线的差异而从容地在三线应之，,目效率对双方不偏不倚现,在的问题是：先手需贴后手多少目才可平衡这微小差异？,三线,点、四线点设置仍如,前面的图再设四线需贴三线 y目棋，,由双方目效率相等的原则，有,则三线的目效率应该为,四线的目效率是,,即先手终局时需贴出5.2目因为目的最小单位是0.5 ，故取5.5目,,这与前些年中国贴,子及日本贴5目半的胜负规则比较接近机动 上页 下页 返回 结束,五. 模型的改进,我们的模型应是客观地建立在围棋本身的规则或规律上，,关于,围棋本质性的东西还有待进一步认识对以上的推理和计算我们,还可做以下改进我们考查,前面图,中的四个三三点与四个四四点（即星位）,,发现它们对围空并未起什么作用，,去掉它们后三线与四线点依,然连成一体成空地，故这些点对成目不起作用，,而只能算官子，,或防止对方切断的一手。

因此在前面模型中的目效率应改为,,,的最优整数解还是,x =19.,即围棋棋盘的最优道数还是 19我们再来看胜负贴目的估算，是否有所改变机动 上页 下页 返回 结束,此时在胜负贴目的估算中目效率变为,方程变为,解变为,即先手终局时需贴出7目这与现行中国规则贴7目半相当接近，,与应氏规则贴8点也比较接近机动 上页 返回 结束,作业,习题二. 2 ，3,。