机器人路径规划问题(TMP1R)题解39.pdf

机器人路径规划问题 （TMP1R ）题解 by immortalCO 机器人路径规划问题 （TMP1R ）题解 by immortalCO 关键字 ：DP 最短路 0 楔子 机器人路径规划问题，是一个在树形路径上的路径规划类问题。本题由于难度较 大、编程复杂度和分析复杂度较高，成为了著名的“网络流与线性规划 24 题”中唯一 一题没有得到解决的问题。 事实上，这个问题并不像它所声称的那样是一个网络流问题。虽然在[1]中，存在 9 一个 O(n )的、缓慢的、定义不完全的网络流算法。 在本文开头，我们将给出一个完整的分析过程，以及一系列的定义及记号。接下 6 来，本文将给出一个时间复杂度为 O(n )的动态规划 （DP ）算法 ，以及它的具体实 现。这个算法的复杂度在后面会有一个新的表示方式 ，并且它的代价可以接近线性。 为了让读者能理解这些算法，我将会给出一些实例和数据辅助理解。 最后，我在这里声明，本题的官方数据存在很大的问题。除了第 1 组数据（n = 16 ）是合法的之外，第2 组数据的答案是错误的（这幅图即[2]中的第一幅演示图 ，答 案为 50 ，但数据中误为 20 ），第3-5 组数据均不满足“树形路径”的要求，图中存 在环路，导致此问题失效。关于一般图中的路径规划 ，参见[1]。 如果各位读者对有环的图上的机器人路径规划有兴趣，则可以阅读[1]。本文的算 法可以在 0.001s 之内通过测试数据，没有开启任何优化开关，包括 O2 编译优化。 日期 ：2015/1/23 Page[ 1 ] , Total = 25 福州一中 陈俊锟（immortalCO ） 机器人路径规划问题 （TMP1R ）题解 by immortalCO 1 题目描述 “机器人 Rob 可在一个树状路径上自由移动。给定树状路径 T 上的起点 s 和终点 t ，机器人Rob 要从 s 运动到 t。树状路径 T 上有若干可移动的障碍物。由于路径狭 窄，任何时刻在路径的任何位置不能同时容纳 2 个物体。每一步可以将障碍物或机器 人移到相邻的空节点上。计算使机器人从 s 运动到 t 的最小移动步数。 ” 本题是一个完整的 TMP1R （在树形路径上的机器人路径规划 ）。对于一个实例S = (T, s, t, O) ，包括一棵树T = (V, E)分别表示树的节点和边的集合 ，两个节点 s 和 t 表示机器人的起点和终点，以及一个集合 ⊂ V表示存在障碍物的集合 ，保证s ∉ O。 题目的要求是算出机器人从 s 到 t 的移动步数。下面这幅图是个样例，其中 A 是它的 一个最优解，答案为 50。 2 分析及定义 2.0 基础定义 设树 T 的节点个数为 n ，则边数为 n – 1。设 s 到 t 的唯一路径的长度为 d ，路径 为 P = (v , v , v , …, v ) ，从起点s = v 到终点 t = v 。我们称 P 为这幅图的绝对路 0 1 2 d 0 d 径 ，因为最小的移动步数 ≥ d ，当且仅当P ∩ O = ∅即 P 上不存在障碍时，等号成 立。对于一个 v ，如果 i 不为 0 ，和 v 存在连边的点 （称作 v 的相邻点 ）有至少 1 个 i i i 不在 P 上，那么称 v 为一个分支节点。对于每个分支节点，我们定义 v 的不在 P 上的 i i 相邻点中任意但固定的一个节点为一个让步节点 ，因为机器人可以到在这个节点上给 要向后运动的障碍物“让步”。 日期 ：2015/1/23 Page[ 2 ] , Total = 25 福州一中 陈俊锟（immortalCO ）