求一个算法，多边形对角线的问题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 4210 天前的主题，其中的信息可能已经有所发展或是发生改变。

问题是这样的

有一个多边形，有n个顶点，现在想取m个对角线，而行这m个对角线是不相交的，问最多有多少种取法

比如，5个顶点的多边形，取2个不相交的对角线，可以有5种取法

做interviewstreet的编程挑战，卡到这里了，求解惑

对角线

多边形

取法

22 条回复 • 1970-01-01 08:00:00 +08:00

plan9

2012-10-25 14:59:59 +08:00

目前的想法是这样的

1，求所有对角线
2，从里面取m个对角线并查看是否相交，如果不相交则count加一
3，重复2，直到对角线都取了个遍

有其他更好的吗

aa88kk

2012-10-25 15:17:39 +08:00

简单想了下，应该是个排列组合问题，先从n个点选m, m多边形再两两相连，找出不相交的两条线。

plan9

2012-10-25 15:31:44 +08:00

@aa88kk m是对角线的个数，2条对角线可能有2个顶点，也可能有4个顶点，而且可能我表达的不够清楚，要找的不是2条对角线，而是要找m条不相交的对角线的可能性有几种

比如有1，2，3，4，5这5个顶点，2条不相交的对角线为
13，14
24，25
31，35
42，41
52，52
因此有5种可能性

txx

2012-10-25 18:59:59 +08:00

@plan9 你的方法太暴力明显订一个顺序写一个递归会更好

chx007

2012-10-25 19:14:46 +08:00

是正多边形吗？
如果不是，是凸多边形吗？
如果不是，多边形自身的边有没相交呢？

chx007

2012-10-25 19:28:06 +08:00

如果是凸多边形（包括正多边形）应该是吧
m = n * ( n - 3 ) / 2

momou

2012-10-25 21:23:34 +08:00

给多边型定义一个坐标系，就很容易解决了。。。

leoleozhu

2012-10-25 21:32:20 +08:00

@plan9 13,14不是会在1处相交吗

luin

2012-10-25 21:53:23 +08:00

想象成一维的就好解决了啊

plan9

2012-10-25 23:53:32 +08:00

@txx 是啊，我也感觉太暴力

plan9

2012-10-25 23:54:16 +08:00

@txx 求订一个顺序递归做的算法

plan9

2012-10-25 23:55:22 +08:00

@chx007 不是，但是求最大的可能性，最大可能性应该就是正多边形

plan9

2012-10-25 23:56:28 +08:00

@chx007 这个。。。不是求对角线的个数。。。

plan9

2012-10-25 23:57:04 +08:00

@momou 求解答

plan9

2012-10-25 23:58:01 +08:00

@leoleozhu 具有同一个顶点的不算相交

zellux

2012-10-26 00:03:55 +08:00

和 Catalan 数的算法有点类似。取一条对角线把多边形分成两个，接下来要在左右两个多边形中一共取 m - 1 条，可能的取法是左边 0 条，右边 m - 1 条；左边 1 条，右边 m - 2 条……；左边 m - 1 条，右边 0 条（这里有些取法可能不成立，比如左边是三角形的话就只能取 0 条对角线）。这样递归下去就能算出来了。

Air_Mu

2012-10-26 00:12:28 +08:00

请用严谨的语言描述数学问题。不相交具体到底上什么情况？是在图形内不相交还是完全不相交（平行）。或者说AB 和AC这两条线相交于点A 这算相交还是不相交？

还有，这多边形是什么样的多边形？这种变态的图形也是多边形哦：

txx

2012-10-26 00:49:49 +08:00

@plan9 见@zellux 不过要想清楚就是了顺着时针考虑好边界情况

plan9

2012-10-26 01:36:08 +08:00

@zellux
@txx
非常感谢，也想过类似的方法，不过觉得这样得到的结果是不全的

按照这种方法，要想求得所有可能性的话
每次再归都要知道所在多边形的所有对角线
然后要拿每条对角线进行分割
并且要记录下来每个可能性的对角线都是什么
每次再归要是发现新的可能性都有与之前所记录的每种可能性进行比较

这样反而感觉更加暴力了

plan9

2012-10-26 01:39:25 +08:00

@Air_Mu 问题上没有说是什么样的多边形。。。就是说你这种变态多边形的也是可能的
相交的话只说了是在多边形的内部相交，那么AB 和AC这两条线相交于点A应该不算相交了
其他的描述就什么也没有了，还没有我这里描述的详细。。。

darkgt

2012-10-26 02:22:20 +08:00

见过类似的问题，参见http://discuss.codechef.com/questions/1968/maxgame-editorial
不过那个问题没有限制对角线的个数(m)，而且K=1的时候是要求对角线不能共点。
@zellux说的会导致重复情况被算了多次，不过做法类似。
放对角线的过程可以看做：
给一个n个点多边形形状的蛋糕，然后每次沿着2个顶点切一刀，(这两块蛋糕有一块只有1个刀痕，另一块有2个刀痕)，留下那个有1个刀痕的，重复上面的过程。
有个问题是重复计算，比如(0,1,2,3,4,5)的一个方案是(0,4)(0,3)(1,3)，先切(0,4)或(1,3)都会产生这个结果。不过还好，这种对于每种方案，只重复了2次(这里需要一些抽象思维)，因为切蛋糕的顺序只能是(0,4)(0,3)(1,3)或者(1,3)(0,3)(0,4)，两种方案是顺序反过来的。

下面说做法:
首先考虑在一个n点多边形(蛋糕^^)放一条对角线，会把多边形分成 i个点和 n-i+2个点的两个多边形(稍微比划一下就能想出来)，只在i个点那个多边形里继续操作，然后将最后的合法方案数/2。
递归是非常慢的，实现上使用动态规划就可以了。
dp[n][m]表示在个n点多边形放m个对角线的方案数，dp[n][m] = sum( dp[i][m-1] )，i=3~n-i-1
两个循环即可，复杂度O(n*n*m)

darkgt

2012-10-26 02:36:05 +08:00

更正一下。
计数那里有点问题，在一个有n个边的蛋糕切一刀，保留有i条边的子蛋糕(并且只有1个切痕)，这个过程的方案刚才忘考虑了。
我想了下，应该是n-i+1

所以 dp[n][m] = sum( dp[i][m-1]*(n-i+1) )