V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
suspended
V2EX  ›  问与答

请教大家一个算法,脑子烧糊了。。。

  •  
  •   suspended · 2016-12-03 18:26:28 +08:00 · 3248 次点击
    这是一个创建于 2671 天前的主题,其中的信息可能已经有所发展或是发生改变。
    题目:

    已知一个矩形容器[(0,0), (W,H)],其中已经容纳(摆放)了 m 个小矩形,
    这些矩形均满足以下条件:
    1. 当然都比容器小,且摆放位置未超出容器范围;
    2. 所有小矩形的边均与容器的某一边平行或者重叠;
    3. 所有小矩形不重叠;
    4. 所有小矩形至少有两条相邻边与容器或者其他小矩形的边重叠(其实就是指
    小矩形向某角落挤紧,在保持不重叠的情况下只有 0 个或 1 一个自由度可滑动)

    问题算法:
    取另一个小矩形 (w,h)摆放到容器中,使其满足所有上述 1~4 的条件,
    求所有可能的摆法。


    想了很久没有思路。请教诸位了。
    第 1 条附言  ·  2016-12-03 20:34:48 +08:00
    补充一下:

    a) 矩形尺寸为整数;
    b) 条件 4 括号里的解释更严格,不过条件 4 也够了
    27 条回复    2016-12-04 11:26:26 +08:00
    sherlocktheplant
        1
    sherlocktheplant  
       2016-12-03 18:31:06 +08:00
    你这是要压缩贴图吗?
    suspended
        2
    suspended  
    OP
       2016-12-03 18:42:17 +08:00
    @sherlocktheplant 不是,工业需求。
    Kilerd
        3
    Kilerd  
       2016-12-03 19:24:38 +08:00
    这算是动态规划的题目把。
    sherlocktheplant
        4
    sherlocktheplant  
       2016-12-03 19:40:59 +08:00
    你可以看看 uv 压缩相关的算法 虽然是图形学的东西 但是实际是一样的
    9hills
        5
    9hills  
       2016-12-03 19:54:20 +08:00 via iPhone
    4 并不能得出 向某角落挤紧

    举个例子,小矩形绕内壁一周。
    SCaffrey
        6
    SCaffrey  
       2016-12-03 20:03:44 +08:00 via iPad
    数据范围大该怎样呢
    suspended
        7
    suspended  
    OP
       2016-12-03 20:12:01 +08:00
    @sherlocktheplant 那个方面的算法不太符合要求,因为不会考虑是否方便切割之类的工业要求。
    suspended
        8
    suspended  
    OP
       2016-12-03 20:14:41 +08:00
    @9hills 虽然我括号里的这个解释其实有点多余。。。不过你说的小矩形绕内壁一周没问题啊,只有在往四个角落挤紧是符合条件 4 的,因为要求至少两条相邻边重叠。
    9hills
        9
    9hills  
       2016-12-03 20:21:37 +08:00
    @suspended 某角落指的四个角落中任意一个么。。

    就算你这么解释也不对,比如容器 10X10 的,然后放入一个 5X10 的在中间,四个角落都不沾

    另外题目里也没有说矩形是不是有最小单位,如果没有的话,那解肯定是无穷多个
    9hills
        10
    9hills  
       2016-12-03 20:24:37 +08:00
    @suspended 没看到相邻边,有这个约束也没关系,在 5X10 靠边放一个 1X1 的就好了,还是四个角落都不沾
    suspended
        11
    suspended  
    OP
       2016-12-03 20:26:49 +08:00
    @9hills
    "比如容器 10X10 的,然后放入一个 5X10 的在中间,四个角落都不沾 "

    所以这种情况不符合要求 4 ,因为没有任何边与其他矩形重合。
    “某角落”是指任意角落,我表达得有些含糊了。

    另外,矩形肯定最小 1x1 , 0x0 不能称为矩形吧?
    suspended
        12
    suspended  
    OP
       2016-12-03 20:29:26 +08:00
    @9hills
    "在 5X10 靠边放一个 1X1 的就好了,还是四个角落都不沾"

    这个不矛盾啊,我是指往某一个角落挤紧,不是说位于某个角落。当然,其实不看括号里的解释就好了,如果觉得解释反而更不好理解的话。
    9hills
        13
    9hills  
       2016-12-03 20:29:27 +08:00
    @suspended 看我补充,你找两个 1x1 的方块,靠紧。放到任意一个边上,依然满足你的 1-4 的全部要求
    0.5x0.5 就不是矩形了?
    suspended
        14
    suspended  
    OP
       2016-12-03 20:32:00 +08:00
    @9hills 啊,对头,看来括号里的说明似乎比条件 4 更严密些,我得想想如何修改。

    矩形尺寸肯定是整数,我补充一下题干好了。
    9hills
        15
    9hills  
       2016-12-03 20:33:21 +08:00
    @suspended 你把矩形改成从第一个小矩形开始,必须一个一个添加就行了。

    看起来想是做切割。。。
    suspended
        16
    suspended  
    OP
       2016-12-03 20:38:02 +08:00
    @9hills 是做切割。我找了好些论文,比较了各种算法,挑出来一个最符合需求的来实现。论文嘛,限于篇幅,都语焉不详的,实现的时候发现其中的一个子算法(就是我的问题所述)论文里并没有交代,所以放上来请教一下大家。

    "你把矩形改成从第一个小矩形开始,必须一个一个添加就行了。",的确就是这么一个过程,不过会有本质区别吗?
    9hills
        17
    9hills  
       2016-12-03 20:40:44 +08:00
    其实我看了下,用轮询的方法,时间复杂度也不高。 M 和 N 不大的话轮询就好了。。。
    suspended
        18
    suspended  
    OP
       2016-12-03 21:05:22 +08:00
    @9hills 我目前想破脑袋想出来的也只有轮询了。 3x 。
    binux
        19
    binux  
       2016-12-03 21:15:00 +08:00
    工业算法和竞赛算法是不同的,很多时候,竞赛算法就是在「求所有可能的摆法」以及「最佳」中纠结。
    但是在工业中,贪婪次优都是是可行的。

    一边给出「求所有可能的摆法」,一边又要「考虑是否方便切割」,先搞清楚到底要什么比较好。
    suspended
        20
    suspended  
    OP
       2016-12-03 21:24:10 +08:00
    @binux 是从所有可能摆法中选优。题目的这个算法,即便穷举的话,时间复杂度大约是 O(n^2)?(不好意思,不懂算法啦)所以「求所有可能的摆法」完全可行吧,「考虑是否方便切割」就是如何选优(选优还有其他要求)的问题,这个条件以目前的计算能力是达不到最优的,只能在可接受的时间内找到个较优的算法。

    现在就是「求所有可能的摆法」这个步骤希望找到比穷举更好的办法喽。
    binux
        21
    binux  
       2016-12-03 21:36:49 +08:00
    @suspended 你需求只有添加 1 个,不能再多个矩形吗?如果不是,你怎么保证局部最优就是全局最优?
    suspended
        22
    suspended  
    OP
       2016-12-03 21:46:11 +08:00
    @binux 添一个能搞定之后,添多个不就是一个一个添喽。:D

    局部最优当然不保证全局最优。全局最优根本不可能实现,因为是个 N-P 问题啦。全局较优是外围算法来负责的,我这个问题里的算法只是全局算法里的一个步骤而已。因为论文里面这个步骤的算法没有交代,自己琢磨了几个小时也只有穷举的办法,所以才拿上来请教一下诸位同仁。
    suspended
        23
    suspended  
    OP
       2016-12-03 21:52:34 +08:00
    @SCaffrey 哎呀,漏掉了这位仁兄,不好意思。 m 最大在 1000 这个量级,谢谢。
    yangyaofei
        24
    yangyaofei  
       2016-12-03 23:10:32 +08:00 via Android
    这个……是为了更省料的切割方法?
    suspended
        25
    suspended  
    OP
       2016-12-03 23:24:17 +08:00
    @yangyaofei 是滴是滴,除了省料,还要好切
    SCaffrey
        26
    SCaffrey  
       2016-12-03 23:51:21 +08:00 via iPad
    既然 1000 那么枚举放的位置不就是很妙了吗 XD
    如果每次查询的小矩形规格是定值的话似乎可以预处理一波吧
    suspended
        27
    suspended  
    OP
       2016-12-04 11:26:26 +08:00
    @SCaffrey 规格肯定有若干,每个规格的矩形有若干。所以不想穷举的说。。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4351 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 10:11 · PVG 18:11 · LAX 03:11 · JFK 06:11
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.