gta
这个问题到底有没有多项式复杂度的解法哦
设有m条水平线和n条垂直线共组成m*n个交点。
现选取一些交点。
要求任意四个所选的交点都不成为[color=Red][color=Red]矩形[/color][/color]的四个顶点。
应如何选取最多的交点？
注意，[color=Red]矩形[/color]是指水平矩形，如图
--a--A---B---C---*----*---*----*---*-
--f--b---D---*---*----*---*----*---*-
--*--g---c---*---*----*---*----*---*-
--*--*---h---d---*----*---*----*---*-
--*--*---*---i---e----*---*----*---*-
--*--*---*---*---j----*---*----*---*-
--*--*---*---*---*----*---*----*---*-
如果存在aAfb,ABbD,AgBc...... 这样的就不符合要求，
而 AfgD 这样的就不认为是矩形的四个顶点。
请问这个问题有没有多项式复杂度的算法啊
[[i] 本帖最后由 gta 于 2008-2-16 12:23 编辑 [/i]]
gta
[quote]原帖由 [i]emacsnw[/i] 于 2008-2-16 15:14 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7967384&ptid=1053324][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]
难道不是m+n-1个？ [/quote]
应该不是吧。比如下图
醉卧水云间
m, n是无穷大的话， 点的数量也是有限的, 和m, n无关.
这是我的猜测! 暂时没想到怎么写程序来计算.
hll
回复 #4 醉卧水云间 的帖子
当n=2时，点的最大个数是m+1
ydhbzkx
可能
我觉的只要四个点所在线的数目只要不为四就可以了!
gta
谢谢各位。我发帖的目的不是要得到一个形如f(m,n)的公式。我是想知道有没有polynomial time的算法。目前我能想到的只有递归回溯，但这种做法复杂度是2^(mn)。我也考虑过dynamic programming，但我发现这问题似乎没有"overlapping subproblems"这个特性，因此DP也不可行。
SuperZ
这个和8皇后问题很想啊。
当年学算法的时候，汉诺塔和8皇后问题是递归和回朔的必将题目。
理论上每个递归算法都有对应非递归算法，可是对于这些非递归并不一定更好用。
cugb_cat
[quote]原帖由 [i]gta[/i] 于 2008-2-17 17:03 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=7970123&ptid=1053324][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]
谢谢各位。我发帖的目的不是要得到一个形如f(m,n)的公式。我是想知道有没有polynomial time的算法。目前我能想到的只有递归回溯，但这种做法复杂度是2^(mn)。我也考虑过dynamic programming，但我发现这问题似乎 ... [/quote]
DP的话，楼主看看这样行不行，可能达不到多项式的复杂度：
每个点都可以看做是4个部分共用的顶点，而这四个部分的每个部分都是矩形套矩形的，这样就可以找到递归式了，通过记录中间值，减少重复计算，应该可以提高不少速度。