层次任务网络规划中的可解性边界
原文中文，约400字，阅读约需1分钟。发表于：。层次任务网络规划中的复杂理论界限研究，包括提供计划的验证、可执行计划的存在性和给定状态是否可以通过某个计划到达等三个经典问题。研究发现，在常数偏序宽度（及其推广）的原始任务网络上，这三个问题均可以在多项式时间内解决，而对于后两个问题，只有在有关状态空间的明显必要限制下才成立。然后，提出了一个算法元定理和相应的下界，以确定使得一般多项式时间可解性结果从原始任务网络推广到一般任务网络的紧密条件。...
研究了层次任务网络规划中的复杂理论界限，发现三个经典问题在常数偏序宽度的原始任务网络上可以在多项式时间内解决。然而，后两个问题只有在有关状态空间的明显必要限制下才成立。通过分析参数化复杂性，发现可以通过替换网络的点覆盖数来实现这三个问题的固定参数可解性。
