路径规划算法:DFS,BFS,Dijkstra, GBFS 和 A*

介绍 图搜索算法中最常见的一个应用就是路径规划,常见的针对无权图的搜索有DFS和BFS,引入权重后,Dijkstra算法解决了单源最短路径问题,而启发式搜索的存在(GBFS,A*)则能够通过启发函数来提高搜索效率。 DFS 深度优先搜索(Depth First Search)通过维护栈这一数据结构,能够实现对全部路径的搜索,但他会沿着一条路走到最后,在没有结果时才会回头选择另一条路,因此无法保证找到的路径是最优路径。 def dfs(start_point, goal_point): path = [] seen = set() stack = [] seen.add(start_point) stack.append(goal_point) while len(stack) > 0: current = stack.pop() path.append(current) if current == goal_point: break if not graph.neighbors(current): path.pop() continue for next in graph.neighbors(current): if next not in seen: stack.append(next) seen.add(next) return path BFS 广度优先搜索(Breadth First Search)在搜索无权图最短路径时很有用,他会优先探索当前位置的所有方向而不是向着一个方向探索到最后,这也是广度的由来。实现BFS通常依靠队列。同时,我们通过字典来保存我们走过的路径,并通过从终点开始的反向遍历得到路径。 def bfs(start_point, goal_point): frontier = Queue() frontier.put(start_point) came_from = dict() came_from[start_point] = None seen = set() seen....

November 25, 2022 · yunlang

Rust: 泛型,特征与特征对象

Rust: 泛型,特征与特征对象 最近在学习 Rust 的一些概念思想,记录一下自己对 Rust 中泛型,特征与特征对象的理解。 泛型 泛型与 CPP 中的模版类似,可以减少代码的重复。泛型会在编译时实现单态化(monomorphization),会将通用代码转换为特定代码,因此不会出现运行时开销。 可以理解为编译器帮你把写的泛型代码重新转换为写了具体类型的代码。 泛型可以用在结构体,枚举,函数乃至方法中,其中枚举和方法可以多讲一下。 泛型在枚举中的实现 泛型在枚举中的实现本身没有要讲的,不过标准库实现的Option<T>和Result<T, E>很想讲一下。 Option 标准库中的泛型定义 pub enum Option<T> { None, Some(T), } 简约而又简单,rust 中并不存在空指针,通过 None 进行替代,Option常使用在返回值中。当返回值可能为一个结果,也有可能失败或缺值时,可以通过模式匹配进行处理。这里的 T 就是泛型说明 Result<T, E> 标准库中的泛型定义 pub enum Result<T, E> { Ok(T), Err(E), } 除了Option可以在结果失败时传递 None,但有时我们想要知道具体的失败信息,Result 实现了这一点。Result<T, E> 拥有两个泛型 T 和 E,在不同的场景下你可以将他们作为不同的类型。 泛型在方法中 泛型在方法中需要在impl后面声明<T>,这里是为了告诉 Rust 类型后面的 T 是一个泛型而不是具体类型,注意这里impl后面提供的泛型声明只与后面具体类型要实现的泛型有关。 与之相应的,你也可以为一个泛型实现他具体类型的方法。 // 对一个泛型实现具体方法,其中方法中又提供了更多的泛型声明 struct Mix<T, U> { x: T, y: U, } impl<T, U> Mix<T, U> { fn mixup<V, W>(self, other: Mix<V, W>) -> Mix<T, W> { //这里提供了另外两个泛型: V和W, 代表other的类型参数 Mix { x: self....

November 14, 2022 · yunlang

Verilog 实现双边沿触发器Dual Edge_triggered_flip Flop

Verilog 实现双边沿触发器Dual Edge_triggered_flip Flop 在做HDLbits时,有一道很有趣的双边沿触发器问题 ,这里记录一下相关内容和解答方式。 问题描述 实现一个双边沿触发器,即在时钟的上升沿和下降沿都被触发。 module top_module ( input clk, input d, output q ); 问题 无法直接通过always @(posedge clk or negedge clk)直接创建双边沿触发器,FPGA 中只能存在单边沿触发器。 但是你可以创建两个触发器,分别是上升沿和下降沿。 解决方案(1) 虽然我们无法直接创建双边沿触发器,但是可以通过使用两个触发器和一个多路选择器实现相同的功能。 module top_module ( input clk, input d, output q ); reg q1; reg q2; always @(posedge clk) begin q1 <= d; end always @(negedge clk) begin q2 <= d; end assign q = clk ? q1 : q2; endmodule 注意,你可能想要两个触发器内都填写q <= d,这在思维上是合理的,但是在实现中会引入多驱问题。...

November 11, 2022 · yunlang

右值引用: 移动语义

右值引用:移动语义 左值与右值 左值有标识 标识:你有某个值,并有某个值的内存地址,可以安全的使用它 左值(lvalue)可以出现在赋值的左侧(当我们使用他的名称时),也可以出现在赋值的右侧(当我们使用他的值时)。因此当我们称某个值为左值时,他未必出现在等号左侧,而是认为他有标识。 这里的左值严格意义上称为泛左值,包括左值和将亡值两种。 右值可移动,左值不能 有些值并非泛左值,换句话说你无法获得其内存地址并使用。这类值的优点是可以移动他而不是复制它。(通常情况下移动要比赋值开销小很多)。移动一个值意味着他不会在原来的位置,当你称一个值可以移动时,我们认为是右值。 左值是不可移动的,因为这破坏了左值的概念:通过内存地址使用 右值引用的对象,是临时的,即将被销毁。 纯右值 纯右值没有标识,因此我们无法使用他的内存地址,但他是可以移动的(因为是右值)。 值类别汇总 泛左值(glvalue):有标识 左值:有标识但不能移动 将亡值:有标识,但也可以移动,是之前的某个左值变成了右值引用。 纯右值:没有标识,可以移动。 右值:可移动 左值持久,右值短暂 左值引用与右值引用 重新观察T& 重新观察T&和const T&,他们现在实际上是对左值的引用。左值引用可以绑定到左值,但不可以绑定到右值。 左值引用时,我们将一个对象的内存空间绑定到另一个变量上,因此我们使用的是一个对象在内存中的位置,这是一个左值。 右值引用 通过T&&可以标识一个类型T的右值引用,右值引用引用了一个可移动值,其内容在使用后无需保留。右值引用绑定到右值而非左值(右值引用假定内容无需保留而进行移动的值)。 右值引用意味着:1.右值是临时的,即将被销毁。 2.右值引用的对象不会在其他地方使用。 这两个特性意味着:接受和使用右值引用的代码,可以自由地接管所引用的对象的资源,而无需担心对其他代码逻辑造成数据破坏。 右值引用是左值还是右值 对于左值引用,当我们想要使用他的值时,他是右值,当我们想要使用他的地址(内存空间)时,他是左值。对于右值引用也一样,当我们进行右值引用时,右值的变量已经被右值引用接管了,这个时候的变量可以通过右值引用保存下来,因此可以成为左值。而我们也可以直接使用右值引用的值,这个时候右值引用会作为右值。 移动语义 右值引用支持“移动语义”,利用移动语义,你可以让一个对象转移到另一个对象而非使用拷贝构造,他也可以使用临时对象转移资源。 右值中的数据可以被安全移走使得右值可以用来表达移动语义。 考虑vector对象的实例,当vector容量满时,我们会开辟一块新的空间并将内容拷贝构造到新空间,销毁之前的空间。但拥有了移动语义后,我们可以实现移动而非拷贝,这可以避免成本高昂的内存分配和复制操作。

October 7, 2022 · yunlang

数据库系统(一)

数据库系统 数据库 什么是数据库? 将信息以某种形式存储在一起。 数据库的重要位置 系统软件之一,为多种应用软件提供基础。 注意数据库(Database)与数据库管理系统(Database management system,DBMS)的区别。 传统数据整理 传统数据整理的方式:一种方式为 CSV 的表格式存储。 缺点:安全性,效率性,使用时的复杂度等。 如无法保证在数字栏插入的一定是数字。检索需要遍历,出现问题容易直接崩溃等。 早期的DBMS DBMS:软件层面上对数据模型进行定义,提供了增删改查等功能。 早期的数据模型:逻辑与物理紧密结合,必须对特定的数据库场景安排对应的处理应用。 根本原因为物理存储上直接采用应用对数据格式,位置等进行规定,因此切换场景等都需要重新进行设计。 关系模型 基于关系定义了一种数据模型的抽象。 利用一种简单的数据结构(关系)进行数据库存储 用户操作基于高级语言,DBMS 负责具体执行策略 物理存储由 DBMS 负责实现。 关系模型是将无序的各种数据通过关系串联起来,而对这些数据的操作和物理存储的实现都交给了 DBMS,因此使用者可以相对透明的完成对数据的处理。 关系模型也定义了三个概念: 数据结构 数据操作 数据约束 关系模型利用了数学上的关系定义 主键与外键 主键:每个关系中唯一的键,作为该关系的关键字。(如省略,一般会自动生成) 外键:提供关系与关系间的纽带。 DML Data Manipulation Languages,数据操作语言,用来操作数据库表中的记录。 中文可以理解成增删改查四种操作。 常见的两种分类: Procedural: 指定了做什么,和如何做 Non-Procedural(Declaratice): 仅仅指定了做什么 关系代数 关系代数是对关系模型中各种运算操作的集合(前面说了关系模型其实是一种数学的关系定义)。 注意和数学上的关系运算并不完全相同。 “选择”、“投影”、笛卡尔积(也叫做“叉积”或“交叉连接”)、并集、差集、“重命名”、“自然连接”。 利用关系代数我们可以解释两种 DML 的不同之处:...

September 2, 2022 · yunlang