规避障碍物算法
假定有一根数轴，有两种长度的材料，数轴上面有若干障碍物，现在给定一个起点、终点，要求使用2种材料进行排布，并优先使用其中一种，材料的端点不能在障碍物的影响半径以内（每个障碍物影响半径不同）
比如两个材料长度是900，1200，障碍物的x坐标分别是2400，3000，影响半径分别是10，20，优先使用材料1200，指定起点0，终点3600，那么使用的材料分别是：
1200，900，1200，空缺300
我在想这个应该是可以通过递归写出一个函数，但是苦于没有思路，大家有什么建议吗？
本帖最后由 caoliu023 于 2023-9-9 22:23 编辑
以下由gpt回复：
是的，你可以通过递归来解决这个问题。
下面是一个使用递归的Python函数示例，可以根据给定的起点、终点、材料长度和障碍物信息来排布材料
def arrange_material(start, end, material_lengths, obstacles):
# 递归终止条件：起点和终点之间没有障碍物
if not any(obstacle <= start <= obstacle or obstacle <= end <= obstacle for obstacle in obstacles):
return ] * ((end - start) // material_lengths) + ]
# 递归终止条件：材料长度不足以覆盖起点和终点之间的障碍物
if material_lengths < max(obstacle - obstacle for obstacle in obstacles):
return None
# 优先使用第一种材料
arrangement = ]
# 查找起点和终点之间的第一个障碍物
for obstacle in obstacles:
if obstacle <= start <= obstacle or obstacle <= end <= obstacle:
break
# 将材料排布到障碍物之前的部分
if obstacle > start:
sub_arrangement = arrange_material(start, obstacle, material_lengths, obstacles)
if sub_arrangement is None:
return None
arrangement.extend(sub_arrangement)
# 将材料排布到障碍物之后的部分
sub_arrangement = arrange_material(obstacle, end, material_lengths, obstacles)
if sub_arrangement is None:
return None
arrangement.extend(sub_arrangement)
return arrangement
使用示例：
material_lengths =
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("无法排布材料以满足要求")
输出：
使用的材料分别是:
注意：这只是一个简单的示例函数，仅考虑了给定的情况，并没有对所有可能的输入进行全面的验证。 在实际使用时，你可能需要根据具体情况进行适当的调整和扩展
(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 LenRecommendLenUsing)))
)
)
(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 发表于 2023-9-8 13:27
啥叫“优先使用其中一种”？最好画图说明所述问题。
就是使用一种长度的材料，如果碰到了障碍物，这个时候就换另一个长度的，比如优先使用1200的，在没有碰到障碍物的时候都是1200，碰到了就换900 本帖最后由 mahuan1279 于 2023-9-8 14:34 编辑
花开富贵 发表于 2023-9-8 14:29
就是使用一种长度的材料，如果碰到了障碍物，这个时候就换另一个长度的，比如优先使用1200的，在没有碰到 ...
优先使用较长的？还是说不管怎么组合，只要不碰到障碍物及影响半径内就行？ 你的题目没有描述清楚。是否理解成多个间隔区间（中间被障碍物隔断）上的线性组合问题？ mahuan1279 发表于 2023-9-8 14:32
优先使用较长的？还是说不管怎么组合，只要不碰到障碍物及影响半径内就行？
优先使用1200，横穿不了障碍物半径的时候，才使用900的，就是优先使用1200进行组合。
最终组合的结果是多条连续的线，没有缝隙的线
花开富贵 发表于 2023-9-8 15:25
优先使用1200，横穿不了障碍物半径的时候，才使用900的，就是优先使用1200进行组合。
最终组合的结果 ...
那要是第一个障碍物处就卡壳了咋办？比如第一个不管选1200，还是900，右端点都在第一个障碍物半径内？
页:
[1]
2