V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
plan9
V2EX  ›  程序员

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

  •  
  •   plan9 · 2012-10-25 14:53:50 +08:00 · 5461 次点击
    这是一个创建于 4441 天前的主题,其中的信息可能已经有所发展或是发生改变。
    问题是这样的

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

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

    做interviewstreet的编程挑战,卡到这里了,求解惑
    22 条回复    1970-01-01 08:00:00 +08:00
    plan9
        1
    plan9  
    OP
       2012-10-25 14:59:59 +08:00
    目前的想法是这样的

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

    有其他更好的吗
    aa88kk
        2
    aa88kk  
       2012-10-25 15:17:39 +08:00
    简单想了下,应该是个排列组合问题, 先从n个点选m, m多边形再两两相连,找出不相交的两条线。
    plan9
        3
    plan9  
    OP
       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
        4
    txx  
       2012-10-25 18:59:59 +08:00
    @plan9 你的方法太暴力 明显订一个顺序写一个递归会更好
    chx007
        5
    chx007  
       2012-10-25 19:14:46 +08:00
    是正多边形吗?
    如果不是,是凸多边形吗?
    如果不是,多边形自身的边有没相交呢?
    chx007
        6
    chx007  
       2012-10-25 19:28:06 +08:00
    如果是凸多边形(包括正多边形)应该是吧
    m = n * ( n - 3 ) / 2
    momou
        7
    momou  
       2012-10-25 21:23:34 +08:00
    给多边型定义一个坐标系,就很容易解决了。。。
    leoleozhu
        8
    leoleozhu  
       2012-10-25 21:32:20 +08:00
    @plan9 13,14不是会在1处相交吗
    luin
        9
    luin  
       2012-10-25 21:53:23 +08:00
    想象成一维的就好解决了啊
    plan9
        10
    plan9  
    OP
       2012-10-25 23:53:32 +08:00
    @txx 是啊,我也感觉太暴力
    plan9
        11
    plan9  
    OP
       2012-10-25 23:54:16 +08:00
    @txx 求订一个顺序递归做的算法
    plan9
        12
    plan9  
    OP
       2012-10-25 23:55:22 +08:00
    @chx007 不是,但是求最大的可能性,最大可能性应该就是正多边形
    plan9
        13
    plan9  
    OP
       2012-10-25 23:56:28 +08:00
    @chx007 这个。。。不是求对角线的个数。。。
    plan9
        14
    plan9  
    OP
       2012-10-25 23:57:04 +08:00
    @momou 求解答
    plan9
        15
    plan9  
    OP
       2012-10-25 23:58:01 +08:00
    @leoleozhu 具有同一个顶点的不算相交
    zellux
        16
    zellux  
       2012-10-26 00:03:55 +08:00
    和 Catalan 数的算法有点类似。取一条对角线把多边形分成两个,接下来要在左右两个多边形中一共取 m - 1 条,可能的取法是左边 0 条,右边 m - 1 条;左边 1 条,右边 m - 2 条……;左边 m - 1 条,右边 0 条(这里有些取法可能不成立,比如左边是三角形的话就只能取 0 条对角线)。这样递归下去就能算出来了。
    Air_Mu
        17
    Air_Mu  
       2012-10-26 00:12:28 +08:00
    请用严谨的语言描述数学问题。不相交具体到底上什么情况?是在图形内不相交还是完全不相交(平行)。或者说AB 和AC这两条线相交于点A 这算相交还是不相交?

    还有,这多边形是什么样的多边形?这种变态的图形也是多边形哦:
    txx
        18
    txx  
       2012-10-26 00:49:49 +08:00
    @plan9 见@zellux 不过要想清楚就是了 顺着时针 考虑好边界情况
    plan9
        19
    plan9  
    OP
       2012-10-26 01:36:08 +08:00
    @zellux
    @txx
    非常感谢,也想过类似的方法,不过觉得这样得到的结果是不全的

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

    这样反而感觉更加暴力了
    plan9
        20
    plan9  
    OP
       2012-10-26 01:39:25 +08:00
    @Air_Mu 问题上没有说是什么样的多边形。。。就是说你这种变态多边形的也是可能的
    相交的话只说了是在多边形的内部相交,那么AB 和AC这两条线相交于点A应该不算相交了
    其他的描述就什么也没有了,还没有我这里描述的详细。。。
    darkgt
        21
    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
        22
    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) )
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   6104 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 79ms · UTC 02:14 · PVG 10:14 · LAX 18:14 · JFK 21:14
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.