求优化算法：若干矩形覆盖闭合曲线围成的区域
任意闭合曲线，用若干矩形去覆盖，使得多覆盖的区域面积尽可能小，漏盖的区域面积尽可能小，矩形的个数尽可能少。
各位同行们多多指教。。。。
[70 byte] By [msdn] at [2007-9-26 8:19:57] 
# 1 Re: 求优化算法：若干矩形覆盖闭合曲线围成的区域
"区域面积尽可能小"，"矩形的个数尽可能少" 是2个矛盾的要求,
你可以只用一个矩形来覆盖,这时数目最少了,但有些遗漏!
你可以用n个矩形来覆盖,这时数目虽多,但一点也不遗漏了!
你必须说明哪一个更重要?
zzwu at 2004-9-23 16:17:16 >
# 4 Re: 求优化算法：若干矩形覆盖闭合曲线围成的区域
上面讲错了,改为:
"区域面积尽可能小"，"矩形的个数尽可能少" 是2个矛盾的要求,
你可以只用一个矩形来覆盖,这时数目最少了,但有些多覆盖的区域,
你可以用n个矩形来覆盖,这时数目虽多,但可以做到一点也不多覆盖!
你必须说明哪一个更重要?
zzwu at 2004-9-23 16:44:22 >
# 5 Re: 求优化算法：若干矩形覆盖闭合曲线围成的区域
syy64(太平洋):这个问题的背景的确很象Gis的问题。闭合曲线就好比有多峰的垂直截面地型图。“拓扑和overlay”?我Google先 ，多谢。
fzx at 2004-9-23 18:45:46 >
# 6 Re: 求优化算法：若干矩形覆盖闭合曲线围成的区域
zzwu(未名) ( )：久仰。
是我表述不清楚。
算法输入：闭合曲线。
算法输出：若干矩形的长、宽。
约束条件：
1）覆盖后，漏掉的区域面积尽可能小（有漏掉区域面积的容差）
2）覆盖后，多覆盖的区域面积尽可能小（有多覆盖的面积容差）
3）矩形的个数尽可能少（有数目上限，但要尽可能少）
同时满足上述约束条件，要求找到最优解/较优解。
再次感谢！
fzx at 2004-9-23 18:56:22 >
# 7 Re: 求优化算法：若干矩形覆盖闭合曲线围成的区域
syy64(太平洋):我没学过GIS,能否提供一点叠置算法的资料?
fudqpi@ sina.com.cn
3Q!
fzx at 2004-9-23 19:47:01 >
# 9 Re: 求优化算法：若干矩形覆盖闭合曲线围成的区域
fzx(乐言不言) :
你讲清楚3个约束条件,但仍然没有把"最优"的"目标"函数讲出来.
也就是说,设
x = 覆盖后漏掉的区域面积
y = 覆盖后多覆盖的区域面积
z = 矩形的个数
你想作最优化,即min{f(x,y,z)},的函数f(x,y,z)的表达式是什么?
zzwu at 2004-9-24 10:39:20 >
# 10 Re: 求优化算法：若干矩形覆盖闭合曲线围成的区域
打个比方(仅仅是比方,未考虑函数实际是否可用),你可以选
1. f(x,y,z)=x+y+z, 这表示3个参数同等重要
2. f(x,y,z)=3x+2y+z, 这表示漏掉区域面积最重要,多覆盖的区域面积其次,矩形的个数最不重要
3. f(x,y,z)=x*x*x+y*y+z, 和2一样,但3者的重要性差别更明显了.
zzwu at 2004-9-24 10:49:35 >
# 11 Re: 求优化算法：若干矩形覆盖闭合曲线围成的区域
zzwu(未名):
我数学不好，见笑了。
你的提示，也让我想清楚了，这其中的确要加权。
因为这个算法问题是从一个很专业的业务中抽象出来的，权重（f(x,y,z)表达式）其实也是外界输入，姑且假设这样：
f(x, y, z) = a * x + b * y + c * z；(a,b,c 都是float类型)
不知道有没有更通用的算法，不依赖于具体f(x,y,z)？
fzx at 2004-9-24 14:09:45 >
# 12 Re: 求优化算法：若干矩形覆盖闭合曲线围成的区域
如果f(x, y, z) = x + y + z；这个问题怎么解？
再次感叹：数学对软件开发实在太重要了。作这个行当，数学不好，真的走不远。
以后多来这个版块，向大家学习。。。
fzx at 2004-9-24 14:20:56 >
# 14 Re: 求优化算法：若干矩形覆盖闭合曲线围成的区域
求线性表达式:
f(x,y,z) = ax + by + cz
的(x,y,z),使f(x,y,z)取到最大或最小,其中x,y,z本身带有线性的约束条件,
是一种"线性规划"问题,有多种工具可用.
可在名字叫<线性规划>,<最优化方法>,<运筹学>等的书中找到所需的工具.
zzwu at 2004-9-27 15:00:05 >