规避障碍物算法

花开富贵

假定有一根数轴，有两种长度的材料，数轴上面有若干障碍物，

现在给定一个起点、终点，要求使用2种材料进行排布，并优先使用其中一种，材料的端点不能在障碍物的影响半径以内（每个障碍物影响半径不同）

比如两个材料长度是900，1200，障碍物的x坐标分别是2400，3000，影响半径分别是10，20，优先使用材料1200，指定起点0，终点3600，那么使用的材料分别是：
1200，900，1200，空缺300

我在想这个应该是可以通过递归写出一个函数，但是苦于没有思路，大家有什么建议吗？

caoliu023

以下由gpt回复：
是的，你可以通过递归来解决这个问题。
下面是一个使用递归的Python函数示例，可以根据给定的起点、终点、材料长度和障碍物信息来排布材料

1. def arrange_material(start, end, material_lengths, obstacles):
   
2.     # 递归终止条件：起点和终点之间没有障碍物
   
3.     if not any(obstacle[0] <= start <= obstacle[1] or obstacle[0] <= end <= obstacle[1] for obstacle in obstacles):
   
4.         return [material_lengths[0]] * ((end - start) // material_lengths[0]) + [material_lengths[1]]
   
5. 
   
6.     # 递归终止条件：材料长度不足以覆盖起点和终点之间的障碍物
   
7.     if material_lengths[0] < max(obstacle[1] - obstacle[0] for obstacle in obstacles):
   
8.         return None
   
9. 
   
10.     # 优先使用第一种材料
    
11.     arrangement = [material_lengths[0]]
    
12. 
    
13.     # 查找起点和终点之间的第一个障碍物
    
14.     for obstacle in obstacles:
    
15.         if obstacle[0] <= start <= obstacle[1] or obstacle[0] <= end <= obstacle[1]:
    
16.             break
    
17. 
    
18.     # 将材料排布到障碍物之前的部分
    
19.     if obstacle[0] > start:
    
20.         sub_arrangement = arrange_material(start, obstacle[0], material_lengths, obstacles)
    
21.         if sub_arrangement is None:
    
22.             return None
    
23.         arrangement.extend(sub_arrangement)
    
24. 
    
25.     # 将材料排布到障碍物之后的部分
    
26.     sub_arrangement = arrange_material(obstacle[1], end, material_lengths, obstacles)
    
27.     if sub_arrangement is None:
    
28.         return None
    
29.     arrangement.extend(sub_arrangement)
    
30. 
    
31.     return arrangement

复制代码

使用示例：

1. material_lengths = [1200, 900]
   
2. obstacles = [(2400, 2410), (3000, 3020)]
   
3. start = 0
   
4. end = 3600
   
5. 
   
6. result = arrange_material(start, end, material_lengths, obstacles)
   
7. if result is not None:
   
8.     print("使用的材料分别是:", result)
   
9. else:
   
10.     print("无法排布材料以满足要求")

复制代码

输出：

使用的材料分别是: [1200, 900, 1200, 900, 1200, 900, 300]
注意：这只是一个简单的示例函数，仅考虑了给定的情况，并没有对所有可能的输入进行全面的验证。 在实际使用时，你可能需要根据具体情况进行适当的调整和扩展

花开富贵

(defun f(LenUsing)
        (setq lenTotal (sumx LenUsing))       
        (cond                
                ((vl-some '(lambda(y z) (equal lenTotal y z)) obstruction Rinfluence)
                        (f (PlanB LenUsing))
                )
                ((<= lenMax2 lenTotal lenMax) (reverse LenUsing))
                ((< lenMax lenTotal ) (reverse(cdr LenUsing)))
                (t (f (cons LenRecommend  LenUsing)))
        )
)


(defun PlanB(LenUsing / elenew lenusing$ loop)
        (setq LenUsing$ LenUsing
                loop t
        )
        (while loop
                (if (setq eleNew(cadr (member (car LenUsing$) LenList)))
                        (setq LenUsing$ (cons eleNew (cdr LenUsing$))  loop nil)
                        (setq LenUsing$ (cdr LenUsing$))
                )
                (if (null LenUsing$) (getstring"\n已经没有替代方案了，检查是否有错误，或者补充下备用材料再尝试运行此命令"))
        )
        LenUsing$
)


(defun sumx (x)
        (if x (apply '+ x) 0.0)
)


例子

(defun c:tt()
  (setq
    LenMax 1000;;;任务总要求
    LenMax2 950;;;任务临界值
   
    LenList '(  120 90 60);;;优先用120，其次90，再60......
    LenRecommend (car LenList);;;推荐材料尺寸
    obstruction '(100 240 350 540 980);;;障碍物位置
    R 0.01
    Rinfluence '(20 30 40 30 30);;;障碍物影响半径
    )
  (princ"\n从前到后的材料长度分别为：")(f (list LenRecommend))
  )

花开富贵

mahuan1279 发表于 2023-9-8 14:32
优先使用较长的？还是说不管怎么组合，只要不碰到障碍物及影响半径内就行？

是的，可以横穿障碍物及影响半径，但是端点一定不能落到影响半径内部，（这个时候就需要使用另一种长度的材料进行调整了），这些材料直接都是连续的，没有缝隙的。
有的时候可能需要2次甚至3次调整才可以避开影响半径

花开富贵

如果这个例子里面影响半径分别是10，30，那么结果就是900，900，900，900

花开富贵

花开富贵 发表于 2023-9-8 10:50
如果这个例子里面影响半径分别是10，30，那么结果就是900，900，900，900

说错了，影响半径分别是100，300

mahuan1279

啥叫“优先使用其中一种”？最好画图说明所述问题。

花开富贵

mahuan1279 发表于 2023-9-8 13:27
啥叫“优先使用其中一种”？最好画图说明所述问题。

就是使用一种长度的材料，如果碰到了障碍物，这个时候就换另一个长度的，比如优先使用1200的，在没有碰到障碍物的时候都是1200，碰到了就换900

mahuan1279

花开富贵 发表于 2023-9-8 14:29
就是使用一种长度的材料，如果碰到了障碍物，这个时候就换另一个长度的，比如优先使用1200的，在没有碰到 ...

优先使用较长的？还是说不管怎么组合，只要不碰到障碍物及影响半径内就行？

mahuan1279

你的题目没有描述清楚。是否理解成多个间隔区间（中间被障碍物隔断）上的线性组合问题？

花开富贵

mahuan1279 发表于 2023-9-8 14:32
优先使用较长的？还是说不管怎么组合，只要不碰到障碍物及影响半径内就行？

优先使用1200，横穿不了障碍物半径的时候，才使用900的，就是优先使用1200进行组合。

最终组合的结果是多条连续的线，没有缝隙的线

mahuan1279

花开富贵 发表于 2023-9-8 15:25
优先使用1200，横穿不了障碍物半径的时候，才使用900的，就是优先使用1200进行组合。

最终组合的结果 ...

那要是第一个障碍物处就卡壳了咋办？比如第一个不管选1200，还是900，右端点都在第一个障碍物半径内？