pxt19890404 发表于 2012-11-5 15:24

优化问题求助！

现有n个点，如果其中m个点（大于等于3个）能拟合出一条直线，且这m个点到该直线的距离都小于d，那么该m个点可组合成立一条直线，求这n个点的组合，使“组合出满足要求的直线数目”+“剩余点数”最少。这个问题怎么建模？用什么算法？请大神给予思路！

厚积薄发 发表于 2012-11-5 15:33

这个题目只需要找准决策变量就好办了

madio 发表于 2012-11-5 18:15

我感觉可以这样建模，先找到这n个点的重心，以这个重心为旋转轴，我们可以旋转一个宽度为2d的直线，看看转到什么角度可以覆盖最多的点！

pxt19890404 发表于 2012-11-5 18:29

madio 发表于 2012-11-5 18:15 static/image/common/back.gif
我感觉可以这样建模，先找到这n个点的重心，以这个重心为旋转轴，我们可以旋转一个宽度为2d的直线，看看转到 ...

这样的话不就是一条直线了吗？比如说有10个点，其中有3个点可以拟合出一条线，另外4个点能拟合出一条线，剩下的3个点不行，这样就是两条线和3个点。

pxt19890404 发表于 2012-11-5 18:31

厚积薄发 发表于 2012-11-5 15:33 static/image/common/back.gif
这个题目只需要找准决策变量就好办了

求大哥指教！小弟求教！

madio 发表于 2012-11-5 19:07

pxt19890404 发表于 2012-11-5 18:29 static/image/common/back.gif
这样的话不就是一条直线了吗？比如说有10个点，其中有3个点可以拟合出一条线，另外4个点能拟合出一条线， ...

你可以按照我说的方法继续进行就可以了，先找到一条可以覆盖最多点的直线，然后再把剩余的点拿出来再利用这个方法找到一条拟合最多点的直线，直到没有被覆盖的点小于三个为止!
页: [1]
查看完整版本: 优化问题求助！