【每天进步一点】2012.04.12

一时失言乱红尘 2021-10-26 16:48 254阅读 0赞

# **上午** #

上午刚到实验室的时候，先写完了一个程序，在USACO上一次就pass，虽然比较水，但是还是很开心。然后又打电话跟女朋友沟通了一些感情上的问题，说完之后，感觉心情明显好得多了。要不然，可能今天一整天就会用写程序去打发它了。

之后阅读了<<Introduction To Algorithms>>的single-source shortest paths章节中的两个算法：Bellman-Ford算法与Dijkstra算法。其中，Bellman-Ford算法的效率没有Dijkstra的效率高，但它可以去解决存在negative-edge的情况。

在Bellman-Ford算法中，首先需要initialize这个single source图。然后循环对所有的边进行v-1次relax操作。最后判断有无非环的操作是遍历每一条边(u,v),测试d\[v\]>d\[u\]+(u,v)。

而在Dijkstra算法中，类似于BFS，它使用一个一个最小堆来维护所有的顶点，从当中取出具有最小d值的节点，然后访问它所有直接相连的边，进行relax操作。然后将新的节点更新到最小堆中，这里涉及Decrease-Key操作。

# 下午 #

下午按照导师布置的任务，接触了MagicARM2410试验箱，完成了一个GPIO实现，基本的原理和问题都能够搞得比较明白，只是将程序烧写到板子上之后，就进不去原来自带的Linux系统了，从网上查阅了一些资料，估计以后会进行到这一步，然后完成它的。虽然自己一点儿都不喜欢嵌入式，不过还是强迫着自己去学习吧，遇到困难不能够畏缩，而是要迎头而上。这才是作为一个更强的人的基本保证。毕竟，为什么别人可以，我不行呢？就应该这样对自己说。

# 晚上 #

今天晚上又学习了<<Introduction To Algorithms>>中的接下来一部分内容，比较重要的是Difference contraints使用shortest paths方法求解。这里讲解了一种处理比较特殊的一类linear programming问题——Systems of difference contraints。使用顶点来表示未知的x，每一条边就代表着b值，也即约束条件。使用的方法是，构建graph的时候，添加进来一个新的顶点v与v到其他所有顶点的边，每个边的权值都是0，最后从v点开始，使用Bellman-Ford算法搜索Shortest path，每个顶点的d值即是x的可取值。

转载于:https://www.cnblogs.com/XjChenny/archive/2012/04/12/2444683.html