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

Question

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

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

的主要限制是：

1. 线不能是区域的外侧或一个孔的内部
2. 两个侧由端线之间的距离不能超过一个可变D
3. 线上必须定位在固定间隔I，即y mod I = 0，其中y是行的Y坐标。
4. 形状内的每个可用的点不能由管线进一步比D/2

我想通过最小化线Ñ的总数，以优化的解决方案。什么样的优化算法适合这个问题？我假设大多数方法涉及到将光栅形状简化为像素高度（像素高度为I），并禁用或启用每个像素。我认为这是一个明显的LP问题，并试图用GLPK进行设置，但发现很难用这个简化的光栅来描述任意数量的行。我也怀疑解决方案空间可能太大。

我已经在C＃中实现了一个算法，可以完成这项工作，但并不是非常优化。这是如何工作的：

1. 创建几何
2. 的简化光栅计算用于使用复杂的公式，可能需要的线路长度和距离其它杆和障碍考虑每个小区的分数。
3. 确定哪些需要加强（其中y方向>d游离细胞数）
4. 接与需要加强最高分数的细胞，并尽可能在-x加强它和+ X方向
5. 重复

根据复杂的公式，这个效果很好，但开始把最后几行的时候给予不想要的结果，因为它不能移动已经放线。 有没有其他的优化技术，我应该看看？

Answer 1

我不确定接下来会发生什么 - 我相当确定这不是你想到的 - 但如果听起来合理，你可以试试看。

因为距离至多为d简单，并且可以是任何小于，似乎乍一看像一个贪心算法应该在这里工作。总是放置下一行，以便（1）尽可能少，（2）尽可能远离现有线路。

假设你有这个问题的最优算法，并放置在距离a <= d从最后一行的下一行（S）。说它放置b行。我们的贪心算法肯定会放置不超过b线（因为第一个标准是把尽可能少的），如果它把b线将它们放置在距离c与a <= c <= d，因为它然后将这些线就可能。

如果贪心算法没有做优化算法做了什么，它在不同的下列方式之一：

1. 它放置在相同或更少的行得更远。假设最佳算法在距下一步距离a'处放置b'行。然后这些线将在距离a+a'处，并且总共将有b+b'线。但贪婪算法可以通过选择c' = (a+a') - c将b'行置于位移a+a'处模拟最佳算法。由于c > a和a' < d,c' < 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可能是一个循环，在两个边界内检查缓存。