C++
作业 1(8 月 18 日前完成) 1.1Overview
In this assignment you will implement a simplified algorithm for Path Planning, and use it with a simple simulated 2D robot moving around a room.
在这个作业中，您将实现一个简化的路径规划算法，并将其与一个简单的模拟二维机器人一起在房间
内移动。
In this assignment you will:
在本作业中，您将:
• Practice the programming skills covered throughout this course, such as: 练习本课程所涵盖的编程技能，例如:
– Pointers 指针
– Dynamic Memory Management 动态内存管理 – Provided API 提供的 API
• Correctly Implement a pre-defined API 正确实现预定义的 API
• Implement a medium size C++ program 实现一个中等大小的 C++程序
• Use a prescribed set of C++11/14 language features 使用规定的 C++ 11/14 语言特征集
This assignment is divided into four Milestones: 此作业分为四个里程碑:
• Milestone 1: Writing Unit Tests
编写单元测试
• Milestone 2: Minimum required component for implementing a simple Grid Search 实现简单网格搜索所需的最小组件
• Milestone 3: Optional component to extend the search for a simplified path planner 扩展搜索简化路径规划器的可选组件
• Milestone 4: Optional component for efficient memory management 高效内存管理的可选组件
1.2 Relevant Lecture/Lab Material 相关讲座/实验材料
To complete this assignment, you will require skills and knowledge from lecture and lab material for Weeks 2
to 4 (inclusive).
要完成这项作业，你需要在第 2 至第 4 周(包括第 2 至第 4 周)内从课堂和实验材料中获得技能和知 识。
1.3 Start-up Code
You will find starter code to help you get running with the assignment. This code includes:
您将找到有助于运行作业的启动程序代码。此代码包括:
• Header files, of the API (C++ classes) that you will implement 将执行的 API(C++类)的头文件
• Dummy (empty) code files, for you to implement 虚拟(空)代码文件，供您实现
• Unit Testing code, to help you write and run tests on your implementation 单元测试代码，帮助您编写和运行实现测试
• Example Unit Test case(s)
单元测试用例示例
Page 1 of 10
2. Learning Outcomes
This assessment is relevant to the following Learning Outcomes:
此作业与以下学习成果相关:
1. Analyse and Solve computing problems; Design and Develop suitable algorithmic solutions using software concepts and skills both (a) introduced in this course, and (b) taught in pre-requisite courses; Implement and Code the algorithmic solutions in the C++ programming language.
分析和解决计算问题，设计和开发合适的算法解决方案，使用软件概念和技能(a)在本课程中
介绍，和(b)在必修课程中教授;在 C++程序设计语言中实现和编码算法解决方案。
2. Discuss and Analyse software design and development strategies; Make and Justify choices in software design and development; Explore underpinning concepts as related to both theoretical and practical applications of software design and development using advanced programming techniques.
讨论和分析软件设计和开发策略;做出和证明软件设计和开发的选择;使用先进的编程技术探
索与软件设计和开发的理论和实践应用相关的基础概念。
3. Discuss, Analyse, and Use appropriate strategies to develop error-free software including static code analysis, modern debugging skills and practices, and C++ debugging tools.
讨论、分析和使用适当的策略来开发无差错软件，包括静态代码分析、现代调试技巧和实践，
以及 C++调试工具。
4. Implement small to medium software programs of varying complexity; Demonstrate and Adhere to good programming style, and modern standards and practices; Appropriately Use typical features of the C++ language include basic language constructs, abstract data types, encapsulation and polymorphism, dynamic memory management, dynamic data structures, file management, and managing large projects containing multiple source files; Adhere to the C++11/C++14/C++17 ISO language definition and features.
实现不同复杂度的中小型软件程序;演示并坚持良好的编程风格和现代标准和实践;适当使用 C++语言的典型特征，包括基本语言结构、抽象数据类型、封装和多态性;动态内存管理、动态 数据结构、文件管理和管理包含多个源文件的大型项目;坚持 C++ 11/C++ 14/C++ 17 的 ISO 语言定义和特性。
5. Demonstrate and Adhere to the standards and practice of Professionalism and Ethics, such as described in the ACS Core Body of Knowledge (CBOK) for ICT Professionals.
证明并遵守职业精神和道德标准和实践，如美国通信与通信技术专业人员协会核心知识体系 (CBOK)所述。
3.Assessment details 作业细节
One challenge in robotics is called path planning. This is the process of the robot figuring out how to navigate between two points within some environment. In this assignment you will implement a simplified path planning problem for a robot moving about a simple 2D maze.
机器人学的一个挑战是路径规划。这是机器人在某个环境中计算如何在两个点之间导航的过程。在这
个作业中，你将为一个在简单的二维迷宫中移动的机器人实现一个简化的路径规划问题。
In this assignment, the simple 2D maze will be represented as a grid of ASCII characters. For example:
在这个作业中，简单的二维迷宫将被表示为一个 ASCII 字符网格。例如:
~~~~~~~~~~~~~
~………..~
~=======.===~
~..=…=….~
~..=…..=..~
~..=..=..=..~
~~~~~~~~~~~~~
Aspects of the maze are represented by different symbols:
迷宫的各个方面用不同的符号表示:
Symbol Meaning
Empty/Open Space. The robot can enter any open space. . (dot) 空/开放空间。机器人可以进入任何开放空间。
Wall or Obstacle within the maze. The robot cannot pass
obstacles
= (equal) 迷宫中的墙或障碍物。机器人不能通过障碍物
The edge of the maze. Every maze is always bounded by the edge symbols
~ (tilda) 迷宫的边缘。每一个迷宫都有边界符号
Each location in the maze (including the maze edges) is indexed by a cartesian (x,y) co-ordinate. The top-left corner of the maze is always the co-ordinate (0,0), the x-coordinate increases right-wards, and the y-coordinate increases down-wards. For the above maze, the four corners have the following co-ordinates:
迷宫中的每个位置(包括迷宫边缘)都由笛卡尔坐标(x，y)编制索引。迷宫的左上角始终是坐标 (0,0)，X 坐标向右增加，Y 坐标向下增加。对于上述迷宫，四个角具有以下坐标:
For the purposes of this assignment we will make two important assumptions:
在本作业中，我们将作出两个重要假设:
1 The robot knows the map of the whole maze 机器人知道整个迷宫的地图。
2 It may not be possible for the robot to reach every empty space 机器人可能无法到达每一个空位。
For this assignment, the robot:
对于这个作业，机器人:
• May only be located at cells with empty spaces. 只能位于有空位的单元。
• The robot can move to any one of 4 cells, that are to the left, right, up, or down from the robots originating cell.
机器人可以移动到 4 个单元中的任意一个，即从机器人原始单元向左、向右、向上或向下移动。 • For this assignment the direction the robot is “facing” is ignored.
对于这项作业，机器人“朝向”的方向将被忽略。
Page 2 of 10
(0,0)
.
.
(12,0)
.
.
.
.
(0,6)
.
.
(12,6)
! In worked examples, the robot’s position will be marked by a star *. ! 在工作示例中，机器人的位置将用星号*标记。
For example, if the robot is at position (8,2):
例如，如果机器人处于位置(8,2):
then the robot could move to positions (8,1) or (8,3).
然后机器人可以移动到位置(8，1)或(8，3)。 3.1 Reachable Positions 可到达位置
For this assignment, you will develop a simplified path planning solution1. In Milestone 2 you will develop a base algorithm, which can be used in Milestone 3 to develop the path planning algorithm.
对于此作业，您将开发一个简化的路径规划解决方案 1。在里程碑 2 中，您将开发一个基本算法，它可 以在里程碑 3 中用于开发路径规划算法。
The Milestone 2 algorithm, is given the starting position of the robot and calculates:
里程碑 2 算法给出机器人的起始位置，并计算:
• All possible locations that the robot can reach from x
机器人可从 X 到达的所有可能位置
• The number of spaces that each position is from x, which is equivalent to the number of moves the robot
would need to make to reach each position.
每个位置距离 x 的空间数，相当于机器人到达每个位置所需的移动次数。 This algorithm is given below. 下面给出了该算法。
To conduct this algorithm, each position must be annotated by the distance that the position is from the robot’s starting position, x.
为了执行这个算法，每个位置都必须用距离机器人的起始位置 x 来注释。
…
=*=
=..
Pseudocode for Milestone 2: Generate all Reachable Positions 里程碑 2 的伪代码:生成所有可到达位置
Let x be the starting position of the robot with distance 0 设 x 为距离为 0 的机器人的起始位置。 Let P be a list of positions the robot can reach, with distances (initially contains x)
假设 p 是机器人可以到达的位置列表，包括距离(最初包含 x)
Let T be a temporary list (initially empty) 设 T 为临时列表(最初为空) repeat
| Select an item p from P that is not in T 从 P 中选择不在 T 中的项目 P
| foreach Position, q that the robot can reach from p do 前臂位置，机器人可以从 P do 到达的 Q 7 | | Set the distance of q to be one more than the distance of p
| |AddqtoPifandonlyifthereisnoiteminPwiththesameco-ordinateasq
10 | AddptoT 将p添加到T
11 until No such position p can be found 直到找不到这样的位置 P
7、将 q 的距离设置为大于 p 的距离
8、当且仅当 P 中没有与 Q 具有相同坐标的项目时，将 Q 添加到 P 中。
1
2
3
4 5
6
8
9 |end
3.2 Worked Example 工作示例
A worked example of stage 1 is given using the above maze. 利用上述迷宫给出了第 1 阶段的一个实例。
Let us assume that the robot knows the map, and it’s starting position, x, is at co-ordinate (8,2). To help with annotations, the distance that the robot is from the starting position, x will added to the co-ordinate to form a 3- tuple:
假设机器人知道地图，它的起始位置 x 在坐标(8，2)上。为了有助于注释，机器人与起始位置的距 离，X 将添加到坐标中以形成 3 元组:
(
For example, as the distance from the starting location is 0, this gives the tuple: (8,2,0).
例如，由于到起始位置的距离为 0，所以这给出了元组:(8,2,0)。
Initially, P contains the starting location and distance, such that P = [(8,2,0)]. Also initially, the temporary list,
T is empty.
最初，p 包含起始位置和距离，这样 p=[(8,2,0)]。最初，临时列表 t 也是空的。
In the loop, since P contains one item, it is selected, so that p =(8,2,0). Since T does not contain an item with the co-ordinate of p, the loop continues. By looking at the map, it is possible to determine all places from p that the robot can reach:
在循环中，因为 p 包含一个项，所以它被选中，所以 p=(8,2,0)。因为 t 不包含坐标为 p 的项，所以 循环继续。通过查看地图，可以从 P 中确定机器人可以到达的所有位置:
1 This is a simplified algorithm for the purposes of this assignment. There are many variations in literature, so be careful!
这是一个简化的算法，用于本作业。文学作品有很多变种，所以要小心!
Page 3 of 10
…
=*=
=..
,
These are given below. They are also a distance of 1 from the starting position, x, so they form tuples: 以下给出了这些。它们与起始位置 x 的距离也为 1，因此它们形成元组:
1. (8,1,1) 2. (8,3,1)
All of these are added to P, such that: P =[(8,2,0),(8,1,1),(8,3,1)]. Also p is added to T, such that: T =[(8,2,0)]. The loop then repeats.
所有这些都添加到 p 中，这样:p=[(8,2,0)，(8,1,1)，(8,3,1)]另外，p 加在 T,上，这样: In the 2nd iteration of the loop, an item is selected from P. This item may be:
在循环的第二次迭代中，从 P 中选择一个项。此项可以是: 1. (8,1,1)
2. (8,3,1)
since the item (8,2,0) has a co-ordinate that is in T, it is not considered. For this example, the item (8,1,1) is selected so that p =(8,1,1), and the loop continues. By looking at the map, it is possible to determine all places from p that the robot can reach:
由于项目(8,2,0)的坐标为 t，因此不考虑。对于本例，选择项目(8,1,1)，使 P=(8,1,1)，循环继 续。通过查看地图，可以从 P 中确定机器人可以到达的所有位置:
These locates are, with their respective distances: 这些位置及其各自的距离为:
1. (7,1,2) 2. (9,1,2) 3. (8,2,2)
Note that the distance is always one more than the distance in p. The first two are added to P, but the third has a co-ordinate that is already in P, so it is not added. Thus:
请注意，距离总是比 p 中的距离多一个。前两个距离加在 p 中，但第三个坐标已经在 p 中了，所以不 加。因此:
P=[(8,2,0),(8,1,1),(8,3,1),(7,1,2),(9,1,2)].
Also p is added to T, such that: T =[(8,2,0),(8,1,1)] 另外，p 加在 T 上，使得:T =[(8,2,0)，(8,1,1)]
The loop repeats until it is impossible to find an item in P that does not have the same co-ordinate as an item in T. Eventually P contains the list of all positions the robot can reach in the maze and the distance to those positions. These will be all but the squares marked with an x.
循环重复，直到在 P 中找不到与 T 中的项目没有相同坐标的项目为止。最终，P 包含机器人在迷宫中可 以到达的所有位置的列表以及到这些位置的距离。除了标有 X 的正方形外，这些都是。
~~~
.*.
=.=
~~~~~~~~~~~~~
~………..~
~=======.===~
~xx=…=….~
~xx=…..=..~
~xx=..=..=..~
~~~~~~~~~~~~~
The final cost of reaching each co-ordinate (from starting position (8,2) which has a cost of 0) :
到达每个坐标的最终成本(从成本为 0 的起始位置(8,2)):
~~~~~~~~~~~~~
~87654321234~
~=======0===~
~xx=765=1234~
~xx=65432=45~
~xx=76=43=56~
~~~~~~~~~~~~~
Page 4 of 10
,
4. Task
This assignment is divided 4 Milestones. 此作业分为 4 个里程碑。 You must complete these milestones in sequence.
您必须按顺序完成这些里程碑。
4.1 Milestone 1: Unit Tests 里程碑 1:单元测试
Before starting out on implementation, you need to write a series of unit tests, so that you can test if your
implementation is 100% correct.
在开始实施之前，您需要编写一系列单元测试，以便可以测试实现是否 100%正确。 A Unit test consists of three text files: 单元测试由三个文本文件组成:
1.
3.
5.
Your unit tests should be sufficient so that, if all of your unit tests pass, you are confident that your code in 100% correct.
您的单元测试应该足够，这样，如果您的所有单元测试都通过了，您就确信您的代码 100%正确。 The starter code provides sample unit tests to help you get started These example tests are not sufficient. You will need to write your own tests!
starter 代码提供了示例单元测试来帮助您开始这些示例测试还不够。您需要编写自己的测试!
! The starter code provides a simple unit testing wrapper to help run your unit tests. The testing code is executed by: ./test
起始代码提供了一个简单的单元测试包装器来帮助运行单元测试。 测试代码执行人:./test
4.2 Milestone 2: Reachable Positions with Distances 里程碑 2:可到达的位置和距离
Your task is to implement the an API that facilitates the simplified path planning algorithm described in Section
3.1 using three C++ Classes:
您的作业是实现一个 API，该 API 有利于使用三个 C++类在第 3.1 节中描述的简化路径规划算法:
• PostionDistance 位置距离 • PDList
• PathPlanning 路径规划
For each class, you are given the API that you must implement. This API is a set of pre-defined methods on the classes. You are able to add any of your own code, but you must not modify the provided API. In addition to implementing the classes:
对于每个类，都会为您提供必须实现的 API。这个 API 是类上的一组预定义方法。您可以添加自己的 任何代码，但不能修改提供的 API。除了实现类之外:
• You must provide some documentation about your implementation. 您必须提供一些关于您的实施的文档。
• Your code should be well formatted, following the style guide 您的代码应该是格式良好的，遵循样式指南
• Your implementation of the API must comply with the a set of requirements and restrictions. 您的 API 实现必须符合一组要求和限制。
!
You are implementing an API (set of methods), not a full C++ program. To actually run your code,
testing file provided in the starter code. Remember you cannot modify the pre-defined methods!
您正在实现一个 API(一组方法)，而不是一个完整的 C++程序。要实际运行代码，您需要在启动 程序代码中提供单元测试文件。
Page 5 of 10
you will need the unit
4.2.1 PositionDistance Class 位置距离类
The PositionDistance classes represents one co-ordinate (x,y) of the robot within a maze, and the distance of that co-ordinate from the starting position. It has three methods that provide the components of the position of the robot.
PositionDistance 类表示迷宫中机器人的一个坐标(x，y)，以及该坐标与起始位置之间的距离。它 有三种方法来提供机器人位置的组件。
// x-co-ordinate int getX();
// y-co-ordinate int getY();
// Distance
int getDistance();
To help with using Position-Distance’s, the PDPtr type is defined. This is a pointer to a PositionDistance object.
为了帮助使用位置距离，定义了 PDPtr 类型。这是指向 PositionDistance 对象的指针。 指向位置距离的指针
4.2.2 PDList Class
The PDList class provides a method for storing a list of PositionDistance objects, as used in the pseudocode (Section 3.1). It has one constructor, one de-constructor, and a number of methods.
PDList 类提供了存储 PositionDistance 对象列表的方法，如伪代码(第 3.1 节)中所用。它有一个构造函数、一 个反构造函数和许多方法。
// Create a New Empty
List PDList();
// Clean-up the 清理 list ~PDList();
// Number of items in the 中的项数 list int size();
// Get a pointer to the position-distance at index 获取指向索引处位置距离的指针
i PDPtr get(int i);
// Add a position-distance (as a pointer) to the list 在列表中添加位置距离(作为指针)
// This class now has control over the pointer 此类现在可以控制指针
// And should delete the pointer if the position-distance is removed from the
list void addBack(PDPtr position);
如果位置距离从列表 void addBack(PDPtr 位置)中移除，则应删除指针;
// Checks if the list contains a position-distance with the same co-ordinate
// as the given position. 检查列表是否包含与给定位置具有相同坐标的位置距离。 bool containsCoordinate(PDPtr position); 布尔 包含坐标(PDPtr 位置);
// Remove everything from the list 从列表中删除所有内容
// Don’t forget to clean-up the memory! void clear();
// Pointer to a PositionDistance typedef PositionDistance* PDPtr;
To implement the PDList you MUST use an array of pointers. To help you with this, the starter code gives an example way for storing the array of pointers. You are free to change this if you wish.
要实现 PDList，必须使用指针数组。为了帮助您实现这一点，起始代码给出了一个存储指针数组的 示例方法。如果你愿意，你可以随意改变这个。
The PDList class has full control over all pointers that are stored in the list. Thus, if items are removed
from the list you must remember to “delete” the PositionDistance object.
PDList 类对存储在列表中的所有指针具有完全控制权。因此，如果从列表中删除项目，则必须记住“删
PDPtr positions[100]; int numPositions;
除”PositionDistance 对象。
Page 6 of 10
,
! Make sure you correctly clean-up the memory used by the PDList!
! 确保正确清理 PDList 使用的内存!
4.2.3 PathPlanning Class 路径规划类
The PathPlanning class provides an API (set of methods) to implementation of the algorithm in Section 3.1,
and a simplified path planning algorithm. It has three components:
PathPlanning 类为实现第 3.1 节中的算法提供了一个 API(方法集)和一个简化的路径规划算法。它 有三个组成部分:
1.Creating the class, using a map of the maze 使用迷宫地图创建类
2.Providing the initial position of the robot 提供机器人的初始位置
3.The method for Milestone 2 for retrieving the possible positions the robot can reach, along with the
distances 里程碑 2 的方法，用于检索机器人可能到达的位置以及距离。 4.The path planning method for Milestone 3 里程碑 3 的路径规划方法
The map of the maze is provided in the constructor of the PathPlanning
迷宫的地图在路径规划的建设者中提供。
The maze is provided as a Grid, which is defined as a 2D array (see below). The top-left corner of the 2D array corresponds to the location (0,0). The parameters rows and cols give the size of the maze.
迷宫是一个网格，定义为一个二维数组(见下文)。二维数组的左上角与位置(0,0)相对应。参数
行和列给出了迷宫的大小。
It is very important to understand what the Grid type is. It is defined as a 2D array (given below). If you recall from lectures/labs, a 2D array is indexed by rows then columns. So if you want to look-up a position (x,y) in the maze, you find this by maze[y][x], that is, first you look-up the y value, then you look-up the x value.
理解网格类型是非常重要的。它被定义为二维数组(如下所示)。如果您从讲座/实验室中回忆起来， 二维数组将按行和列编制索引。所以，如果你想在迷宫中查找一个位置(x，y)，你可以通过迷宫 [y][x]找到这个位置，也就是说，首先查找 y 值，然后再查找 x 值。
// A 2D array to represent the maze or observations 表示迷宫或观测的二维数组 // REMEMBER: in a grid, the location (x,y) is found by
grid[y][x]!
记住:在网格中，位置(x，y)由网格[y][x]找到! typedef char** Grid;
The initial position of the robot is given to the PathPlanning class through the method
通过该方法将机器人的初始位置赋予路径规划类
After being given the initial position, the PathPlanning may be asked for all of the possible positions (with distances) that the robot can reach: 在给定初始位置后，可能会要求对机器人能够到达的所有可能位置
(带距离)进行路径规划:
// Initialise a with a given maze of size (x,y) PathPlanning(Grid maze, int rows, int cols);
// The initial position 初始位置
void initialPosition(int x, int y);
// Method for Milestone 2 里程碑 2 的方法
// Return a DEEP COPY of the PDList of all position-distance’s
// that the robot can reach 返回机器人可以到达的所有位置距离的 PDList 的深度副本 PDList* getReachablePositions();
The getReachablePositions method returns a deep copy of the PDList. getReachablePositions 方法返回 PDList 的深度副本。
! A deep copy of a PDList is a new list is with a copy of all of the PositionDistance objects.
! PDList 的深度副本是一个新列表，其中包含所有 PositionDistance 对象的副本。
4.2.4 Code Description 代码描述
At the top of your PathPlanning implementation you must provide a description of the design of your implementation.
Provide this in a comment-block. This block should:
在路径规划实现的顶部，必须提供实现设计的描述。
在注释块中提供。此块应:
• Describe (briefly) the approach you have taken in your implementation 描述(简要)您在实施过程中采用的方法
• Describe (briefly) any issues you encountered 描述(简要)您遇到的任何问题
• Justify choices you made in your software design and implementation 证明您在软件设计和实现中所做的选择是正确的
• Analyse (briefly) the efficiency and quality of your implementation, identifying both positive and negative aspects of your software
分析(简要)实施的效率和质量，确定软件的正面和负面方面
Page 7 of 10
4.2.5 Code Style 代码样式
Your code style will be assessed. It should be well-formatting and comply with the course style guide.
将评估您的代码样式。它应具有良好的格式并符合课程样式指南。
4.2.6 Mandatory Requirements and Restrictions 强制性要求和限制 ! 注意事项。您的作业必须符合这些要求。
Your implementation MUST: 您的实施必须:
• Your PDList implementation must use an Array of Pointers to store all PositionDistance
objects. Your implementation may:
• PDList 实现必须使用指针数组来存储所有 PositionDistance 对象。
您的实施可以:
• Add additional methods to the given classes. However, your code will ONLY be assessed using the methods listed in this spec, and provided in the starter code.
为给定类添加其他方法。但是，您的代码将只使用本规范中列出的方法进行评估，并在起始代码
中提供。
Your implementation MUST NOT: 您的实施不得:
• Alter the definition of the provided methods. 更改所提供方法的定义。
• Use the STL containers (such as array, vector, list, deque, map, or any of utility). For this assignment
they are banned. If you are unsure if you can use an STL container, ask on the forum first.
使用 STL 容器(如数组、向量、列表、deque, map 或任何实用程序)。对于这项任务，他们是 被禁止的。如果您不确定是否可以使用 STL 容器，请先在论坛上询问。
4.3 Milestone 3: Path Planning 里程碑 3:路径规划
! This is an extension Milestone.
! 这是一个扩展里程碑。
The PathPlanning class contains an additional method: PathPlanning 类包含一个附加方法:
// Method for Milestone 3 里程碑 3 的方法
// Get the path from the starting position to the given co-ordinate
获取从起始位置到给定坐标的路径
// The path should be a DEEP COPY 路径应该是深度复制
PDList* getPath(int toX, int toY);
This method finds a path from the robot’s starting position to the specified goal co-ordinate. This should contain the ordered sequence of PositionDistance objects including the starting position and the given goal co- ordinate. You may assume that the goal co-ordinate can be reached from the starting position.
该方法从机器人的起始位置到指定的目标坐标找到一条路径。这应该包含位置距离对象的有序序列，
包括起始位置和给定目标坐标。你可以假设目标坐标可以从开始位置达到。
To solve this problem, you will be able to use the list of reachable positions that is generated in your Milestone 2. The algorithm is not given to you. However, think carefully about what information is contained in the list, specifically the distance information. There may also be more than one valid path.
为了解决这个问题，您将能够使用里程碑 2 中生成的可到达位置列表。算法没有给你。但是，仔细 考虑列表中包含的信息，特别是距离信息。也可能有多个有效路径。
You will need to include additional Milestone 3 tests as part of your assignment 1. 作为作业 1 的一部分，您需要包括其他里程碑 3 测试。
4.4 Milestone 4: Efficient Memory Management 里程碑 4:高效内存管理 ! This is an extension Milestone. 这是一个扩展里程碑。
For this Milestone, you need implement the classes to use memory as efficiently as possible. Your code should only consume as much memory as is necessary.
对于这个里程碑，您需要实现类以尽可能高效地使用内存。您的代码应该只消耗必要的内存。 To do this, you may wish to consider the following: 为此，您可能希望考虑以下事项:
• Limiting the size of the array of pointers in PDList to only the number of cells needed to store all of the elements of the list.
将 PDList 中指针数组的大小限制为仅存储列表中所有元素所需的单元格数。
• Storing the maze in PathPlanning to use only the number of rows and columns given in the constructor
在路径规划中存储迷宫，以仅使用构造函数中给定的行数和列数
• Which class(es) have ownership over any memory, variable or parameter. 哪个类拥有任何内存、变量或参数的所有权。
Page 8 of 10
4.4.1 Code Description 代码描述
Finally, for this Milestone, in your implementation of the PathPlanning class, you must:
最后，对于这个里程碑，在 PathPlanning 类的实现中，必须:
• Describe (briefly) the approach you have taken in your implementation. 描述(简要)您在实施过程中采用的方法。
• Justify (briefly) why your implementation is efficient. 证明(简要)为什么您的实施是有效的。
5.Starter Code 启动代码
The starter code comes with the following
files:
启动程序代码附带以下文件:
File
Types.h
PositionDistance.h/cpp
PDList.h/cpp PathPlanning.h/cpp unit_tests.cpp
Description
Header file the typeedefs used in the assignment
头文件在作业中使用 typeedefs
The PositionDistance class 位置距离类 The PDList class
The PathPlanning class
路径规划类
Code file to run unit tests 运行单元测试的代码文件
To compile individual files, into object file for testing, you can use the command:
要将单个文件编译为要测试的对象文件，可以使用以下命令:
g++ -Wall -Werror -std=c++14 -O -c file.cpp
5.1. Running Unit Tests 运行单元测试
To compile the unit test code, with your implementation into an executable, you can use the command:
要将单元测试代码编译为可执行文件，可以使用以下命令:
g++ -Wall -Werror -std=c++14 -O -o unit_tests PositionDistance.cpp PDList.cpp PathPlanning.cpp unit_tests.cpp
A unit test can be run with the command: 可以使用以下命令运行单元测试: ./unit_tests
For example, using the starter code 例如，使用起始代码
./unit_tests sampleTest/milestone2
5.2. Getting Started
Part of the learning process of the skill of programming is devising how to solve problems. The best way to get started is to try just give some programming a go and try things out. Experimenting and practising are important
to the process of learning the skills of programming and this course. 编程技能学习过程的一部分是设计如 何解决问题。最好的开始方法是试着让一些编程尝试一下。实验和练习对于学习编程和本课程的技能 非常重要。
。
,
6、作业质量:
Page 9 of 10
1、Unit Tests:Comprehensive Unit tests for Milestones 2 & 3, covering the majority of common use cases, and most edge cases
里程碑 2 和 3 的综合单元测试，涵盖大多数常用用例和大多数边缘用例。
2、Software Implementation 软件实现:
✓ Complete and error-free implementation of Milestones 2, 3 & 4.
完成里程碑 2、3 和 4 的无错误实施。
✓ Compiles with the Milestone 2 & 4 mandatory requirements and restrictions.
符合里程碑 2 和 4 的强制性要求和限制。
3、Code Style:
✓ Exceptional and clear software design.
卓越清晰的软件设计。
✓ Exceptional coding style and suitably documented code. No input from the developers is required to comprehend the code. 特殊的编码风格和适当的文档化代码。理解代码不需要开发人员的输入。
✓ Excellent use of permitted C++11/14 language features. 优秀的使用 C++ 11/14 语言的特点。
4、Code Description/Report 代码描述/报告
✓ Suitable report for Milestones 2, 3 & 4, with good analysis 适用于里程碑 2、3 和 4 的报告，分析良好
Page 10 of 10