jacobajak/urban-incident-response-dsa-public

# 城市突发事件响应系统 **课程：** 04-630: 工程师数据结构与算法 **讲师：** George Okeyo 教授 **专业：** 信息技术理学硕士 (MSIT)，一年级 **卡内基梅隆大学非洲分校 | 第 19 组** ## 小组成员 | 姓名 | Andrew ID | 贡献 |------|-----------|-------------- | Guilaine Ndahiro | gndahiro | 哈希表 (UnitTable + IncidentTable), AVL 树 | | Lynne Chepkwony | ichepkwo | 带权图, Dijkstra 最短路径, 字典树 | | Ajak Makuach Abuol | aabuol | 优先队列 (最小堆), 并查集, 线段树 | ## 项目描述 我们构建了一个城市突发事件响应系统，用于管理以卢旺达基加利为模型的城市 的应急行动。该城市被表示为一个有向带权图，其中交叉口为节点，单行道为带有 行驶时间权重的边。系统处理火灾、事故和犯罪等突发事件，并沿最快可用路线 派遣救护车、消防车和警察等应急单位。 所有七种数据结构均已实现。每个核心操作的运行时间在 O(log n) 或更佳。 ## 七大 DSA ### 期中 DSA (第 15-18 讲) | DSA | 用途 | 负责人 | 复杂度 | |-----|---------|-------|------------| | 优先队列 (最小堆) | 按严重程度对突发事件排序，确保最紧急的事件始终被优先派遣 | Ajak | O(log n) 插入, O(log n) extractMin | | 哈希表 (链地址法) | 通过 ID 存储和检索单位及事件记录 | Guilaine | 平均 O(1) 插入和搜索 | | 带权图 | 将基加利建模为交叉口和道路的有向邻接表 | Lynne | O(V + E) 空间 | | Dijkstra | 查找从单位到事件现场的最快路线 | Lynne | O((V+E) log V) | ### 期末 DSA (第 11-14 讲) | DSA | 用途 | 负责人 | 复杂度 | |-----|---------|-------|------------| | AVL 树 | 按时间戳记录突发事件，支持诸如“过去一小时内的所有事件”的范围查询 | Guilaine | O(log n) 插入, O(log n + k) 范围查询 | | 并查集 (DSU) | 在运行 Dijkstra 前预先检查道路连通性，避免无效的寻路计算 | Ajak | O(α(n)) ≈ O(1) | | 线段树 | 在任意时间窗口内以 O(log n) 计数突发事件，无需线性扫描 | Ajak | O(log n) 更新和查询 | | 字典树 | 位置名称的前缀搜索，输入“CHU”即可立即获得“CHUK Hospital” | Lynne | O(L) 插入和搜索 | ## 系统工作原理 当接到紧急情况报告时，七种 DSA 会协同工作： 1. **优先队列** 接收事件并根据严重程度进行排序。最关键的事件始终排在最前面。 2. **哈希表** 存储队列未跟踪的完整事件详情（类型、位置、解决状态）。 3. **并查集** 运行近乎 O(1) 的预先检查：单位与事件之间是否存在任何道路路径？如果不存在，则完全跳过 Dijkstra。 4. **Dijkstra** 在带权图上计算从单位所在路口到事件现场的最快路线。 5. **AVL 树** 按时间戳记录每个新事件，以便调度员随后可以查询“10:00 到 11:00 之间发生了什么？” 6. **线段树** 以 O(log n) 的时间统计任意时间窗口内的事件数量，为轮班主管提供数据分析。 7. **字典树** 允许调度员仅通过输入前几个字母来搜索位置名称。 ## 数据结构说明 ### 优先队列 (最小堆) **是什么：** 一种基于二叉树的数据结构，其中每个父节点的优先级值都小于其子节点。最小（最高优先级）的元素始终位于根节点，并且可以在 O(log n) 时间内被提取。 **工作原理：** 将事件插入到一个完全二叉树中，通过“上浮”（在插入期间）将元素向上移动，或通过“下沉”（在提取期间）将元素向下筛选到正确位置，从而保持最小堆特性。该树存储在数组中，其中节点 i 的左子节点位于索引 2*i+1，右子节点位于 2*i+2。 **在项目中的作用：** 维护一个按严重程度排序的紧急事件队列。当调度员需要处理下一个事件时，extractMin 会立即返回最关键的事件，而无需扫描整个事件列表。 **时间复杂度：** - 插入：**O(log n)** — 添加到末尾，上浮至正确位置 - 提取最小值：**O(log n)** — 移除根节点，将最后一个节点移至根部，执行下沉操作 - 访问最小值：**O(1)** — 返回根节点而不移除 ### 并查集 (不相交集合合并 / DSU) **是什么：** 一种跟踪一组不相交（不重叠）集合的数据结构，能够高效地回答“元素 A 和 B 是否在同一个集合中？”它使用一个森林结构，其中每个元素指向一个父节点，而树的根节点作为集合的代表。 **工作原理：** - **find(x):** 从 x 沿着父指针遍历到根节点。使用*路径压缩* — 一旦找到根节点，就将 x 的父节点直接指向它，从而为未来的查询展平树结构。 - **unite(x, y):** 找到两个集合的根节点。如果不同，则通过使一个根节点指向另一个根节点来合并它们。使用*按秩合并* — 通过将较小的树附加在较大的树下，保持树的浅层结构。 **在项目中的作用：** 在运行 Dijkstra 复杂度为 O((V+E) log V) 的最短路径算法之前，并查集会执行近乎瞬时的 O(1) 预先检查：“单位与事件位置之间是否存在任何道路路径？”如果不连通，则完全跳过 Dijkstra，从而节省计算资源。 **时间复杂度：** - find(x): **O(α(n)) ≈ O(1)** — 路径压缩后近乎常数时间 (α = 反阿克曼函数，对于实际应用数值小于 5) - unite(x, y): **O(α(n)) ≈ O(1)** — 两次查找加一次指针更新 - connected(x, y): **O(α(n)) ≈ O(1)** — 比较 find(x) == find(y) ### 线段树 **是什么：** 一种基于数组构建的二叉树数据结构，支持高效的范围查询和点更新。每个内部节点存储其子节点的聚合信息（如总和），允许通过组合来自多个节点的结果来回答跨越范围的单次查询。 **工作原理：** - 存储在数组中，其中节点 i 的左子节点位于 2*i，右子节点位于 2*i+1 - **update(pos, value):** 定位到位置 pos 的叶子节点，对其进行更新，然后通过重新计算总和将更改一直向上传播到根节点 - **query(left, right):** 递归遍历树；对于每个节点，对重叠情况进行分类： - 无重叠 → 返回 0 - 完全重叠 → 返回该节点的存储值 - 部分重叠 → 在两个子节点上递归并对结果求和 **在项目中的作用：** 以 O(log n) 的时间回答时间分析问题：“在时间 100 和时间 500 之间发生了多少起突发事件？”如果没有线段树，这将需要扫描整个数组。线段树预先组织了时间间隔，因此可以通过组合 O(log n) 个预先计算的总和来回答任何范围查询。 **时间复杂度：** - update(pos, value): **O(log n)** — 找到叶子节点，更新它，通过 O(log n) 个祖先节点传播到根节点 - query(left, right): **O(log n)** — 递归组合范围；树高为 O(log n) - 空间复杂度：**O(n)** — 大小为 4*n 的数组足以应对任何完全二叉树 ## 基准测试结果 (n = 10,000 次操作) | DSA | 操作 | 耗时 (ms) | Big-O | |-----|-----------|-----------|-------| | AVL 树 | 插入 x10,000 | 1.686 | O(log n) | | AVL 树 | 范围查询 x10,000 | 46.475 | O(log n + k) | | 并查集 | 合并 x10,000 | 0.034 | O(α(n)) ~O(1) | | 并查集 | 连通检查 x10,000 | 0.032 | O(α(n)) ~O(1) | | 线段树 | 更新 x10,000 | 0.784 | O(log n) | | 线段树 | 查询 x10,000 | 0.035 | O(log n) | | 字典树 | 插入 x10,000 | 0.634 | O(L) | | 字典树 | 搜索 x10,000 | 2.698 | O(L) | | 优先队列 | 插入 x10,000 | 0.495 | O(log n) | | 优先队列 | 提取最小值 x10,000 | 1.138 | O(log n) | | 哈希表 | 插入 x10,000 | 0.611 | O(1) 平均 | | 哈希表 | 搜索 x10,000 | 0.059 | O(1) 平均 | | Dijkstra | 完整运行 x10,000 | 1.727 | O((V+E)log V) | 内存：已通过 valgrind 验证 —— 零泄漏，70,037 次分配与 70,037 次释放完全匹配。 ## 如何运行主演示 ``` g++ -std=c++17 -o main_demo main.cpp \ priority_queue/priority_queue.cpp \ hash_table/hash_table.cpp \ graph/weighted_graph.cpp \ djikstra/djikstra.cpp \ avl_tree/avl_tree.cpp \ union_find/union_find.cpp \ segment_tree/segment_tree.cpp \ trie/trie.cpp ./main_demo ``` 该演示是交互式的。它会加载基加利城市地图，注册单位，并预设三个初始事件。 一个包含 10 个选项的菜单允许您报告突发事件、使用 Dijkstra 路由派遣单位、 按前缀搜索位置、查询事件时间线、统计时间窗口内的事件以及检查道路连通性。 ## 如何运行基准测试 ``` g++ -std=c++17 -O2 -o benchmark benchmark.cpp \ priority_queue/priority_queue.cpp \ hash_table/hash_table.cpp \ graph/weighted_graph.cpp \ djikstra/djikstra.cpp \ avl_tree/avl_tree.cpp \ union_find/union_find.cpp \ segment_tree/segment_tree.cpp \ trie/trie.cpp ./benchmark ``` ## 如何运行单元测试 每个 DSA 都有其对应的测试文件。 **AVL 树：** ``` g++ -std=c++17 -o test_avl tests/test_avl_tree.cpp avl_tree/avl_tree.cpp ./test_avl ``` **并查集：** ``` g++ -std=c++17 -o test_uf tests/test_union_find.cpp union_find/union_find.cpp ./test_uf ``` **线段树：** ``` g++ -std=c++17 -o test_st tests/test_segment_tree.cpp segment_tree/segment_tree.cpp ./test_st ``` **字典树：** ``` g++ -std=c++17 -o test_trie tests/trie_test.cpp trie/trie.cpp ./test_trie ``` **哈希表：** ``` g++ -std=c++17 -o test_hash tests/hash_table_test.cpp hash_table/hash_table.cpp ./test_hash ``` **优先队列：** ``` g++ -std=c++17 -o test_pq tests/test_priority_queue.cpp priority_queue/priority_queue.cpp ./test_pq ``` **带权图：** ``` g++ -std=c++17 -o test_graph tests/test_weightedgraph.cpp graph/weighted_graph.cpp ./test_graph ``` **Dijkstra：** ``` g++ -std=c++17 -o test_dijkstra tests/test_djikstra.cpp \ graph/weighted_graph.cpp \ djikstra/djikstra.cpp ./test_dijkstra ``` ## 项目结构 ``` urban-incident-response-dsa-group19/ ├── main.cpp # Main interactive demo (all 7 DSAs) ├── benchmark.cpp # Benchmark timing for all 7 DSAs ├── avl_tree/ │ ├── avl_tree.h │ └── avl_tree.cpp ├── union_find/ │ ├── union_find.h │ └── union_find.cpp ├── segment_tree/ │ ├── segment_tree.h │ └── segment_tree.cpp ├── trie/ │ ├── trie.h │ └── trie.cpp ├── hash_table/ │ ├── hash_table.h │ └── hash_table.cpp ├── priority_queue/ │ ├── priority_queue.h │ └── priority_queue.cpp ├── graph/ │ ├── weighted_graph.h │ └── weighted_graph.cpp ├── djikstra/ │ ├── djikstra.h │ └── djikstra.cpp ├── tests/ │ ├── test_avl_tree.cpp │ ├── test_union_find.cpp │ ├── test_segment_tree.cpp │ ├── trie_test.cpp │ ├── hash_table_test.cpp │ ├── test_priority_queue.cpp │ ├── test_weightedgraph.cpp │ └── test_djikstra.cpp └── docs/ └── Group 19 Project Proposal.pdf ``` ## 项目提案 完整的项目提案可在 `docs/` 文件夹中找到。

标签：AVL树, C++, CMU, Dijkstra算法, GIS, Python, SEO优化词, 事件调度, 交通路网建模, 优先队列, 加权有向图, 哈希表, 响应时间优化, 图论, 地理信息系统, 城市应急响应系统, 基加利, 字典树, 并查集, 应急指挥调度, 报警与接处警, 救援系统, 数据擦除, 数据管道, 数据结构, 无后门, 智能交通, 最小堆, 最短路径, 期末项目, 算法, 紧急事件管理, 线段树, 路由规划, 软件工程