布线问题——分支界限法
最近学校数据结构课程布置了一个作业，我觉得很有意思，这里记录一下题目布线问题：印刷电路板将布线区域划分为n×m个方格阵列。布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案要求：布线时电路只能沿直线或直角布线。已布线方格做上封闭标记，其他线路布线不允许穿过封闭区域。（如下图所示）算法实现这里使用队列式分支限界法来解决首先，记录起点步数为0，起点的上下左右中，可达的节点步数为1，并将...
最近学校数据结构课程布置了一个作业，我觉得很有意思，这里记录一下题目布线问题：印刷电路板将布线区域划分为n×m个方格阵列。布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案要求：布线时电路只能沿直线或直角布线。已布线方格做上封闭标记，其他线路布线不允许穿过封闭区域。（如下图所示）算法实现这里使用队列式分支限界法来解决首先，记录起点步数为0，起点的上下左右中，可达的节点步数为1，并将...
众所周知，斐波那契数是很多动态规划的教程里面的第一个案例，既简单，简单到即使在不会动态规划的情况下，也可以用动态规划的方法把他做了出来，又经典，小小一个题目包含了动态规划的思想，确实不错。因此，尽管斐波那契数比较简单，我依然选择记录一下，算是作为动态规划的第一个笔记吧。当然，本文仅仅算是我个人的理解，跟大佬们讲的有些许甚至很大的出入，仅供参考。什么是动态规划动态规划（英语：Dynamic p...