极小极大问题的束方法算法的开题报告.docx

极小极大问题的束方法算法的开题报告
一、选题背景和意义
极小极大问题是指在一组可行解中，寻找一组使得问题得到的值最小，但在这组最小值中，选择使得该最小值最大的解。它在实际生产和生活中具有重要的应用，如负载平衡问题、博弈论、网络流量控制等，是一类典型的优化问题。
束方法是一种广泛应用于优化问题的算法，在求解具有约束的非线性优化问题、非线性函数最小化、非线性规划等问题中都得到了广泛应用。束方法以约束条件为依据，将全部可行解求出，并用一个约束子集表示这些可行解。然后在这个约束子集内进行优化求解，更适合于求解带有约束条件的非线性优化问题。
本文旨在探讨束方法在极小极大问题中的应用，通过研究束方法的理论原理和实现方法，将其运用到极小极大问题中，提高该类问题的求解效率。
二、研究内容和技术路线
1.研究束方法的理论原理和实现方法，了解其优点和局限性。
2.研究极小极大问题的数学模型和约束条件，并运用束方法对其求解。
3.通过编写计算机程序，对比束方法与其他求解方法在极小极大问题上的效率和精度。
4.对实验结果进行分析和总结，并给出有关结论和建议。
技术路线：
1.收集相关文献资料，梳理理论体系。
2.确定极小极大问题的数学模型和约束条件。
3.实现束方法求解极小极大问题的算法。
4.编写可视化计算程序，比较不同算法的效率和精度。
5.实验结果分析和总结，给出结论和建议。
三、预期成果及创新点
1.基于束方法求解极小极大问题的计算机算法和程序，具有一定实用价值。
2.对比不同求解方法在极小极大问题中的优缺点，提出相应的改进建议。
3.深入研究束方法在优化问题中的应用，对算法设计和应用提出一些新的思路和方法。
四、进度安排
1.前期阅读相关文献，梳理理论框架，确定研究方向和方法。【1-2周】
2.研究极小极大问题的数学模型和约束条件，构建计算模型。【3-4周】
3.设计并实现基于束方法的算法，利用计算机程序进行实验验证。【5-6周】
4.分析实验结果，总结方法优点、缺陷及改进的启示。【7-8周】
5.完成论文的撰写和修改。【9-10周】
五、注重的问题
1.要对比不同求解方法的精度和效率，需要对数据进行统计分析和计算，要求较强的大数据处理能力。
2.要求对算法设计和优化问题有一定的数学背景，对计算机编程也要求熟练。
3.需要花费大量的时间阅读相关文献，对于自学能力和文献研读能力要求较高。
六、参考文献
[1]刘洁,樊琰,于洋.求解极小极大问题的几种方法及比较[J].实验技术与管理,2018,(1):167-172.
[2]J.Barber.“TheUseofBundleMethodsinGlobalOptimization”,Ph.D.Dissertation,UniversityofFlorida,Gainesville,FL,1999.
[3]H.Wolkowicz,R.Saigal,andL.Vandenberghe,HandbookofSemidefiniteProgramming,Boston:KluwerAcademicPublishers,pp.267–307,2000.