BriefGPT - AI 论文速递 · 2024-01-25T00:00:00Z

层次任务网络规划中的可解性边界

📝

内容提要

研究了层次任务网络规划中的复杂理论界限，发现三个经典问题在常数偏序宽度的原始任务网络上可以在多项式时间内解决。然而，后两个问题只有在有关状态空间的明显必要限制下才成立。通过分析参数化复杂性，发现可以通过替换网络的点覆盖数来实现这三个问题的固定参数可解性。

🏷️

标签

参数化复杂性 复杂理论界限 多项式时间 层次任务网络规划 点覆盖数