一类极小极大问题的滤子算法的任务书.docx

一类极小极大问题的滤子算法的任务书
任务书
一类极小极大问题的滤子算法
一、任务背景
极小极大问题（minimaxproblem）是指在一个两人对弈的游戏中，一个人的最优策略使另一个人的最劣策略得到最优化，即找到对手最优策略下自己的最劣策略。这类问题广泛存在于博弈论、优化计算等领域中。
滤子算法是解决极小极大问题的一种常见方法，其主要思想是通过剪枝策略，使得搜索范围缩小，从而达到快速解决问题的目的。
二、任务要求
本项目要求编写一种滤子算法，解决以下极小极大问题：
假设有两个集合A和B，A中有n个正整数，B中有m个正整数。玩家1从集合A中选取一个数，玩家2从集合B中选取一个数，两个选出的数相加得到一个点数，记为S。若S≤t，玩家1得分为S，玩家2得分为0；若S>t，玩家1得分为0，玩家2得分为S。求玩家1的最优得分和相应策略。
具体要求：
1.实现一个滤子算法，用于求解以上问题。
2.通过编写测试程序，测试所实现的滤子算法的正确性和运行效率，并对比其他极小极大算法的性能表现。
3.编写报告，包括算法设计思路、测试程序等详细内容。
三、参考资料
1.Nim游戏的搜索与评估算法，吕建峰，南开大学学报（自然科学版），2003。
2.极大极小搜索算法在个向量三维模型三视图布局问题的应用，袁利平，大学物理实验（中）、（下），2004。
3.常用搜索算法在游戏策略中的应用研究，李瑞华，数学学报，2005。
4.游戏树搜索技术及其应用，解人庆，计算机学报，2008。
五、备注
本项目难度较高，需要具备扎实的算法功底和编程实践经验，建议操作者结合实际情况进行调整。