## 4 Path-Smoothing Method Based on an Improved Dynamic Programming Algorithm
### Improved Dynamic Programming Algorithm  
**Lemma 1**. : _If \(P=\left\{v_{1},v_{2},\ldots,v_{k}\right\}\) is the shortest path from \(v_{1}\) to \(v_{k}\), then for any two nodes \(v_{i}\) and \(v_{j}\)\((1\leq i\leq j\leq k)\) in this path, the sub-path \(\mathrm{P}_{ij}=\left\{v_{i},v_{i+1},\ldots,v_{j}\right\}\) is also the shortest path from \(v_{i}\) to \(v_{j}\)._  
The following proves the feasibility of using dynamic programming algorithm for this problem. Proof. : Since \(\mathrm{Q}\) is a TSP from \(\mathrm{B}\) to \(\mathrm{E}\), **Lemma 1** indicates that \(\mathrm{Q}\) has the property of optimal substructure. If there is a common point \(p_{j}=q_{i}\) in \(\mathrm{P}\), \(\mathrm{Q}\), and \(p_{j}\in P\cap Q\), then the subsequence \(\left\{\mathrm{B},\mathrm{q}_{1},\mathrm{q}_{2},\ldots,\mathrm{q}_{\mathrm{i}}\right\}\) of \(\mathrm{Q}\) forms a TSP from \(\mathrm{B}\) to \(q_{i}\), and the subsequence \(\left\{\mathrm{q}_{i},\mathrm{q}_{i+1},\ldots,\mathrm{q}_{\mathrm{i}},\mathrm{ E}\right\}\) of \(\mathrm{Q}\) forms a TSP from \(q_{i}\) to \(\mathrm{E}\). According to the definitions of \(\mathrm{P}\) and \(\mathrm{Q}\), \(\left\{\mathrm{B},\mathrm{q}_{1},\mathrm{q}_{2},\ldots,\mathrm{q}_{\mathrm{i}}\right\}\) is a subsequence of \(\left\{\mathrm{B},\mathrm{p}_{1},\mathrm{p}_{2},\ldots,\mathrm{p}_{\mathrm{j}}\right\}\), and \(\left\{\mathrm{q}_{i},\mathrm{q}_{i+1},\ldots,\mathrm{q}_{\mathrm{i}},\mathrm{ E}\right\}\) is a subsequence of \(\left\{\mathrm{p}_{j^{\prime}},\mathrm{p}_{\mathrm{j}+1},\ldots,\mathrm{p}_{r}, \mathrm{E}\right\}\). This means that the optimal solution to this problem can be broken down into the optimal solutions of these subproblems. Therefore, this problem also possesses the property of optimal substructure, and it can be solved using dynamic programming algorithms. Since this problem not only requires obtaining the path length but also storing the shortest path, an additional array is needed during the dynamic programming process to record the historical optimal paths. However, as the algorithm runs, the number of nodes in the historical optimal paths increases, causing the array's length to vary, which is not  
Figure 11: Data structure for a set of candidate points of length \(\mathrm{n}\) (ellipses represent path points and numbers represent their order in the set, and arrows indicate that there is a path in the set). conductive to pre-allocating space. Moreover, when the problem scale is large, a significant amount of storage space is required for these paths. To address this issue, we leverage the characteristic of the optimal substructure of candidate point sets by setting up an auxiliary array that stores the indices of predecessor nodes instead of the paths themselves, as shown in Figure 12.  
It is also noted that the set of candidate points has the following properties:  
**Property 1. **_The subsequent adjacent points of a point in the candidate set extracted by SGPs are continuous in the candidate set._  
**Proof of Property 1. ** Suppose that in the candidate set of a certain SGP, the subsequent adjacent points of a point are discontinuous in the set. That is, there exists a continuous subsequence \(\{\mathrm{A},\ldots,\mathrm{B},\mathrm{C},\ldots,\mathrm{D}\}\), where \(\{\mathrm{A},\ldots,\mathrm{B}\}\) are adjacent points, A and C are not adjacent, D is a subsequent candidate point of C, and A and D are adjacent. Since A and C are not adjacent points, the line connecting A and C must pass through an obstacle or a common vertex of two obstacle grids. Connect point A to the boundary point of the obstacle to form two lines \(\mathbf{a}\) and \(\mathbf{b}\), as shown in Figure 13. Since A and D are adjacent, D must be located outside lines \(\mathbf{a}\) and \(\mathbf{b}\). If D is on the outside of line \(\mathbf{a}\), because A and D are adjacent, line AD will not pass through the obstacle or the wall gap (which is considered illegal in this context).