开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 图论、图搜索算法 -> 正文阅读

[数据结构与算法]图论、图搜索算法

基础概念

配置空间、工作空间

机器人配置（Robot Configuration）：对机器人上所有点的位姿描述
机器人自由度（Robot Degree Of Freedom, DOF）：描述机器人路径规划的最少坐标数量 $n$ 。
机器人配置空间（Robot Configuration Space, C-Space）：包含机器人所有可能位姿的 $n$ 维空间
机器人位姿在配置空间中假定为一个点
机器人工作空间（Robot Workspace）：机器人实际工作的复杂环境

障碍物、运动规划

机器人具有不同的形状、尺寸大小，障碍物（Obstacle）的碰撞检测需要了解机器人的形状、大小等属性，较为复杂：

在这里插入图片描述

故而，一般在配置空间中做机器人的路径规划问题。已知机器人位姿在配置空间C-space中假定为一个点，例如欧氏空间下的机器人位姿可使用 $\Re^{3\times3}\in SO(3)$ 进行表示。则可将障碍物进行膨胀得到配置空间中的障碍物（C-Obstacle），若机器人所在点不落在C-Obstacle范围内，则判定机器人处于自由状态下，不会被碰撞：C-Free。

在这里插入图片描述

配置空间由障碍物及自由空间组成： $(C-Space)=(C-Obstacle)\cup(C-Free)$

移动机器人的运动规划是在机器人的起点 $q_{start}$ 到机器人的目标点 $q_{goal}$ 之间，处于 $C ? F r e e$ 空间中的规划。

图搜索（Graph Search Basis）

图（Graphs）

图是一种由节点（Nodes）和边（Edges）构成的抽象网络，网络中各个节点由边进行连接，表明两节点存在关系。

在这里插入图片描述

节点（Node）

节点表示某个事物或对象，如上图中各个带字母的点。

边（Edge）

边表示事物与事物间的逻辑关系，如上图中两节点间的绿线。

同构（Isomorphism）

同构的两张图具有相同的节点及节点间连接的边，同构图仅存在画法的不同，但包含的逻辑关系不变。

在这里插入图片描述

有向图（Directed Graph）、无向图（Undirected Graph）

无向图的边没有方向，而有向图的边具有方向性。

在这里插入图片描述

如上图，有向图的方向如下： $D\to A\to G$ 、 $D\to C\to E$ 、 $B\to A\to G$ 、 $B\to C\to E$ 、 $B\to F\to E$

权重（Weight）

图上的边具有权重值，每条边的权重可以不同，表示由一个节点至另一个节点的代价值。如下图由节点 $A$ 到节点 $G$ 的权重值为4。

在这里插入图片描述

路径（Path）、最优路径（Shortest Path）

图上任取两点作为起点与目标点，由起点到目标点，不经过重复节点和边的路线称为路径。由起点到目标点最短的路径称为最优路径，在选择最优路径时往往需要考虑边的权值。

图搜索（Search-based Method ）

对图结构进行搜索，从起始节点 $S$ 到目标节点 $G$ ，将生成一个搜索树：

在这里插入图片描述

通常，构建一个完整的搜索树结构，所需要的代价很高。图搜索算法的基本逻辑如下：
$\begin{aligned} &1:维护一个用于存储所有被访问节点的容器\\ &2:容器内初始值为起点X_s\\ &3:开始循环Loop\\ &4:\qquad访问节点：根据预先定义的评分函数（Score\:Function）从容器中取出一个节点\\ &5:\qquad扩展节点：获得该节点的所有邻居节点\\ &6:\qquad置入节点：将获得的邻居节点置入容器\\ &7:结束循环End \end{aligned}$
循环结束条件一般置为抵达目标节点，或容器中所有节点被弹出，容器为空。

广度优先搜索（Breadth First Search, BFS）

广度优先算法基于队列（Queue）进行，遵从于先进先出的原则进行：

在这里插入图片描述

举例说明如下：

在这里插入图片描述

广度优先搜索搜先从起点节点 $s$ 开始，首先弹出节点 $s$ ，得到三个邻居节点 $d 、 e 、 p$ 并置入容器中；随后弹出其中一个节点 $p$ ，得到其邻居节点 $q$ 置入容器；其次，再弹出一个节点 $e$ 并将其邻居节点 $h 、 r$ 置入容器；周而复始，弹出 $d$ 并将其邻居节点 $b 、 c 、 e$ 置入容器……知道搜索到目标为止。

应注意，对于邻居节点置入容器的顺序需要被确立，如从左到右置入、顺时针置入等方式。

深度优先搜索（Depth First Search, DFS）

深度优先搜索基于堆栈（Stack）进行，遵从于后进先出原则进行：

在这里插入图片描述

举例说明如下：

在这里插入图片描述

首先，从起点节点 $s$ 开始搜索，弹出节点 $s$ 后，得到邻居节点 $d 、 e 、 p$ 并将其置入容器；随后，弹出节点 $d$ 得到其邻居节点 $b 、 c 、 e$ 置入容器；周而复始，弹出 $b$ 得到邻居节点 $a$ 置入容器后，发现对 $a$ 进行搜索无邻居节点，故而再一次弹出节点 $c$ 得到其邻居节点 $a$ ，同样无邻居节点并再次弹出 $e$ ……直到抵达目标节点 $G$ 时离开循环。