博客

1 题目要求 1.1 背景 随着城市轨道交通的快速发展，地铁已成为现代都市出行的核心方式之一。乘客在出行时，往往需要根据多种因素（如时间、距离、费用）选择最优路径。然而，地铁网络结构复杂，站点间存在多条路径，单一指标无法满足用户多样化需求。因此，开发一个智能的地铁线路规划查询程序，能够为任意两站提供多目标路径推荐，具有重要的实际应用价值。 1.2 目标 开发一个地铁线路规划查询程序，实现以下核心功能： 路径查询：允许用户输入任意起始站和终点站，查询所有可行的路径。 多目标推荐：根据价格、距离和时间三个指标，计算并推荐多种路径选项。 数据集成：构建结构化数据库，支持路径计算。 网状规划：将地铁网络建模为图结构，利用算法解决多目标优化问题。 用户界面：提供友好的图形界面，方便用户输入查询条件和查看结果。 设计与实现 系统架构 为了使项目具备更好的可维护性和可拓展性，我们采取了模块化设计思想，将系统划分为多个独立的模块，包括数据获取模块、路径计算模块和用户界面模块。各个模块之间通过清晰的接口进行交互，便于后续的功能扩展和维护。 有关于项目的模块划分，请参见下图： 数据获取模块 地铁数据来源于高德地图开放的地铁线路 API，每个城市对应唯一的数据链接。例如，西安的数据接口为： 然而，原始数据为 JSON 格式，结构较为复杂。项目通过parse_metro_info()函数，将原始数据解析为统一的数据结构： 核心算法模块 路径规划核心模块主要负责根据用户输入的起点和终点，结合当前地铁线路数据，计算出最优的地铁出行方案。该模块实现了多种策略的路线规划算法，并确保结果的准确性与实用性。 模块首先通过解析后的地铁数据，将整个地铁网络抽象为图结构： 站点建模：每个地铁站点（ 类）拥有唯一 ID、名称、所属线路及经纬度坐标。 邻接表构建：每个站点与其前后相邻站点通过邻接表连接，形成完整的地铁路网。对于环线，首尾站点相互连接，支持环线路径规划。 为了适应换乘站的情况，我们在 类中的所属线路属性中，使用列表来存储一个站点可能属于的多个线路信息。每个线路信息由一个 类表示，包含线路名称、相邻站点等信息。 用户界面模块 本项目的 UI 模块采用了 PyQt5 和 qfluentwidgets 库实现。 其他模块 在 模块中，我们储存了项目所需的静态资产，如背景图片、图标等。 在 模块中，我们实现了一些通用的工具函数，如票价计算、距离计算，便于其他模块调用。 测试与验证 为了确保系统的稳定性和准确性，我们对各个模块进行了充分的测试。测试主要分为单元测试和集成测试两部分。 单元测试主要针对各个函数和类的功能进行验证，确保其在各种输入下都能返回正确的结果。我们使用了 unittest 框架编写了详细的测试用例，并覆盖了常见的边界情况。 集成测试则关注模块之间的协作，确保数据流和控制流的正确性。我们模拟了用户的实际操作场景，验证了从数据获取到路径规划再到结果展示的整个流程。 封装与打包 我们使用 Nuitka 工具对项目进行封装。Nuitka 将 Python 模块翻译成 C 级程序，然后使用 libpython 和自己的静态 C 文件，以 CPython 的方式执行。这种方法相比于pyinstaller 等工具的简单封装，能够生成更小的可执行文件，并且有着更高的运行效率。 在使用过程中，我们发现 Nuitka 工具在处理 PyQt5 的依赖库 SciPy 时，存在一定的兼容性问题，导致部分功能无法正常使用。为了解决这个问题，我们尝试了多种方案，通过手动指定依赖库的方法，最终成功实现了与 Nuitka 的兼容。 拓展与反思 项目的拓展 由于在项目设计时我们使用了模块化的设计思路，使得各个模块之间的耦合度较低，便于后续的功能扩展和维护。而由于我们通过远程数据接口获取地铁线路和站点信息，未来可以方便地接入更多城市的地铁数据，扩展系统的适用范围。 随着城市地铁数据的不断增加，我们需要对数据获取模块进行重构，以支持更多城市的地铁线路和站点信息。我们计划将数据获取模块设计为一个可扩展的插件系统，允许用户根据需要动态加载不同城市的地铁数据。 我们在数据获取模块中引入了城市参数，以便在请求地铁数据时指定城市，通过城市请求相对应的地铁数据，从而实现对不同城市地铁数据的灵活支持。 同时，我们在用户界面模块中引入了城市选择功能，允许用户在不同城市之间切换，从而获取相应城市的地铁线路和站点信息。我们还优化了界面的布局和交互逻辑，以提升用户体验。 项目的反思 在项目的后期开发中，我们发现了一些潜在的问题和改进的空间。如： 在路径规划算法中，我们使用广度优先搜索（BFS）算法进行路径搜索，但在某些复杂情况下，可能会导致搜索效率低下。未来可以考虑引入其他算法，如 A* 搜索算法，以提高路径规划的效率。 由于缺少资料，我们没有在其他城市中支持票价计算功能。 由于对 PyQt5 的不了解，我们在界面设计上遇到了一些困难，也尚未支持线路图示的功能。未来可以考虑进行更多的学习和研究，以提升界面的美观性和易用性。 参见 项目源代码 高德地图地铁线路图 部分源代码 路径规划算法 构建站点对象 获取信息 主程序

基本原理 将题目文本从界面ui通过xpath提取后计算出答案，然后用uiautomator2 swipe的方式将其绘制再屏幕上 经过500题的性能测试，本项目再大多情况下可以维持再1.0s每题左右的速度。 实现方法 获取题目文本 通过xpath实现。 输出 通过将数字、符号转化为矢量点阵储存再静态文件中，再在输出时进行缩放，计算出每个笔画的坐标，从而绘制字符。 通过matplotlib对字符进行检验 进行绘制

引子 这个项目其实是为了班级元旦晚会的抽奖环节而设计的。由于班上几位原批+点子王一拍脑袋，决定整场晚会从幻灯片到背景音乐到幕间游戏全用原神的风格，并且发现现有的抽奖软件都 UI 太过古早且不支持自定义权重，于是就决定自己完成一个程序。 另外，我加入了抽到相应学生会显示对应图片的功能，以提高节目效果（e gao）。 前端设计 项目的前端基于 Pygame 框架，以此来达成绘制出类似于原神祈愿界面的目的。 素材查找 项目所使用的图片素材来源于开源项目Mantan21/Genshin-Impact-Wish-Simulator。通过其我们可以很轻松地得到无背景的按钮、边框及祈愿图片、背景、图标等素材。 面向对象的编程 获得素材之后，紧接着要做的就是完成绘制图片所需要的方法。 经过整理，发现要想完成界面的渲染，我们需要以下对象类。 object description Text 渲染文字 Image 渲染图片 ImageFixed 渲染固定尺寸的图片 ColorSurface 渲染图形 ButtonText 渲染文字按钮 ButtonImage 渲染图片按钮 ButtonColorSurface 渲染图形按钮 其中，每个类都需要一个 方法来完成对象的绘制，而按钮类需要 方法来会调事件。 这些代码均在 中。 图形类的编写 下面以 对象为例子，讲讲图形类是如何编写的。 需要注意的是，为了方便主程序的编写，在 方法中我进行了坐标的转译，使得在调用时不需要左上角坐标而只需要中心坐标就行。 另外，为了方便图形的渲染，可以使用如下方法进行放缩。 按钮类的编写 按钮类与上述大体相同，唯一的区别就是需要一个 方法。 如是，我们即可在主循环中重复检测是否将鼠标移动到按钮上并点击，以此来达到承载事件的目的。 主界面的配置 程序的主界面主要有三部份构成： 背景 结果卡片（result_card） 用户图片（image） 文字背景（text_background） 中奖人姓名（text） 按钮 开始抽奖按钮（roll_button） 配置按钮（config_button） 在本章节中，我们只讲背景和结果卡片的渲染。完整主界面的渲染与按钮我们在后文中会提及。 背景 很简单，没什么可讲的。 结果卡片 这是三者中最复杂的部分。其中主要分为三部份，要依次渲染以面上面的内容被下面的内容覆盖， 在未开始抽奖的情况下，先渲染初始的结果卡片。 在开始抽奖的情况下，渲染响应抽中人的图片和名称。 后端设计 本项目中使用的随机抽取算法为A-Res算法，其通过关键值变换将权重转化为随机优先级，并用最小堆动态维护优先级最高的几个元素，实现了高效的加权随机抽样。 对于$n$个元素中抽取$m$个样本，其时间复杂度为$O(n\log{m})$。 核心思想：关键值变换 对每个元素 ，计算一个关键值$k_i = u_i^{1/w_i}$： $u_i$：从 [0,1] 均匀分布的随机数。 $w_i$：当前元素的权重。 其具有如下数学意义：该变换确保元素被选中的概率与其权重$w_i$成正比。权重越大，$k_i$的期望值越高（因为指数$1/w_i$越小，$u_i^{(1/w_i)}$越接近 1）。 算法流程 初始化：创建一个空的最小堆 （堆顶始终是关键值最小的元素）。 遍历所有元素： 未填满堆时（ ）：直接将当前元素的关键值 ki 和元素本身压入堆。 堆已满（ ）：若当前 ，则替换堆顶元素： 将 压入堆。 弹出堆顶元素（保持堆大小为 ）。 反回结果：遍历结束后，堆中所有元素即为被选中的样本。 伪代码实现 Python实现 主程序 主循环 两个按钮 杂项：播放音视频

This is a test post to show how the theme works. Basic Markdown Syntax Styling text Test Test Test This text is extremely important This is a subscript text This is a superscript text This is an underlined text Quoting text Text that is a quote Links ans images link Lists George Washington John Adams Thomas Jefferson Apple Banana Orange First list item First nested list item Second nested list item #739 https://github.com/octo-org/octo-repo/issues/740 Add delight to the experience when all tasks are complete Footnotes Here is a simple footnote1. A footnote can also have multiple lines2. Tables Column1 Cloumn2 This is A test. Fold This is a detail section. 123321 啊啊 Shortcodes Bilibili Folded bilibili video. Tencent video Youtube Quote Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. ― A famous person, The book they wrote My reference. ↩︎ To add line breaks within a footnote, prefix new lines with 2 spaces. This is a second line. ↩︎