小编far*_*bro的帖子

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

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

主要限制因素是:

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. 重复

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