《算法设计与分析》第04章概要课件.ppt

o计算机博弈计算机博弈o模式识别模式识别o美国火星探测车美国火星探测车状态空间法状态空间法问题的归约问题的归约(与或图与或图)以以FIFO队列作为活结点表队列作为活结点表此过程中活结点表隐含在系统堆栈中实现此过程中活结点表隐含在系统堆栈中实现双连通图的深度优先树有以下特征双连通图的深度优先树有以下特征o 根结点只有一个孩子根结点只有一个孩子o非根结点非根结点u的每一颗子树上的每一颗子树上 均有反向边指向均有反向边指向u的祖先的祖先设设S=(V,T)是图是图G=(V,E)的一颗深度优先树，图中的一颗深度优先树，图中结点结点a是一个关节点，当且仅当是一个关节点，当且仅当oa是根，且是根，且a至少两个孩子至少两个孩子o或者或者a不是根，且不是根，且a的某颗树上没有指向的某颗树上没有指向a的祖的祖先的反向边先的反向边程序中通过全局变量程序中通过全局变量dtime记录记录这里某条路径是指以下情况：这里某条路径是指以下情况：o自结点自结点u出发通过一条反向边到达结点出发通过一条反向边到达结点xo自结点自结点u出发，经过出发，经过u的孩子的孩子w，以及由，以及由w出发由树边组成的路径和一条反向边到达结点出发由树边组成的路径和一条反向边到达结点y。