本任务的目的是简化上述问题被解决。 这些简化会影响问题的三个方面：
•地图的细分：任务中的地图将由四个具有相同尺寸的矩形组成。 在实际应用中，部分卡具有不同的尺寸，这使实现变得非常复杂（请参见图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并未对此提出质疑。但是，我强烈推荐这样的功能对自己的运动进行编程。