最近好多人问我关于基于栅格的蚁群算法机器人路径规划中的G2D邻接矩阵的问题，一一解释把我给累的，于是就想在此大概说一下。
首先要明白一点，在栅格地图中，每一个栅格相当于一个节点；而在一条路径中，各个栅格是相邻的。比如一个4*4栅格，如下
对任意一条路径，比如1-2-7-11-16，它每一个节点对应的栅格是相邻的，即栅格1和栅格2是相邻的，栅格2和栅格7 是相邻的，栅格7和栅格11是相邻的……
也就是说这里路径永远不能是1-3或者2-11或者1-16这种不相邻的。
好了，上面说的是针对一个没有障碍的栅格地图，对于有障碍的地图，障碍栅格和任何栅格都不相邻。如下图，假设7和10号栅格是障碍，认为6和7是不相邻的，6和10不相邻等。
因此我们定义邻接矩阵D，邻接矩阵D就是每个栅格之间的距离。对于上述4*4矩阵，有16个栅格，那么每一个栅格到其他所有（15个）栅格，就得到15个距离。且我们一般算上自己到自己的距离。这样每个栅格到其他栅格的距离就有16个，于是便形成了16*16的矩阵，到这里明白吗？
对于上述障碍栅格地图，邻接矩阵D是16*16的矩阵，为了更好的理解，在此我们用可行性来代替距离，即0表示两个栅格不相邻，即不可行，1表示两个栅格相邻，即可行，且规定自己到自己的为不可行。这个和距离正好成倒数关系，即0表示距离为无穷大，1表示单位距离，如D的第一行表示栅格1到其他各栅格的可行性如下
栅格 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0
栅格6到其他栅格的可行性如下。
栅格 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
6 1 1 1 0 1 0 0 0 1 0 1 0 0 0 0 0
其中7和10与栅格6不可行是以为7和10是障碍栅格，其他不可行是因为二者不相邻。
用上面方法可以分别得到栅格1~栅格16到其他栅格的可行性，得到16*16的邻接矩阵。
好说到这，有些人可能会说和他见过的邻接矩阵不太一样，那么下面就说一下几种情形。
第一，“相邻”有不同的定义，有的是“十字相邻”，即栅格和它的正上/正下/正左/正右的4个栅格相邻，如图1无障碍栅格地图中的栅格6，设定它只与2、5、7、10四个栅格相邻；有的是“米字相邻”，即栅格和它周围一圈8个栅格都相邻，即无障碍地图中的栅格6 与1、2、3、5、7、9、10、11相邻。
根据自己的不同要求可以得到不同的邻接矩阵。
第二，上面只是说了可行性矩阵，即该矩阵为0-1矩阵。但是在蚁群算法实际使用时还是要使用距离，此时0表示不可行，距离为无穷大，1表示可行，表示单位距离，所有需要将上述的可行性矩阵取倒数。
以上只是介绍了邻接矩阵的定义和意义，而在MATLAB蚁群算法求栅格法机器人路径规划中怎么编程呢，很多人都有这个邻接矩阵的程序G2D.m，可能有些人看不懂。在此我只点拨一下，编程时注意
1. 求边角栅格邻接矩阵时程序的处理；
2. 注意邻接的定义，十字？米字？以及具体怎么实现的相邻定义
3. 注意时怎么定义相邻栅格的距离
好啦，就说到这！
首先要明白一点，在栅格地图中，每一个栅格相当于一个节点；而在一条路径中，各个栅格是相邻的。比如一个4*4栅格，如下
对任意一条路径，比如1-2-7-11-16，它每一个节点对应的栅格是相邻的，即栅格1和栅格2是相邻的，栅格2和栅格7 是相邻的，栅格7和栅格11是相邻的……
也就是说这里路径永远不能是1-3或者2-11或者1-16这种不相邻的。
好了，上面说的是针对一个没有障碍的栅格地图，对于有障碍的地图，障碍栅格和任何栅格都不相邻。如下图，假设7和10号栅格是障碍，认为6和7是不相邻的，6和10不相邻等。
因此我们定义邻接矩阵D，邻接矩阵D就是每个栅格之间的距离。对于上述4*4矩阵，有16个栅格，那么每一个栅格到其他所有（15个）栅格，就得到15个距离。且我们一般算上自己到自己的距离。这样每个栅格到其他栅格的距离就有16个，于是便形成了16*16的矩阵，到这里明白吗？
对于上述障碍栅格地图，邻接矩阵D是16*16的矩阵，为了更好的理解，在此我们用可行性来代替距离，即0表示两个栅格不相邻，即不可行，1表示两个栅格相邻，即可行，且规定自己到自己的为不可行。这个和距离正好成倒数关系，即0表示距离为无穷大，1表示单位距离，如D的第一行表示栅格1到其他各栅格的可行性如下
栅格 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0
栅格6到其他栅格的可行性如下。
栅格 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
6 1 1 1 0 1 0 0 0 1 0 1 0 0 0 0 0
其中7和10与栅格6不可行是以为7和10是障碍栅格，其他不可行是因为二者不相邻。
用上面方法可以分别得到栅格1~栅格16到其他栅格的可行性，得到16*16的邻接矩阵。
好说到这，有些人可能会说和他见过的邻接矩阵不太一样，那么下面就说一下几种情形。
第一，“相邻”有不同的定义，有的是“十字相邻”，即栅格和它的正上/正下/正左/正右的4个栅格相邻，如图1无障碍栅格地图中的栅格6，设定它只与2、5、7、10四个栅格相邻；有的是“米字相邻”，即栅格和它周围一圈8个栅格都相邻，即无障碍地图中的栅格6 与1、2、3、5、7、9、10、11相邻。
根据自己的不同要求可以得到不同的邻接矩阵。
第二，上面只是说了可行性矩阵，即该矩阵为0-1矩阵。但是在蚁群算法实际使用时还是要使用距离，此时0表示不可行，距离为无穷大，1表示可行，表示单位距离，所有需要将上述的可行性矩阵取倒数。
以上只是介绍了邻接矩阵的定义和意义，而在MATLAB蚁群算法求栅格法机器人路径规划中怎么编程呢，很多人都有这个邻接矩阵的程序G2D.m，可能有些人看不懂。在此我只点拨一下，编程时注意
1. 求边角栅格邻接矩阵时程序的处理；
2. 注意邻接的定义，十字？米字？以及具体怎么实现的相邻定义
3. 注意时怎么定义相邻栅格的距离
好啦，就说到这！
