6.0.1 事件驱动模拟
Robert Sedgewick Kevin Wayne
我们的第一个示例是一个基础的科学应用:按照弹性碰撞的原理模拟粒子系统的运动。科学家通过这个系统可以理解和预测物理系统的性质。这个模型可以模拟气体中分子的运动、化学反应的动态过程、原子扩散、最密堆积问题(sphere packing)、行星的环的稳定性、某些元素的相变、一维自引力体系前向阵面传播技术等许多问题。它可应用的范围从分子运动中的微小亚原子粒子到天体物理学中巨大的星体对象。
讨论这个问题需要一些高中物理知识、一些软件工程的知识和一些算法知识。我们把大部分和物理有关的内容留作练习,而主要关注使用基础的算法工具(基于堆的优先队列),以处理它的一个实际应用,将不可能的计算变为可能。
6.0.1.1 刚性球体模型
首先介绍一个理想模型,它描述的是原子和分子在含有以下性质的容器中的运动:
运动的粒子与墙以及互相之间的碰撞是弹性的;
每个粒子都是一个已知位置、速度、质量和直径的球体;
不存在其他外力。
这个简单的模型在统计力学这个既与宏观现象(例如温度和压力)有关又与微观现象(例如单个原子和分子的运动)有关的学科中十分重要。麦克斯韦和玻尔兹曼使用这个模型得到了由温度的函数表示的相互碰撞的分子的速度分布,爱因斯坦用这个模型解释了花粉颗粒在水中的布朗运动。不存在其他外力的假设意味着粒子在碰撞之前是在做匀速直线运动。我们也可以通过添加其他作用力来扩展这个模型。例如,如果加上摩擦力和自旋,那就可以更加准确地描述一些熟悉的物理运动,例如台球桌上的台球。
公开
同步至部落
取消
完成
0/2000
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
![](https://static001.geekbang.org/resource/image/d0/e4/d0880927e2a522a038be2d04bf19dfe4.png)
基于弹性碰撞原理的粒子系统模拟方法是一种重要的科学应用,本文介绍了时间驱动模拟和事件驱动模拟两种方法。时间驱动模拟需要计算所有粒子在未来时间点的位置和速度,而事件驱动模拟则关注下一次碰撞的时间点,使用优先队列记录所有事件。文章还介绍了碰撞预测的方法,通过粒子的速度来识别潜在的碰撞。此外,还讨论了排除无效事件的方法,以及粒子数据类型的实现要点。通过简洁的语言和清晰的示例,帮助读者了解了事件驱动模拟的基本原理和应用。事件驱动模拟已经被应用于无数需要对运动中的物理对象建模的其他领域,例如分子学、天体物理学和机器人技术。这些应用可能会用其他实体,或是三维空间,或是其他作用力等许多种方法扩展这个模型。每种扩展都会为计算带来新的挑战。模拟在科学和工程的各个领域都是帮助研究者理解自然世界中各种性质的重要工具。它的应用从制造业、生物学、金融领域到复杂的工程结构,数不胜数。对于它们其中的一大部分应用,基于堆的优先队列数据类型或是高效的排序算法能够使模拟的质量和范围大有改观。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《算法(第 4 版)》
《算法(第 4 版)》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示,欢迎踊跃留言。
收起评论