案例展示 COSC 1285/2123 Assignment 1: Implementing and Evaluating Data Structures for Maze Generation

概述

该作业的目标是通过实现和评估不同的数据结构来生成迷宫，并根据不同的使用场景分析这些数据结构的表现。这项任务不仅要求学生掌握几种常用的数据结构，还需要理解它们在不同情境下的时间复杂度，以及如何通过实验分析得出合理的设计选择。

任务分解

作业分为两个主要部分：

1. 任务 A：实现迷宫数据结构（6 分）

   • 学生需要实现两种图结构的数据表示方式来表示迷宫，分别是边列表和关联矩阵。系统已经提供了二维数组的迷宫实现，学生需在此基础上完成其他两种结构的实现。
   • 具体需要完成的内容包括：
     • 边列表：将迷宫表示为一组边的集合，每个边连接两个顶点。
     • 关联矩阵：用矩阵的形式表示迷宫，行表示顶点，列表示边，矩阵中的值指示一个顶点是否与某条边相关联。
   • 系统提供了 Python 代码框架，学生需要在框架中完成指定部分的实现。

2. 任务 B：评估数据结构（12 分）

   • 理论分析：学生需要分析各个操作（如 updateWall() 和 neighbours()）在不同数据结构中的最佳和最差时间复杂度。并通过示例场景说明这些时间复杂度的来源。
   • 实验分析：学生需要通过实际生成迷宫并测试数据结构的表现，来验证理论分析的结果。实验要考虑迷宫的不同尺寸和数据结构的差异，并进行多次运行以求平均结果。
   • 实验报告：需要撰写一份不超过 5 页的报告，详细阐述理论分析和实验结果，并给出针对不同迷宫尺寸的建议数据结构。

学习目标

该作业旨在实现三个主要的学习成果：

• 比较、对比并应用关键数据结构：树、列表、栈、队列、哈希表和图表示；
• 理论上比较和分析算法和数据结构的时间复杂度；
• 实现、对比并将基本算法和数据结构应用于实际问题。

迷宫背景

迷宫通常表示为一个 2D 网格，网格中的单元格代表可以走的路径或墙壁，入口和出口明确标出。学生的任务是生成完美迷宫，即从迷宫的任意一个单元格都能到达另一个单元格。每个迷宫为一个正方形网格，并且在边缘有虚拟的入口和出口。

例如，5x5 迷宫中，单元格的坐标从 (0, 0) 开始，入口和出口的坐标可能位于迷宫的外部，如 (-1, 0) 或 (5, 4)。

代码实现框架

提供了部分实现的 Python 代码框架，学生需要在这个框架的基础上完成两种图结构的实现。这些图结构的实现涉及：

• Edge List Graph：通过一个边列表来存储迷宫的连接情况。
• Incidence Matrix Graph：通过一个关联矩阵来存储迷宫的结构信息。

代码框架中包含了一些辅助类和工具函数，学生只需按照框架中的提示完成指定部分的实现。

理论分析与实验分析

理论分析要求学生推导出不同操作在各个数据结构中的时间复杂度，并通过分析和实验结果验证这些复杂度的正确性。对于实验部分，学生需要生成多个不同大小的迷宫，并测试数据结构在这些迷宫中的表现。实验结果需要通过报告详细说明，并对不同迷宫尺寸下的最优数据结构给出推荐。

作业提交

• 代码：所有代码文件必须按照指定的目录结构提交，目录名为 Assign1-<学号>，并确保代码能够在 RMIT 的服务器上运行。
• 报告：报告的命名为 assign1.pdf，并放置于代码的根目录下。
• 数据生成代码：实验中使用的数据生成代码需要单独放入 dataGen 文件夹中。

最终提交文件必须打包为 zip 格式，并按照要求命名。

评分标准

• 实现部分（6 分）：要求代码设计清晰、注释充分，并在指定框架内正确实现。
• 报告部分（12 分）：根据报告中的分析和评价来打分，重点考察学生对不同数据结构的理解和实验设计。
• 视频面试（2 分）：面试部分是 pass/fail 形式，考察学生对自己代码和报告的理解。

联系我们

WeChat：pythonyt001
Email: [email protected]