信息工程学院——记忆化的DFS与基于优先队列的BFS的学习

我把老师安排的学习顺序根据自己的情况做了简单修改,所以我在几天前就先学习了STL库函数,然后完成简单的最短路径的练习才进入BFS入门与DFS入门的学习。

BFS与DFS入门的学习还是比较简单的,多写几道题就可以发现思路的相似性,最后只是根据不同的条件进行简单的修改。记忆化的DFS和基于优先队列的BFS的学习则更具有综合性了。

首先是记忆化的DFS,更简单地说这个应该是线性DP即动态规划和DFS的综合使用,突出表现是使用递归,不过记忆化DFS的递归使用方向和线性DP不同,好的运用可以避免不需要的反复计算,用一些空间来替换时间是完全值得的算法。其次是基于优先队列的BFS的学习,这方面的学习首先是要了解优先队列的使用,这里常用到STL库函数中的priority_queue()函数,由于常用于了解这些算法的书上写的不够详细,我查阅了一些资料,在对于这个函数使用更了解的基础上开始练习这一种写法,不得不说收获非常大。