本任务的目的是简化上述问题被解决。 这些简化会影响问题的三个方面:
•地图的细分:任务中的地图将由四个具有相同尺寸的矩形组成。 在实际应用中,部分卡具有不同的尺寸,这使实现变得非常复杂(请参见图1)。
路径而不是路径:在此任务中,仅路径长度应确定,而不是路径是。 这具有关键优势,即您已经具备执行此操作所需的技术在编程任务6和7。 但是,这并不意味着此任务基于后者(请参阅下一点)。
•限制部分实施:它们成为程序代码的一部分得到提供。您的工作将受到精确的指示¨填补程序中的空白。 ¨可以在另一个层次上进行处理。面向对象的范式编程将使您能够以有意义的方式构造复杂的程序。
更高级的算法和数据结构(例如,使用¨的最短路径搜索Dijkstra算法)可让您更有效地解决此处描述的子问题更优雅地解决。
3.1路径查找算法示意图
可以找到最短路线的地图包括四个子地图,分别是它们以PA07格式存储在文本文件中。确定算法以下基本构建块具有许多最短的路径:
•从上述文本文件中提取部分卡片。
•根据以下配方为每个子卡创建无向图:每个字段“ P”节点vi表示在局部图的边缘,为了简化符号我们用它们代表的节点来标识字段。对每一对vi,i=! j的vj加上边¨(vi,vj)如果在里面子图在两者之间有一条路径。边缘的重量就是长度两个节点之间的最短路径。 ¨
•局部图的节点对应于局部图之间的过渡。通过识别在过渡点中,子图可以组合成单个图¨G。解决所有对最短路径(APSP)问题并保存解决方案。给定起点s和终点t不在同一局部图中,将G添加到节点s和t。 (如果它们在同一子图上,请计算令v1,…,vk为G中G的节点。包含的子卡。 如果在s和vi之间存在路径,则添加一条边(s,vi)在存在包含s的部分映射。 选择最短的长度¨作为边缘权重s和vi之间的路径,类似地进行。
•在图表中确定,并借助所存储的有关以下信息的补充¨G中最短路径的长度s和t之间最短路径的长度。
4. 要求
您将收到文件PA13solution_Students.py。 这包含了该问题的解决方案,从中部分或全部删除了某些功能。该文件包括三个部分-主要部分和具有辅助功能的两个部分通过注释与主体分开。 辅助功能已完成。 所有差距都是在文件正文中。 现在,我们进入这部分的功能。 功能完成标记有星号
4.1生成不同图形的函数
•extractPartialMaps()此辅助函数从文本文件students.in中提取部分卡。部分卡的每一行都显示在值U的字符串列表中或P字段。子图将另存为此类列表的列表。返回值¨该功能是部分卡的列表。第一张子卡的左上角元素 然后,例如,partialMaps [0] [0] [0]-其中,partialMaps是对象的名称部分卡列表是。部分卡按照以下方案编号:
-左上:partialMaps [0]。
-右上:partialMaps [1]。
-左下:partialMaps [2]。
-右下:partialMaps [3]。
所有部分卡的尺寸始终为7行10列。关于坐标转换的注意事项:相邻局部地图的边缘彼此认同。也就是说,例如,在整个地图中,partialMaps [0] [0] [9]和partialMaps [1] [0] [0]是相同的字段。
•verticesFromMaps(partialMaps)*接受部分地图列表的列表。为每个局部图确定包含字符串¨P的边缘字段。这些将是格式
(行索引,列索引)归档在列表中。以这种方式编译的列表成为allVertices的列表汇总并从函数返回。 ¨
•edgesFromMaps(partialMaps,allVertices)∗对于每个局部地图¨partialMaps[i]
执行以下操作:对于所有对元组¨vj,allVertices [i]中的vk,在vj =! vk的情况下,确定partialMaps [i]中的vj和vk之间是否存在路径。如果是这样,信息将以以下格式显示在列表中(加权边)部分地图partialMaps [i]对应的图的形式:[v_j,v_k,路段长度]
该函数返回加权边列表的allEdges列表。 ¨•generateTopVertices(partialMapsVertices)生成节点的列表。图G。我们将G称为顶部图。节点以相同的格式存储,从generateTopVertices函数开始。第一次是从¨局部图中的考虑发生在整个图中。这意味着特别是将部分地图坐标转换为整个地图中的坐标是。为此使用了两个函数vertexShiftUp和vertexShiftDown在PA13solution_Students.py的辅助功能部分中。另外,应注意,由于上述识别,所有节点出现两次。这些重复项必须清除。 ¨•generateTopEdges(partialMapsEdges)*从加权列表生成partialMapsEdges中的Edges以相同格式返回TopGraph的加权边的topEdges列表,并返回它们。坐标偏移可以像¨上面提到的,可以通过辅助功能vertexShiftUp实现。必须遵守以下约定:令[v,w,weight]为列表中的一条边。然后,应按对列表[v,w]排序的顺序存储v,w排序()的结果。列表中条目的其余排序是由预定义的代码段。•generateTopMatrix(topVertices,topEdges)*返回TopGraph的邻接矩阵。矩阵以行列表的形式给出,每行又是一个¨清单是。由于顶部图是无向的,因此矩阵是对称的。遵循约定
请注意:
-与节点v对应的行或列索引应与该索引相同节点v在topVertices列表中的索引。函数elemIndex在辅助功能部分
-列表topEdges可以包含双边。在这种情况下,较低的可以在矩阵中输入重量值。
-如果两个节点没有通过边连接,则相应的字段输入的字符串“ inf”。一种可能的步骤是使用辅助功能截面矩阵中的infMatrix(n)可对n×n矩阵进行“ inf”运算,生成条目,然后在给定的topEdges中的边上用适当的边缘粗细替换“ inf”的字段。-所有对角线条目均设置为0。
4.2全对最短路径
您已经了解了PA06中的最小加矩阵乘法。对于(对称¨具有正边权重的无向图G =(V,E)的Sche)邻接矩阵A适用以下条件:令d为正整数,因此Ad = Ad + 1 =:B。那是B的入口bij是G中¨vi和vj之间最短路径的长度。数字d存在总是小于或等于图G的节点数。•allPairsShortestPath(adjacencyMatrix)*接受邻接矩阵并返回路径最短的矩阵。返回的矩阵具有相同的¨格式类似于adjacencyMatrix,但不会覆盖它。
4.3添加起点和终点
现在,我们正在寻找整个地图中两个字段s和t之间的最短路径。该有趣的情况是s和t不在同一个子卡中。在这种情况下,本节的功能实现以下过程:
•令K为s所在的部分牌。对于每个字段¨v,其内容“ P”位于K的边缘检查在K中是否有从s到所述字段的路径。如果是这样,请添加加权¨边缘[s,v,从s到v的长度最短路径]将sEdges添加到列表中。进行模拟程序。
•如上所述,令allPairs为在顶部图中显示最短路径的矩阵。已注册。所有对的尺寸均为n×n。布置新矩阵尺寸为(n + 2)×(n + 2)的newAllPairs,将allPairs嵌入到左上n×n子矩阵中,并用¨填充剩余的两行/列来自sEdge和tEdge的信息。
•让我成为topVertices中不以s开头的节点的索引集,也不是t已连接。对于所有¨i,我删除具有索引i的行和列newAllPairs。
•再次解决APSP问题,以减少¨newAllPairs。倒数第二个进入最后一行(也是最后一列的倒数第二个条目)是最短长度¨s和t之间的路径。所描述的过程使用以下功能实现:
•generateAdjoiningEdges(顶点,allPartialMaps,allVertices)取一个上面介绍的格式的Card字段,以及所有部分卡和部分卡节点反对。返回加权边列表以完成顶部图形。 ¨加权边具有以下格式:
[顶点,顶部图中的节点,边缘权重]
•adjoinEdgesToMatrix(sEdges,tEdges,adjMatrix,topVertices)*实现上面第二点中描述的矩阵newAllPairs的生成。分配索引节点可以依次使用elemIndex。它具有adjMatrix尺寸n×n。然后,来自sEdges的信息应该在第(n + 1)列中在第(n + 2)列中嵌入索引n和来自tEdges的信息索引为n + 1。传递的邻接矩阵不应是要返回的矩阵¨矩阵newAllPairs可以被覆盖。 ¨•extractSubmatrix(矩阵,索引)∗删除¨索引中所有索引的矩阵中相应的行和列。将简化后的矩阵作为返回值。 ¨
4.4综合
理想情况下,您应该能够将所描述的子功能转换为一个功能synthPath(S,T,部分地图,partMapVertices,topVertices,allPairsMatrix)返回值是最短¨s t路径的长度。这将但Comajudge并未对此提出质疑。但是,我强烈推荐这样的功能对自己的运动进行编程。