举例:最短路径问题 ■在多条路径可选的情况下,选最短的 组合优化问题 寻径算法 ■从起点出发,尝试各种可能的路径到终点 是否存在一种有效的算法? 工作量随系统规模扩大成指数增长 算法复杂度问题 P类,NP类,NP- Complete,NP-hard 200399 Dept of computer Science and Engineering, Shanghai fiaotong Uniperaity13 举例:七桥问题 ■普鲁士的 Konigsberg(今俄国 Kaliningrad) 被 Pregel河分成4部分 GURE 1 The Seven Bridges FIGURE 2 Multigraph Model the Town of Konigsberg7 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 13 举例：最短路径问题 „ 在多条路径可选的情况下，选最短的 „ 组合优化问题 „ 寻径算法 „ 从起点出发，尝试各种可能的路径到终点 „ 是否存在一种有效的算法？ „ 工作量随系统规模扩大成指数增长 „ 算法复杂度问题 „ P类，NP类，NP-Complete，NP-hard 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 14 举例：七桥问题 „ 普鲁士的Gönigsberg（今俄国Kaliningrad） 被Pregel河分成4部分