这个问题到底有没有多项式复杂度的解法哦

gta

　　设有m条水平线和n条垂直线共组成m*n个交点。
　　现选取一些交点。
　　要求任意四个所选的交点都不成为矩形的四个顶点。
　　应如何选取最多的交点？

注意，矩形是指水平矩形，如图
　　
     --a--A---B---C---*----*---*----*---*-
　　--f--b---D---*---*----*---*----*---*-
　　--*--g---c---*---*----*---*----*---*-
　　--*--*---h---d---*----*---*----*---*-
　　--*--*---*---i---e----*---*----*---*-
　　--*--*---*---*---j----*---*----*---*-
　　--*--*---*---*---*----*---*----*---*-
　　如果存在aAfb,ABbD,AgBc...... 这样的就不符合要求，
　　而 AfgD 这样的就不认为是矩形的四个顶点。

请问这个问题有没有多项式复杂度的算法啊

[ 本帖最后由 gta 于 2008-2-16 12:23 编辑 ]

emacsnw

难道不是m+n-1个？

gta

原帖由 emacsnw 于 2008-2-16 15:14 发表
难道不是m+n-1个？

应该不是吧。比如下图

醉卧水云间

m, n是无穷大的话， 点的数量也是有限的, 和m, n无关.

这是我的猜测! 暂时没想到怎么写程序来计算.

ydhbzkx

我觉的只要四个点所在线的数目只要不为四就可以了!

gta

谢谢各位。我发帖的目的不是要得到一个形如f(m,n)的公式。我是想知道有没有polynomial time的算法。目前我能想到的只有递归回溯，但这种做法复杂度是2^(mn)。我也考虑过dynamic programming，但我发现这问题似乎没有"overlapping subproblems"这个特性，因此DP也不可行。

SuperZ

这个和8皇后问题很想啊。
当年学算法的时候，汉诺塔和8皇后问题是递归和回朔的必将题目。
理论上每个递归算法都有对应非递归算法，可是对于这些非递归并不一定更好用。

cugb_cat

原帖由 gta 于 2008-2-17 17:03 发表
谢谢各位。我发帖的目的不是要得到一个形如f(m,n)的公式。我是想知道有没有polynomial time的算法。目前我能想到的只有递归回溯，但这种做法复杂度是2^(mn)。我也考虑过dynamic programming，但我发现这问题似乎 ...

DP的话，楼主看看这样行不行，可能达不到多项式的复杂度：
每个点都可以看做是4个部分共用的顶点，而这四个部分的每个部分都是矩形套矩形的，这样就可以找到递归式了，通过记录中间值，减少重复计算，应该可以提高不少速度。

FancyMouse

>m, n是无穷大的话， 点的数量也是有限的, 和m, n无关.
对角线上全都可以选