- 中国铁道出版社
- 9787113319113
- 1-1
- 572090
- 61261746-4
- 16开
- 2025-08
- 工学
- 电子信息类
- 电子与信息大类
- 计算机类
- 计算机类
- 本科
作者简介
内容简介
本书以智能网联汽车决策规划算法的核心原理为基础，结合实际应用场景，深入浅出地讲解了路径规划与决策算法的基本思想与优化策略。全书共10章，分别讲解了Dijkstra算法、A*算法（A-starAlgorithm）、Bellman-Ford算法、Floyd-Warshall算法、Floyd算法、D*算法、D*Lite算法、基于A*算法变种的动态规划算法、RRT算法、优先级遍历算法。
目录
第1章Dijkstra算法..........................................................................................1
1.1Dijkstra算法简介.........................................................................................1
1.1.1背景与历史.................................................................................................1
1.1.2应用领域与典型场景..................................................................................2
1.2Dijkstra算法的核心思想..............................................................................2
1.2.1Dijkstra算法的实现步骤...........................................................................2
1.2.2Dijkstra算法图的表示方法.......................................................................3
1.3Dijkstra算法的应用案例..............................................................................4
1.3.1交通网络中的最短路径规划.......................................................................4
1.3.2在机器人导航系统中的应用.......................................................................5
1.4Dijkstra算法的局限性与改进.......................................................................7
1.4.1负权边问题.................................................................................................7
1.4.2大规模图的计算效率..................................................................................9
1.5综合实战——游戏地图中的最短路径规划...................................................10
1.5.1项目介绍.....................................................................................................10
1.5.2构建Graph..................................................................................................10
1.5.3具体实现......................................................................................................11
习题..........................................................................................................................12
第2章A*算法......................................................................................................14
2.1A*算法简介....................................................................................................14
2.1.1背景与历史...................................................................................................14
2.1.2应用领域与典型场景....................................................................................15
2.2A*算法的核心思想.........................................................................................15
2.2.1A*算法的原理和实现步骤...........................................................................15
2.2.2选择启发式函数（估算函数）......................................................................17
2.3A*算法的优化..................................................................................................18
2.3.1基本的优化措施.............................................................................................18
2.3.2HybridA*算法优化...............................................................................................20
2.4A*算法的应用案例...........................................................................................................22
2.4.1游戏开发中的路径规划.........................................................................................22
2.4.2在机器人导航系统中的应用.................................................................................23
习题..............................................................................................................................................38
第3章Bellman-Ford算法...............................................................................39
3.1Bellman-Ford算法介绍......................................................................................................39
3.1.1背景与历史.............................................................................................................39
3.1.2应用领域与典型场景.............................................................................................40
3.1.3Bellman-Ford算法与其他路径规划算法的对比..................................................41
3.1.4图的表示方法.........................................................................................................42
3.2Bellman-Ford算法的应用案例..........................................................................................42
3.2.1解决负权边的最短路径问题.................................................................................43
3.2.2在网络流量优化中的应用.....................................................................................44
3.2.3在自动驾驶路径规划中的应用.............................................................................44
3.3Bellman-Ford算法的局限性与改进..................................................................................46
3.3.1负权回路的处理.....................................................................................................46
3.3.2大规模图的计算效率.............................................................................................47
3.4综合实战——路线导航.....................................................................................................47
3.4.1项目背景.................................................................................................................48
3.4.2问题介绍.................................................................................................................49
3.4.3具体实现.................................................................................................................50
3.4.4调试运行.................................................................................................................53
3.5综合实战——基于FlaskWeb的路径规划可视化..........................................................55
3.5.1项目介绍.................................................................................................................56
3.5.2路径规划（1）.......................................................................................................56
3.5.3路径规划（2）.......................................................................................................59
3.5.4模板文件.................................................................................................................61
3.5.5脚本文件.................................................................................................................62
习题..............................................................................................................................................65
第4章Floyd-Warshall算法............................................................................66
4.1Floyd-Warshall算法简介...................................................................................................66
4.1.1背景与历史.............................................................................................................67
4.1.2应用领域与典型场景.............................................................................................67
4.2Floyd-Warshall算法的核心思想.......................................................................................68
4.2.1图的表示方法.........................................................................................................68
4.2.2Floyd-Warshall算法的推导过程............................................................................69
4.2.3Floyd-Warshall算法与其他路径规划算法的对比................................................70
4.3Floyd-Warshall算法的应用案例.......................................................................................71
4.3.1航空线路规划.........................................................................................................71
4.3.2城市交通规划应用.................................................................................................72
4.4Floyd-Warshall算法的局限性与改进...............................................................................74
4.4.1算法复杂度与大规模图的挑战.............................................................................74
4.4.2负权回路的处理策略.............................................................................................75
4.5综合实战——无人驾驶领域的路径规划系统（出租车/运输车）..............................76
4.5.1背景介绍.................................................................................................................76
4.5.2键值对映射模板.....................................................................................................77
4.5.3城市编号.................................................................................................................79
4.5.4红黑树数据结构和迭代器.....................................................................................80
4.5.5栈数据结构.............................................................................................................95
4.5.6迭代器接口.............................................................................................................97
4.5.7图结构.....................................................................................................................97
4.5.8车费信息.................................................................................................................98
4.5.9路径规划.................................................................................................................98
4.5.10收费信息.............................................................................................................102
4.5.11入口函数.............................................................................................................103
习题............................................................................................................................................104
第5章Floyd算法.........................................................................................105
5.1Floyd算法简介.................................................................................................................105
5.1.1背景与历史...........................................................................................................106
5.1.2Floyd算法和Floyd-Warshall算法的关系..........................................................106
5.1.3Floyd算法和Floyd-Warshall算法的区别..........................................................106
5.1.4应用领域与典型场景...........................................................................................107
5.2Floyd算法的核心思想.....................................................................................................107
5.2.1Floyd算法的原理和实现步骤.............................................................................107
5.2.2Floyd算法的计算过程.........................................................................................108
5.3Floyd算法的改进.............................................................................................................111
5.3.1通过空间优化来减少内存消耗...........................................................................111
5.3.2并行化优化...........................................................................................................112
5.4综合实战——校内机器人配送系统...............................................................................114
5.4.1项目介绍...............................................................................................................114
5.4.2具体实现...............................................................................................................115
习题............................................................................................................................................121
第6章D*算法..............................................................................................123
6.1动态路径规划算法简介...................................................................................................123
6.1.1静态路径规划算法和动态路径规划算法...........................................................124
6.1.2动态路径规划算法的背景...................................................................................124
6.1.3应用领域与场景...................................................................................................124
6.1.4常用的动态路径规划算法...................................................................................125
6.2D*算法介绍.....................................................................................................................125
6.2.1背景与历史...........................................................................................................126
6.2.2D*算法的原理和实现步骤.................................................................................126
6.2.3D*算法总体流程及与A*算法的对比...............................................................127
6.2.4D*算法的常用概念及函数.................................................................................127
6.3D*算法的应用案例.........................................................................................................128
6.3.1帮助探险家寻找最短路径...................................................................................128
6.3.2迷宫中的D*算法探索与动态障碍物处理........................................................138
6.3.3探索机器人的新家...............................................................................................146
6.4综合实战——基于D*算法的动态路径规划可视化系统............................................155
6.4.1项目介绍...............................................................................................................155
6.4.2D*算法功能的声明.............................................................................................156
6.4.3D*算法功能的实现.............................................................................................157
6.4.4主程序...................................................................................................................165
习题.................................................................................................................................168
第7章D*Lite算法........................................................................................................169
7.1D*Lite算法简介.......................................................................................................169
7.1.1背景与历史...........................................................................................................169
7.1.2应用领域与场景...................................................................................................170
7.2D*Lite算法的核心思想...........................................................................................171
7.2.1基本思想...............................................................................................................171
7.2.2D*Lite算法的实现步骤.......................................................................................171
7.3综合实战——可视化的D*Lite路径规划系统.........................................................172
7.3.1项目介绍...............................................................................................................172
7.3.2运算符重载...........................................................................................................173
7.3.3优先队列...............................................................................................................174
7.3.4实现D*Lite路径规划算法..................................................................................178
7.3.5绘制地图...............................................................................................................186
7.3.6主程序...................................................................................................................189
7.3.7编译运行...............................................................................................................191
7.4综合实战——智能路径导航系统.............................................................................192
7.4.1项目介绍...............................................................................................................192
7.4.2环境的建模和初始化...........................................................................................193
7.4.3实现D*Lite路径规划算法..................................................................................195
7.4.4可视化界面...........................................................................................................203
7.4.5主程序...................................................................................................................210
7.4.6调试运行...............................................................................................................211
习题..................................................................................................................................212
第8章基于A*算法变种的动态规划算法......................................................213
8.1A*算法的变种................................................................................................................213
8.2IncrementalA*算法........................................................................................................214
8.2.1IncrementalA*算法介绍......................................................................................214
8.2.2IncrementalA*算法的实现步骤..........................................................................215
8.3DynamicA*算法.............................................................................................................216
8.3.1DynamicA*算法介绍..........................................................................................216
8.3.2应用领域与场景...................................................................................................217
8.3.3DynamicA*算法的实现步骤..............................................................................217
8.3.4DynamicA*算法和D*算法的区别...................................................................219
习题.................................................................................................................................219
第9章RRT算法...........................................................................................220
9.1RRT算法介绍..........................................................................................................220
9.1.1机器人运动规划介绍...........................................................................................220
9.1.2改进的RRT算法..................................................................................................222
9.1.3与RRT算法相关的概念......................................................................................222
9.2RRT算法的定义与实现..........................................................................................223
9.2.1RRT算法的实现步骤...........................................................................................223
9.2.2原始的RRT算法..................................................................................................224
9.2.3基于概率P的RRT算法.....................................................................................225
9.2.4RRT_Connect算法...............................................................................................226
9.2.5RRT*算法.............................................................................................................227
9.3综合实战——机器人路径规划和轨迹优化系统..........................................................231
9.3.1项目介绍...............................................................................................................231
9.3.2实现RRT*算法....................................................................................................232
9.3.3生成加速度轨迹...................................................................................................241
9.3.4主程序...................................................................................................................248
9.3.5MATLAB可视化..................................................................................................249
9.4综合实战——基于pygame的RRT*路径规划系统....................................................250
9.4.1项目介绍...............................................................................................................250
9.4.2通用文件...............................................................................................................250
9.4.3事件处理...............................................................................................................252
9.4.4点处理...................................................................................................................253
9.4.5碰撞检测...............................................................................................................254
9.4.6绘图操作...............................................................................................................254
9.4.7RRT算法...............................................................................................................256
9.4.8主程序...................................................................................................................258
习题................................................................................................................................259
第10章优先级遍历算法...............................................................................260
10.1优先级遍历算法简介...............................................................................................260
10.1.1背景与历史.........................................................................................................260
10.1.2路径规划应用中的优先级遍历算法.................................................................261
10.2最佳优先搜索算法................................................................................................262
10.2.1最佳优先搜索算法的基本思想.........................................................................262
10.2.2最佳优先搜索算法的实现步骤.........................................................................262
10.2.3应用案例——寻找两个城市之间的最短路径.................................................265
10.3均匀代价搜索算法.........................................................................................................273
10.3.1均匀代价搜索算法的基本思想.........................................................................273
10.3.2均匀代价搜索算法的应用案例.........................................................................274
10.4深度优先搜索算法.........................................................................................................282
10.4.1深度优先搜索算法介绍.....................................................................................282
10.4.2应用案例——寻找猫咪的最短路径.................................................................283
10.5广度优先搜索算法........................................................................................................286
10.5.1广度优先搜索算法介绍.....................................................................................286
10.5.2广度优先搜索算法的应用案例.........................................................................287
习题............................................................................................................................................290
1.1Dijkstra算法简介.........................................................................................1
1.1.1背景与历史.................................................................................................1
1.1.2应用领域与典型场景..................................................................................2
1.2Dijkstra算法的核心思想..............................................................................2
1.2.1Dijkstra算法的实现步骤...........................................................................2
1.2.2Dijkstra算法图的表示方法.......................................................................3
1.3Dijkstra算法的应用案例..............................................................................4
1.3.1交通网络中的最短路径规划.......................................................................4
1.3.2在机器人导航系统中的应用.......................................................................5
1.4Dijkstra算法的局限性与改进.......................................................................7
1.4.1负权边问题.................................................................................................7
1.4.2大规模图的计算效率..................................................................................9
1.5综合实战——游戏地图中的最短路径规划...................................................10
1.5.1项目介绍.....................................................................................................10
1.5.2构建Graph..................................................................................................10
1.5.3具体实现......................................................................................................11
习题..........................................................................................................................12
第2章A*算法......................................................................................................14
2.1A*算法简介....................................................................................................14
2.1.1背景与历史...................................................................................................14
2.1.2应用领域与典型场景....................................................................................15
2.2A*算法的核心思想.........................................................................................15
2.2.1A*算法的原理和实现步骤...........................................................................15
2.2.2选择启发式函数（估算函数）......................................................................17
2.3A*算法的优化..................................................................................................18
2.3.1基本的优化措施.............................................................................................18
2.3.2HybridA*算法优化...............................................................................................20
2.4A*算法的应用案例...........................................................................................................22
2.4.1游戏开发中的路径规划.........................................................................................22
2.4.2在机器人导航系统中的应用.................................................................................23
习题..............................................................................................................................................38
第3章Bellman-Ford算法...............................................................................39
3.1Bellman-Ford算法介绍......................................................................................................39
3.1.1背景与历史.............................................................................................................39
3.1.2应用领域与典型场景.............................................................................................40
3.1.3Bellman-Ford算法与其他路径规划算法的对比..................................................41
3.1.4图的表示方法.........................................................................................................42
3.2Bellman-Ford算法的应用案例..........................................................................................42
3.2.1解决负权边的最短路径问题.................................................................................43
3.2.2在网络流量优化中的应用.....................................................................................44
3.2.3在自动驾驶路径规划中的应用.............................................................................44
3.3Bellman-Ford算法的局限性与改进..................................................................................46
3.3.1负权回路的处理.....................................................................................................46
3.3.2大规模图的计算效率.............................................................................................47
3.4综合实战——路线导航.....................................................................................................47
3.4.1项目背景.................................................................................................................48
3.4.2问题介绍.................................................................................................................49
3.4.3具体实现.................................................................................................................50
3.4.4调试运行.................................................................................................................53
3.5综合实战——基于FlaskWeb的路径规划可视化..........................................................55
3.5.1项目介绍.................................................................................................................56
3.5.2路径规划（1）.......................................................................................................56
3.5.3路径规划（2）.......................................................................................................59
3.5.4模板文件.................................................................................................................61
3.5.5脚本文件.................................................................................................................62
习题..............................................................................................................................................65
第4章Floyd-Warshall算法............................................................................66
4.1Floyd-Warshall算法简介...................................................................................................66
4.1.1背景与历史.............................................................................................................67
4.1.2应用领域与典型场景.............................................................................................67
4.2Floyd-Warshall算法的核心思想.......................................................................................68
4.2.1图的表示方法.........................................................................................................68
4.2.2Floyd-Warshall算法的推导过程............................................................................69
4.2.3Floyd-Warshall算法与其他路径规划算法的对比................................................70
4.3Floyd-Warshall算法的应用案例.......................................................................................71
4.3.1航空线路规划.........................................................................................................71
4.3.2城市交通规划应用.................................................................................................72
4.4Floyd-Warshall算法的局限性与改进...............................................................................74
4.4.1算法复杂度与大规模图的挑战.............................................................................74
4.4.2负权回路的处理策略.............................................................................................75
4.5综合实战——无人驾驶领域的路径规划系统（出租车/运输车）..............................76
4.5.1背景介绍.................................................................................................................76
4.5.2键值对映射模板.....................................................................................................77
4.5.3城市编号.................................................................................................................79
4.5.4红黑树数据结构和迭代器.....................................................................................80
4.5.5栈数据结构.............................................................................................................95
4.5.6迭代器接口.............................................................................................................97
4.5.7图结构.....................................................................................................................97
4.5.8车费信息.................................................................................................................98
4.5.9路径规划.................................................................................................................98
4.5.10收费信息.............................................................................................................102
4.5.11入口函数.............................................................................................................103
习题............................................................................................................................................104
第5章Floyd算法.........................................................................................105
5.1Floyd算法简介.................................................................................................................105
5.1.1背景与历史...........................................................................................................106
5.1.2Floyd算法和Floyd-Warshall算法的关系..........................................................106
5.1.3Floyd算法和Floyd-Warshall算法的区别..........................................................106
5.1.4应用领域与典型场景...........................................................................................107
5.2Floyd算法的核心思想.....................................................................................................107
5.2.1Floyd算法的原理和实现步骤.............................................................................107
5.2.2Floyd算法的计算过程.........................................................................................108
5.3Floyd算法的改进.............................................................................................................111
5.3.1通过空间优化来减少内存消耗...........................................................................111
5.3.2并行化优化...........................................................................................................112
5.4综合实战——校内机器人配送系统...............................................................................114
5.4.1项目介绍...............................................................................................................114
5.4.2具体实现...............................................................................................................115
习题............................................................................................................................................121
第6章D*算法..............................................................................................123
6.1动态路径规划算法简介...................................................................................................123
6.1.1静态路径规划算法和动态路径规划算法...........................................................124
6.1.2动态路径规划算法的背景...................................................................................124
6.1.3应用领域与场景...................................................................................................124
6.1.4常用的动态路径规划算法...................................................................................125
6.2D*算法介绍.....................................................................................................................125
6.2.1背景与历史...........................................................................................................126
6.2.2D*算法的原理和实现步骤.................................................................................126
6.2.3D*算法总体流程及与A*算法的对比...............................................................127
6.2.4D*算法的常用概念及函数.................................................................................127
6.3D*算法的应用案例.........................................................................................................128
6.3.1帮助探险家寻找最短路径...................................................................................128
6.3.2迷宫中的D*算法探索与动态障碍物处理........................................................138
6.3.3探索机器人的新家...............................................................................................146
6.4综合实战——基于D*算法的动态路径规划可视化系统............................................155
6.4.1项目介绍...............................................................................................................155
6.4.2D*算法功能的声明.............................................................................................156
6.4.3D*算法功能的实现.............................................................................................157
6.4.4主程序...................................................................................................................165
习题.................................................................................................................................168
第7章D*Lite算法........................................................................................................169
7.1D*Lite算法简介.......................................................................................................169
7.1.1背景与历史...........................................................................................................169
7.1.2应用领域与场景...................................................................................................170
7.2D*Lite算法的核心思想...........................................................................................171
7.2.1基本思想...............................................................................................................171
7.2.2D*Lite算法的实现步骤.......................................................................................171
7.3综合实战——可视化的D*Lite路径规划系统.........................................................172
7.3.1项目介绍...............................................................................................................172
7.3.2运算符重载...........................................................................................................173
7.3.3优先队列...............................................................................................................174
7.3.4实现D*Lite路径规划算法..................................................................................178
7.3.5绘制地图...............................................................................................................186
7.3.6主程序...................................................................................................................189
7.3.7编译运行...............................................................................................................191
7.4综合实战——智能路径导航系统.............................................................................192
7.4.1项目介绍...............................................................................................................192
7.4.2环境的建模和初始化...........................................................................................193
7.4.3实现D*Lite路径规划算法..................................................................................195
7.4.4可视化界面...........................................................................................................203
7.4.5主程序...................................................................................................................210
7.4.6调试运行...............................................................................................................211
习题..................................................................................................................................212
第8章基于A*算法变种的动态规划算法......................................................213
8.1A*算法的变种................................................................................................................213
8.2IncrementalA*算法........................................................................................................214
8.2.1IncrementalA*算法介绍......................................................................................214
8.2.2IncrementalA*算法的实现步骤..........................................................................215
8.3DynamicA*算法.............................................................................................................216
8.3.1DynamicA*算法介绍..........................................................................................216
8.3.2应用领域与场景...................................................................................................217
8.3.3DynamicA*算法的实现步骤..............................................................................217
8.3.4DynamicA*算法和D*算法的区别...................................................................219
习题.................................................................................................................................219
第9章RRT算法...........................................................................................220
9.1RRT算法介绍..........................................................................................................220
9.1.1机器人运动规划介绍...........................................................................................220
9.1.2改进的RRT算法..................................................................................................222
9.1.3与RRT算法相关的概念......................................................................................222
9.2RRT算法的定义与实现..........................................................................................223
9.2.1RRT算法的实现步骤...........................................................................................223
9.2.2原始的RRT算法..................................................................................................224
9.2.3基于概率P的RRT算法.....................................................................................225
9.2.4RRT_Connect算法...............................................................................................226
9.2.5RRT*算法.............................................................................................................227
9.3综合实战——机器人路径规划和轨迹优化系统..........................................................231
9.3.1项目介绍...............................................................................................................231
9.3.2实现RRT*算法....................................................................................................232
9.3.3生成加速度轨迹...................................................................................................241
9.3.4主程序...................................................................................................................248
9.3.5MATLAB可视化..................................................................................................249
9.4综合实战——基于pygame的RRT*路径规划系统....................................................250
9.4.1项目介绍...............................................................................................................250
9.4.2通用文件...............................................................................................................250
9.4.3事件处理...............................................................................................................252
9.4.4点处理...................................................................................................................253
9.4.5碰撞检测...............................................................................................................254
9.4.6绘图操作...............................................................................................................254
9.4.7RRT算法...............................................................................................................256
9.4.8主程序...................................................................................................................258
习题................................................................................................................................259
第10章优先级遍历算法...............................................................................260
10.1优先级遍历算法简介...............................................................................................260
10.1.1背景与历史.........................................................................................................260
10.1.2路径规划应用中的优先级遍历算法.................................................................261
10.2最佳优先搜索算法................................................................................................262
10.2.1最佳优先搜索算法的基本思想.........................................................................262
10.2.2最佳优先搜索算法的实现步骤.........................................................................262
10.2.3应用案例——寻找两个城市之间的最短路径.................................................265
10.3均匀代价搜索算法.........................................................................................................273
10.3.1均匀代价搜索算法的基本思想.........................................................................273
10.3.2均匀代价搜索算法的应用案例.........................................................................274
10.4深度优先搜索算法.........................................................................................................282
10.4.1深度优先搜索算法介绍.....................................................................................282
10.4.2应用案例——寻找猫咪的最短路径.................................................................283
10.5广度优先搜索算法........................................................................................................286
10.5.1广度优先搜索算法介绍.....................................................................................286
10.5.2广度优先搜索算法的应用案例.........................................................................287
习题............................................................................................................................................290
