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

Question

考虑具有钢筋和孔的混凝土板元件的以下表示.

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

主要限制因素是:

1. 线不能在区域之外或在洞内
2. 两个并排线之间的距离不能超过变量 D
3. 线必须以固定的间隔定位I,即线的Y坐标y mod I = 0在哪里y.
4. 形状内的每个可用点都不能比一条线更远 D/2

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

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

我已经在C#中实现了一个算法来完成这项工作,但还没有很好地优化.这是它的工作原理:

1. 创建几何的简化栅格
2. 使用复杂的公式计算每个单元格的分数,该公式考虑了可能的线路长度和与其他杆和障碍物的距离.
3. 确定哪些需要加固(y方向的自由单元数> D)
4. 选择具有需要加固的最高分的单元格,并在-x和+ x方向上尽可能地加强它
5. 重复

根据复杂的公式,这可以很好地工作,但是在放置最后几行时会开始给出不需要的结果,因为它永远不会移动已经放置的行.我还应该看看其他任何优化技术吗？

Answer 1

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

因为距离最多 d为，并且可以小于该距离，所以乍一看似乎贪婪算法应该在这里起作用。始终放置下一行，以便 (1) 需要的数量尽可能少，并且 (2) 它们距离现有行尽可能远。

假设您有一个解决此问题的最佳算法，并且它将下一行放置在距a <= d上一行一定距离的位置。说它放置了b线。我们的贪婪算法肯定不会放置超过b线（因为第一个标准是放置尽可能少的线），并且如果它放置b线，它将把它们放置在与 的距离c处a <= c <= d，因为它然后将线放置得尽可能远。

如果贪心算法没有执行最优算法的操作，则它在以下方面之一有所不同：

1. 它将相同或更少的线放置在更远的地方。假设最优算法在下一步中继续b'在远处放置线条。a'那么这些线就会相距一定距离，并且总共a+a'会有线。但在这种情况下，贪心算法可以通过选择 来将线放置在位移处，b+b'从而模仿最优算法。由于和，这是一个合法的配售。b'a+a'c' = (a+a') - cc > aa' < dc' < d

2. 它使更少的线条更靠近。这个案例其实是有问题的。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，并且：

1. 如果f(start, stop, x) = a和y < x，则只需要搜索到a，而不是stop，从此以后；
2. 如果f(start, stop, x)未定义并且y < x，则无需再搜索。

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

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