三角网格模型最短路径并行算法的研究与实现的任务书.docx

三角网格模型最短路径并行算法的研究与实现的任务书
一、任务背景
三角网格是计算机图形学中常用的三维模型表示方法之一，广泛应用于计算机辅助设计、三维动画和游戏等领域。在三角网格模型中，各个三角形之间的关系极为复杂，因此如何高效地计算三角网格模型的最短路径是一个重要的问题。
在传统的串行算法中，最短路径常常需要进行大量的计算和迭代，导致算法时间复杂度较高，不能满足实际应用的需要。因此，研究和实现三角网格模型最短路径的并行算法具有重要意义，可以充分发挥多核并行处理器的优势，提高算法的效率和性能。本次任务旨在研究和实现三角网格模型最短路径并行算法，提高计算效率和质量。
二、任务内容
1.研究三角网格模型最短路径的串行算法，分析其时间和空间复杂度；
2.研究三角网格模型最短路径的并行算法，并设计合适的并行计算模型；
3.实现三角网格模型最短路径并行算法的程序，并进行调试和测试；
4.通过对比实验和性能测试，评估并行算法的效率和性能，并进行优化和改进；
5.编写报告，对三角网格模型最短路径并行算法的研究和实现进行总结和归纳。
三、任务要求
1.具有计算机科学、数学和图形学等相关专业的基础知识和理论背景，熟悉并行计算和算法设计相关知识；
2.熟悉C/C++编程语言和并行编程技术，具有一定的编程能力和实践经验；
3.具有较强的分析、设计和问题解决能力，能够独立思考和解决问题；
4.具备良好的团队合作精神和沟通能力，能够与他人协作完成任务。
四、任务时间
本次任务为期两个月，具体时间为2021年6月1日至2021年7月31日。任务执行期间需保持良好的工作记录和进度，每周至少提交一次工作报告，并及时沟通和反馈工作进展。
五、任务成果
1.三角网格模型最短路径并行算法的研究和实现报告，不少于文字5000字；
2.程序代码和文档，包括详细的算法设计和实现说明、输入输出格式和数据等；
3.实验数据和结果，包括验证算法正确性和评估算法效率和性能的实验数据和结果；
4.其他相关材料，包括演示文稿、PPT和演示视频等。
六、参考文献
[1]DiBattistaG,EadesP,TamassiaR,etal.Algorithmsfordrawinggraphs:anannotatedbibliography[J].ComputGeom,1994,4(5):235-282.
[2]EppsteinD,MumfordE.Fastheuristicsforgeometricalshortest-pathqueries[J].DiscreteAppliedMathematics,1998,86(1):81-92.
[3]HanY,XiaoB.ParallelalgorithmsforshortestgeometricpathswithapplicationstoVLSIdesign[J].JournalofParallelandDistributedComputing,2003,63(1):70-83.