规避障碍物算法

花开富贵 · 发表于 2023-9-8 10:44

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

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

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

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

caoliu023 · 发表于 2023-9-9 22:19

本帖最后由 caoliu023 于 2023-9-9 22:23 编辑

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

def arrange_material(start, end, material_lengths, obstacles):
# 递归终止条件：起点和终点之间没有障碍物
if not any(obstacle[0] <= start <= obstacle[1] or obstacle[0] <= end <= obstacle[1] for obstacle in obstacles):
return [material_lengths[0]] * ((end - start) // material_lengths[0]) + [material_lengths[1]]
# 递归终止条件：材料长度不足以覆盖起点和终点之间的障碍物
if material_lengths[0] < max(obstacle[1] - obstacle[0] for obstacle in obstacles):
return None
# 优先使用第一种材料
arrangement = [material_lengths[0]]
# 查找起点和终点之间的第一个障碍物
for obstacle in obstacles:
if obstacle[0] <= start <= obstacle[1] or obstacle[0] <= end <= obstacle[1]:
break
# 将材料排布到障碍物之前的部分
if obstacle[0] > start:
sub_arrangement = arrange_material(start, obstacle[0], material_lengths, obstacles)
if sub_arrangement is None:
return None
arrangement.extend(sub_arrangement)
# 将材料排布到障碍物之后的部分
sub_arrangement = arrange_material(obstacle[1], end, material_lengths, obstacles)
if sub_arrangement is None:
return None
arrangement.extend(sub_arrangement)
return arrangement

复制代码

使用示例：

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

复制代码

输出：

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

花开富贵 · 发表于 2023-9-9 22:57

(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))
  )

花开富贵 · 发表于 2023-9-8 15:23

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

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

花开富贵 · 发表于 2023-9-8 10:50

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

花开富贵 · 发表于 2023-9-8 10:55

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

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

mahuan1279 · 发表于 2023-9-8 13:27

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

花开富贵 · 发表于 2023-9-8 14:29

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

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

mahuan1279 · 发表于 2023-9-8 14:32

本帖最后由 mahuan1279 于 2023-9-8 14:34 编辑

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

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

mahuan1279 · 发表于 2023-9-8 14:40

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

花开富贵 · 发表于 2023-9-8 15:25

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

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

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

mahuan1279 · 发表于 2023-9-8 15:45

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

最终组合的结果 ...

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

账号		自动登录	找回密码
密码			注册