algorithm - 形状内分布线的优化算法选择

Question

考虑带有钢筋和孔的混凝土板单元的以下表示。



我需要一种算法，可以自动将线分布在具有不同孔的任意形状上。

主要限制是:

线不能在区域外或孔内

两条并排线之间的距离不能超过变量 D

行必须以固定间隔定位 I ，即 y mod I = 0 ，其中 y是线的 Y 坐标。

形状内的每个可用点都不能比 D/2 更远离一条线

我想通过最小化总行数 N 来优化解决方案。什么样的优化算法适合这个问题？

我假设大多数方法涉及将形状简化为光栅(像素高度为 I)并禁用或启用每个像素。我认为这是一个明显的 LP 问题，并尝试使用 GLPK 来设置它，但发现使用这种针对任意数量线的简化栅格来描述问题非常困难。我也怀疑解空间可能太大了。

我已经在 C# 中实现了一个算法来完成这项工作，但不是很优化。这是它的工作原理:

创建几何的简化栅格

使用复杂的公式计算每个单元格的分数，该公式考虑了可能的线长以及与其他杆和障碍物的距离。

确定哪个需要加固(y 方向上的自由单元数 > D)

选择需要加固的得分最高的单元格，尽可能在-x和+x方向加固

重复

根据复杂的公式，这很有效，但在放置最后几行时开始给出不需要的结果，因为它永远不能移动已经放置的行。
还有其他优化技术我应该看看吗？

Answer 1

我不确定接下来的内容是您想要的 - 我相当确定这不是您的想法 - 但如果听起来合理，您可以尝试一下。

因为距离最多就是d ，并且可以比这更小，乍一看似乎贪婪的算法应该在这里工作。始终放置下一行，以便 (1) 尽可能少地需要，以及 (2) 它们尽可能远离现有行。

假设您有针对此问题的最佳算法，并将下一行放置在距离 a <= d 处。从最后一行。说它的地方b线。我们的贪心算法肯定不会超过b行(因为第一个标准是尽可能少地放置)，如果放置 b线，它会将它们放置在距离 c与 a <= c <= d ，因为它会尽可能地放置线条。

如果贪心算法没有做最优算法所做的事情，它的不同之处在于以下方式之一:

它将相同或更少的线放在更远的地方。假设最优算法继续放置 b'距离线 a'离开下一步。那么这些线将在距离 a+a'并且会有 b+b'总行。但是贪心算法可以通过放置b'来模拟这种情况下的最优算法。位移线 a+a'通过选择 c' = (a+a') - c .自 c > a和 a' < d , c' < d这是一个合法的安置。

它把更少的线放在一起。这个案子其实是有问题的。有可能这个地方k不必要的行，如果任何位置至少需要 k线和最远的需要更多，并且选择孔的排列使得(例如)它跨越的距离是d的倍数。 .

所以贪心算法在情况 2 中不起作用。然而，它在其他情况下起作用。特别是，我们在第一种情况下的观察非常有用:对于任意两个展示位置 (distance, lines)和 (distance', lines') , 如果 distance >= distance'和 lines <= lines' ，第一个位置始终是首选。这建议使用以下算法:

PlaceLines(start, stop)

    // if we are close enough to the other edge,
    // don't place any more lines.
    if start + d >= stop then return ([], 0)

    // see how many lines we can place at distance
    // d from the last placed lines. no need to
    // ever place more lines than this
    nmax = min_lines_at_distance(start + d)

    // see how that selection pans out by recursively
    // seeing how line placement works after choosing
    // nmax lines at distance d from the last lines.
    optimal = PlaceLines(start + d, stop)
    optimal[0] = [d] . optimal[0]
    optimal[1] = nmax + optimal[1]

    // we only need to try fewer lines, never more
    for n = 1 to nmax do

        // find the max displacement a from the last placed
        // lines where we can place n lines.
        a = max_distance_for_lines(start, stop, n)

        if a is undefined then continue

        // see how that choice pans out by placing
        // the rest of the lines
        candidate = PlaceLines(start + a, stop)
        candidate[0] = [a] . candidate[0]
        candidate[1] = n + candidate[1]

        // replace the last best placement with the
        // one we just tried, if it turned out to be
        // better than the last
        if candidate[1] < optimal[1] then
            optimal = candidate

    // return the best placement we found
    return optimal

这可以通过放入结果 (seq, lines) 的内存来改善到由 (start, stop) 索引的缓存中.这样，我们可以识别何时尝试计算可能已经评估过的分配。我希望我们会有很多这种情况，无论您对问题实例使用粗离散化还是精细离散化。

我没有详细说明如何 max_lines_at_distance和 max_distance_for_lines函数可能会起作用，但也许就这些而言。

第一个告诉您在给定位移下需要多少条线来跨越几何图形。如果您将几何图形和彩色孔像素化为黑色，这将意味着查看指定位移处的单元格行，考虑连续的黑色线段，并从那里确定隐含的线数。

第二个告诉您，对于给定的候选行数，可以放置该行数的当前位置的最大距离。您可以通过让它告诉您可以放置​​该数量或更少的线的最大距离来改善这一点。如果您使用此改进，您可以反转迭代的方向 n和:

如果 f(start, stop, x) = a和 y < x , 最多只需要搜索 a ，不是 stop ， 从那时起;

如果 f(start, stop, x)未定义和 y < x ，您无需再搜索。

请注意，如果无法放置 n，则此函数可以是未定义的。或更少的行在 start 之间的任何地方和 stop .

另请注意，您可以单独内存这些函数以节省重复查找。您可以预先计算 max_lines_at_distance对于每一行并将其存储在缓存中以备后用。然后， max_distance_for_lines可能是一个循环，在两个边界内将缓存从前检查。