常见的实现形式 搜索,备忘录,递推 ■自底向上 通过递推公式由小问题得到大问题的解,状态 函数 shortPath返回一个节点到目标节点的最小路径 就是递推公式的每个中间结果 自顶向下一一备忘录 建立一个全局可以访问的状态表,把递归搜索 ford= Lchild begin; jl= i child. endo: ++D) 的结果保存起来,当下次达到状态时直接返回 第一种形式的程序更快更省空间 第二种形式有时候更直观,有助于理解 搜索,备忘录,递推 搜索,备忘录,递推 graph[MAX_NODE_NUM]: 递推的方法 emset(graph, O, sizeof(int) MAX_ NODE_NUM); 递推式 shortPath(= min(shortPath(+ path (i,D)) aph[nodel 〔是的子节点) d begin(;jI= i.child. end(:++)( shortPath()=0(为目标节点) if(t+ length(node, 1)< min) ■然后使用从递推式边界算起的方法递推 到上层 搜索,备忘录,递推 0-1背包问题(1) ■搜索算法最直观,最容易想到 0-1背包问题 ■发现有重复的搜索节点就使用备忘录保 问题描述: 存节点信息。 有一个最多能用m公斤的背包,现 手件的重量分别是 ■得到递推方程一般可以转化为递推的算 法,节省函数递归的开销。 C1,C2,mCn求旅行者能获得的最大总价值。 特点: 每种物品仅有一件,可以选择放或不放。2 常见的实现形式 „ 自底向上——递推 通过递推公式由小问题得到大问题的解，状态 就是递推公式的每个中间结果。 „ 自顶向下——备忘录 建立一个全局可以访问的状态表，把递归搜索 的结果保存起来，当下次达到状态时直接返回 结果。 第一种形式的程序更快更省空间 第二种形式有时候更直观，有助于理解 搜索，备忘录，递推 „ 搜索的方法 „ 函数shortPath返回一个节点到目标节点的最小路径 长度 shortPath(node) { min = INF; for(j = i.child.begin(); j != i.child.end(); ++j) { t = shortPath(*j); if (t + length(node,*j) < min) min = t + length(node,*j) ; } return min; } 搜索，备忘录，递推 „ 备忘录的方法 int graph[MAX_NODE_NUM]; memset(graph,0,sizeof(int)*MAX_NODE_NUM); shortPath(node) { if (graph[node] != 0) return graph[node]; min = MAXINT; for(j = i.child.begin(); j != i.child.end(); ++j) { t = shortPath(*j); if (t + length(node,*j) < min) min = t + path(node,*j) ; } graph[node] = min; return min; } 搜索，备忘录，递推 „ 递推的方法 „ 递推式 „ shortPath(i) = min(shortPath(j) + path(i,j)) (j是i的子节点) „ shortPath(i) = 0 (i 为目标节点) „ 然后使用从递推式边界算起的方法递推 到上层 搜索，备忘录，递推 „ 搜索算法最直观，最容易想到。 „ 发现有重复的搜索节点就使用备忘录保 存节点信息。 „ 得到递推方程一般可以转化为递推的算 法，节省函数递归的开销。 0-1背包问题（1） „ 0-1背包问题 „ 问题描述： 一个旅行者有一个最多能用m公斤的背包，现 在有n件物品，每件的重量分别是 W1,W2,...,Wn, 每件的价值分别为 C1,C2,...,Cn。求旅行者能获得的最大总价值。 „ 特点： 每种物品仅有一件，可以选择放或不放