阳光精品论坛 >> 『 CFD 专栏 』 >> 介绍方程离散化的经典文章

本主题已阅读1800次,回复0 篇

作者 | 本页主题： 介绍方程离散化的经典文章

even2004      信息：  来自：未填  发贴：1239 贴  积分：244 点 货币：5814 阳光币 注册时间：2008/12/31  资料 好友 消息 引用回复 选择字号91011121415161820253050 介绍方程离散化的经典文章 如果说今年这时候OIBH问得最多的问题是二分图，那么去年这时候问得最多的算是离散化了。对于“什么是离散化”，搜索帖子你会发现有各种说法，比如“排序后处理”、“对坐标的近似处理”等等。哪个是对的呢？哪个都对。关键在于，这需要一些例子和不少的讲解才能完全解释清楚。       离散化是程序设计中一个非常常用的技巧，它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中“只考虑我需要用的值”。下面我将用三个例子说明，如何运用离散化改进一个低效的，甚至根本不可能实现的算法。     《算法艺术与信息学竞赛》中的计算几何部分，黄亮举了一个经典的例子，我认为很适合用来介绍离散化思想。这个问题是UVA10173(http://acm.uva.es/p/v101/10173.html)，题目意思很简单，给定平面上n个点的坐标，求能够覆盖所有这些点的最小矩形面积。这个问题难就难在，这个矩形可以倾斜放置（边不必平行于坐标轴）。       这里的倾斜放置很不好处理，因为我们不知道这个矩形最终会倾斜多少度。假设我们知道这个矩形的倾角是α，那么答案就很简单了：矩形面积最小时四条边一定都挨着某个点。也就是说，四条边的斜率已经都知道了的话，只需要让这些边从外面不断逼近这个点集直到碰到了某个点。你不必知道这个具体应该怎么实现，只需要理解这可以通过某种方法计算出来，毕竟我们的重点在下面的过程。     我们的算法很显然了：枚举矩形的倾角，对于每一个倾角，我们都能计算出最小的矩形面积，最后取一个最小值。     这个算法是否是正确的呢？我们不能说它是否正确，因为它根本不可能实现。矩形的倾角是一个实数，它有无数种可能，你永远不可能枚举每一种情况。我们说，矩形的倾角是一个“连续的”变量，它是我们无法枚举这个倾角的根本原因。我们需要一种方法，把这个“连续的”变量变成一个一个的值，变成一个“离散的”变量。这个过程也就是所谓的离散化。       我们可以证明，最小面积的矩形不但要求四条边上都有一个点，而且还要求至少一条边上有两个或两个以上的点。试想，如果每条边上都只有一个点，则我们总可以把这个矩形旋转一点使得这个矩形变“松”，从而有余地得到更小的矩形。于是我们发现，矩形的某条边的斜率必然与某两点的连线相同。如果我们计算出了所有过两点的直线的倾角，那么α的取值只有可能是这些倾角或它减去90度后的角（直线按“”方向倾斜时）这么C(n,2)种。我们说，这个“倾角”已经被我们 “离散化”了。虽然这个算法仍然有优化的余地，但此时我们已经达到了本文开头所说的目的。       对于某些坐标虽然已经是整数（已经是离散的了）但范围极大的问题，我们也可以用离散化的思想缩小这个规模。最近搞模拟赛Vijos似乎火了一把，我就拿两道Vijos的题开刀。       VOJ1056(http://www.vijos.cn/Problem_Show.asp?id=1056) 永远是离散化的经典问题。大意是给定平面上的n个矩形（坐标为整数，矩形与矩形之间可能有重叠的部分），求其覆盖的总面积。平常的想法就是开一个与二维坐标规模相当的二维Boolean数组模拟矩形的“覆盖”（把矩形所在的位置填上True）。可惜这个想法在这里有些问题，因为这个题目中坐标范围相当大（坐标范围为-10^8到10^8之间的整数）。但我们发现，矩形的数量n<=100远远小于坐标范围。每个矩形会在横纵坐标上各“使用”两个值， 100个矩形的坐标也不过用了-10^8到10^8之间的200个值。也就是说，实际有用的值其实只有这么几个。这些值将作为新的坐标值重新划分整个平面，省去中间的若干坐标值没有影响。我们可以将坐标范围“离散化”到1到200之间的数，于是一个200*200的二维数组就足够了。实现方法正如本文开头所说的“排序后处理”。对横坐标（或纵坐标）进行一次排序并映射为1到2n的整数，同时记录新坐标的每两个相邻坐标之间在离散化前实际的距离是多少。这道题同样有优化的余地。       最后简单讲一下计算几何以外的一个运用实例（实质仍然是坐标的离散）。才考的VOJ1238(http://www.vijos.cn/Problem_Show.asp?id=1238)中，标程开了一个与时间范围一样大的数组来储存时间段的位置。这种方法在空间上来看十分危险。一旦时间取值范围再大一点，盲目的空间开销将导致Memory Limit Exceeded。我们完全可以采用离散化避免这种情况。我们对所有给出的时间坐标进行一次排序，然后同样用时间段的开始点和结束点来计算每个时刻的游戏数，只是一次性加的经验值数将乘以排序后这两个相邻时间点的实际差。这样，一个1..n的数组就足够了。      离散化的应用相当广泛，以后你会看到还有很多其它的用途。 编辑 |  发表于 2010/06/18/08:34  |  1 层  进入评分

推荐给朋友 可打印版本 文章模式

论坛跳转： 论坛跳至≡ 论坛管理 ≡ |- 『 论坛版务 』 |- 『 公告栏 』≡ 电脑及网络技术 ≡ |- 『 应用软件 网络技术 』 |- 『 硬件家园 』 |- 『 人才交流 』 ≡ 专业技术讨论区 ≡ |- 『 CAD 专栏 』 |- 『 CAM 专栏 』  |- 『 CAE 专栏 』 |- 『 CFD 专栏 』 |- 『 模具设计 逆向工程 』 |- 『 设计精品欣赏 』≡ 会员区 ≡ |- 『 软件上传与下载 』 |- 『 软件预览 0day介绍 』 |- 『 软件安装及求助 』≡ 休闲一刻 ≡ |- 『 网事闲谈 』 |- 『 文学苑 』 |- 『 美丽贴图 』 |- 『 游戏园地 』≡ 违规处理区 ≡ |- 『 回收站 』

快速回复

文章内容： HTML 代码不可用 关闭BMB Code 关闭Emot Code BMB代码选项： [img] - 开启 [flash] - 开启 [size] - 开启 上传附件[还可传0个]: 开启 最大字节: 200000 字节 最少发帖: 20 篇 标题: 签名 自动URL 动作 动作招呼欢迎灌水无聊负责生气高兴鼓掌等待反对浪漫不要找死去死狂笑傻笑痛哭道别跳舞唱歌害羞比酷救命狂妄拳击我踢我踩饶命眨眼臭美变态拼酒深情恶心惊讶抽烟怀疑拉勾经典同意ＯＫkiss生日晕倒气你错啦加油恭喜简单鼓励过奖原谅大笑考虑感动叹气道谢摇头拥抱无奈   [使用 Ctrl+Enter 直接提交贴子] 你的用户名：  你的密码： 忘了密码? 有效文件类型：---------jpggifziprarpngaceisocgiaspswftxtbmp

阳光精品论坛 >> 『 CFD 专栏 』 >> 介绍方程离散化的经典文章

本主题已阅读1800次,回复0 篇

本论坛言论纯属发表者个人意见，与 阳光精品论坛 立场无关 联系我们 Powered by BMForum v5.0 Skin by Bob Shen