PDF《科别：数学科》

科别:数学科 组别:高中组 作品名称:猫捉老鼠的秘密 关键词:猫捉老鼠游戏、尤拉公式、平面图 编号:040409 学校名称: 国立花莲女子高级中学 作者姓名: 邱玮婷、吴思慧 指导老师: 邱俊良、黄光骘 摘要 本文探讨了特定问题的组合最佳化,所谓组合最佳化就是在共同限制及相互 影响下,来求得最佳解.

一个组合最佳化问题的困难,往往是由於其庞大的 解空间所致.本文介绍了猫抓老鼠问题的组合最佳化,并在第一步中,以归 纳法解决了一个较简单的例子.经由我们归纳的结果,我们一共得到了五个 证明,来推广每个顶点相等通道的一般性,并且得到了四个相等通道问题所 应该有的性质,之后我们又用了二个证明,推广在完全对称下所需的结果. 第二步中,我们又用了四个证明,将问题推广到每个顶点不相等通道的问题, 并且以二个不等通道的例,阐释了我们所得的结果.我们所得到的结果, 能有效的解决解空间不大的某些特定问题,尤其是以人工来解决问题时,提 供了一个绝佳的途径.然而当解空间变得较大且边数不等时,即使有不错的 结果,问题也会变的非常的复杂.我们在特例探讨上,解释了即使是单纯且 限制了许多条件的问题,要证明一般性也不是这样容易,所以当问题变大时, 我们改以组合最佳化的最佳解逼近来取代求最佳解,而不直接求最佳解. 一个好的最佳解逼近就是在可接受的时间围内,求得逼近最佳解.当然我 们仍能以暴力法则求得最佳解,但时间围是我们所不能接受的,故在此不 予讨论. 壹、研究动机 在一次偶然的机会里,我们看到一种叫做「猫抓老鼠」的游戏.这个游戏在一张 纸上画了

20 间房间,每间房间里各养一只猫,房间之间有通道相连,猫咪可以相互 跑来跑去.现在主人想抓

10 只老鼠放进去,可是每间房间只能养一只猫或老鼠,所 以必须抓

10 只猫出来.我们知道猫会吃老鼠,所以猫咪和老鼠之间的通道必须是关

1 闭的,请问主人应该怎麽做,在关闭最少的通道下把老鼠放进去? 当我们见到这问题时,我们直觉想到可以用高一教的归纳法[1]来找到规律,再 从规律来探讨一般式 , 我们同时也想到可以用几何学下册[2] [3]教的尤拉公式与多面 体来探讨,因为课本教了我们如何将正多面体挖一个洞摊在平面上,让平面图也符 合尤拉公式.这虽然只是个小游戏,但却蕴含著极为有趣的数学概念.我们藉著这 次科展的机会,深入探讨这个问题. 图1贰、研究目的 假设有 n 间房间,每个房间各养一只猫,房间与房间之间有的相通,有的不相 通,我们要抓 k 只猫出去,并放进 k 只老鼠.游戏规则为: 1. 每个房间只能住一只猫或老鼠;

2. 猫会吃老鼠,因此若猫和老鼠的房间相通,那麽就要关闭通道. 问题:若要养 k 只老鼠进去,其中

2 n k ≤ ,请问要抓哪些猫出去,使得需要被封闭的 通道最少? 以下我们讨论这个组合最佳化的问题. 参、研究设备及器材 纸、笔、个人电脑、Matlab 6.

5、Visual C++ 6.0 肆、研究过程或方法

一、 定义及名词解释 1. 我们以 表示 n 间房间的状态,其中 .令S为所有解所成集合,显然 S 有 个元素.令函数 为由解空间 S 映至 正整数的函数,代表一组解所需关闭的通道数.我们称两组不同的解 ] ,..., [

1 n s s s = ? ? ? ? + = 个房间为老鼠 若第 个房间为猫 若第 i ,