13种行驶路线 不能同时走的路线对 嚼 ·(ABBC)(ABBD) BA BC, BD (AB DA)(AB EA) DA, DB, DC AC DB)(AC EA)(AC EB) EA, EB, EC (AD EA)(AD EB)(AD EC) ·(BCEB)(BcDB 不能同时 ·(BDDA)(BDEB)(BDEc) ·(DAEB)(DAEC) 如AB、BC;BB、AD (DB EC) 可以同时 多叉路口交通灯管理问题 有连线则不能同时通行 13种行驶路线 AB, AC, AD BA BC. BD e DA, DB DC EA EB. ec 不能同时 如AB、BC B 地图着色 地图着色问题 对一张地图用若干种颜色着色 ●最少着色分组的最优解问题是NP复 ·要求相邻的区域用不同的颜色 杂性问题 ●穷举法或回溯法来解决地图着色问 题。对于小型地图可以使用 对于大型模式,由于时间的指数上 升,不可接受 ●指数级或NP问题往往通过一些逼近 方法来求近似最优解12 13种行驶路线 z AB,AC,AD z BA,BC,BD z DA,DB,DC z EA,EB,EC z ED z 不能同时 z 如AB、BC；EB、AD z 可以同时 z 如AB、EC B C A D E 不能同时走的路线对 z (AB BC) (AB BD) (AB DA) (AB EA) z (AC DA) (AC BD) (AC DB) (AC EA) (AC EB) z (AD EA) (AD EB) (AD EC) z (BC EB) (BC DB) z (BD DA) (BD EB) (BD EC) z (DA EB) (DA EC) z (DB EC) B C A D E 多叉路口交通灯管理问题 z 13种行驶路线 z AB,AC,AD z BA,BC,BD z DA,DB,DC z EA,EB,EC z ED z 不能同时 z 如AB、BC B C A D E 有连线则不能同时通行 AB AC AD BA BC BD DA EC DB EA DC EB ED 1 1 1 1 1 1 2 2 3 2 3 4 4 地图着色 z 对一张地图用若干种颜色着色 z 要求相邻的区域用不同的颜色 2 1 3 4 7 5 6 8 地图着色问题 z 最少着色分组的最优解问题是NP复 杂性问题 z 穷举法或回溯法来解决地图着色问 题。对于小型地图可以使用 z 对于大型模式，由于时间的指数上 升，不可接受 z 指数级或NP问题往往通过一些逼近 方法来求近似最优解