查人人中国名人网无为教育信息网:最优寻路/遍历算法
来源：百度文库 编辑：查人人中国名人网 时间：2024/05/04 20:41:46
例如，有一棵十分庞大的大树，从根节点出发，每向上一层分支，就分为20个子节点。每个节点再向上分出20个分支。如此向上共生长5层，第5层将有3200000个节点。假设这些就是最终节点。不再有分支。
问题1，设计一个从根出发，到一个特定节点（不一定是最终节点）的所有路径，并找到一条最短路径的最优算法。
问题2，指定的某两个节点之间，列出所有的路径，并找到一条最近的路径。
问题1，设计一个从根出发，到一个特定节点（不一定是最终节点）的所有路径，并找到一条最短路径的最优算法。
问题2，指定的某两个节点之间，列出所有的路径，并找到一条最近的路径。
你说的是图的搜索算法，不是树的算法。看你的要求，推荐用贪心算法。
每次从当前的所有下层结点当中选择花费最小的子结点进入，之后也都是。
不过对这些整数问题，贪心未必能够找到最好的路径，真正最好的路径应该是使用动态规划算法的。
找一本计算机竞赛的辅导书吧，上面对动态规划讲的会可以的。另外还有一种什么网络流算法，我一直没学会，你可以试试看，也是找图的最短路径的。
对于给定2结点之间的搜索，你可以用双向广度优先算法，从2个结点同时出发，向路径中间结点搜索最短路径。