代码之家  ›  专栏  ›  技术社区  ›  Chris

目标定位算法

partitioning object algorithm
  •  6
  • Chris  · 技术社区  · 16 年前

    我想知道这个问题是否有一个“最佳”的解决方案:

    我有一个n x m(像素)大小的空间,上面有p个预先存在的矩形对象,大小不一。现在我想在这个空间中放置Q(同样大小的)新对象,而不需要任何重叠。

    我提出的算法是:

    1. 创建大小为的数组A[] [(n)/(size_of_object_from_q)]x[(n)/(size_of_object_from_q)]

    2. 迭代p和中的所有元素:

      mark all fields in A[][] as occupied, where the element "lies"

    3. 将q中的所有元素放在未标记[]中字段的相应位置。

    (孩子,我希望我能理解…)

    有更好的方法吗?任何帮助都将不胜感激!

    3 回复  |  直到 16 年前
        1
  •  1
  •   Anna    16 年前

    从互联网上的一个简短搜索,似乎最佳矩形包装是 NP-hard 问题。 我想学术界的聪明人找到了一些近似算法,所以这是谷歌的一个选择。

    但我会首先尝试使简单的方法工作:

    1. 根据对象的宽度将其划分为大小
    2. 尝试将它们从最大到最小逐行放置。

    我的猜测是,在许多情况下,这种幼稚的解决方案会奏效。

        2
  •  1
  •   Larry OBrien    16 年前

    如果我理解这个问题,听起来你在寻找一个“最优”的装箱算法(又称背包问题)。这是一个NP完全问题,尽管你的描述听起来像是你可以蛮力地用你的方式找到一个最佳的解决方案。

        3
  •  0
  •   John Paulett    16 年前

    我知道这不是你问题的具体答案,但是研究和/或深入研究 graphviz 源代码。graphviz提供了许多布局模型,包括neato,它试图最小化全局能量函数。

    维基百科有一些伪代码 force-base algorithms .

    推荐文章
    关于   移动版
    代码之家 - 一站式码农服务社区
    沪ICP备11025650号