《Graphs 留学 留学资料 教案.pdf》由会员分享，可在线阅读，更多相关《Graphs 留学 留学资料 教案.pdf（17页珍藏版）》请在三一文库上搜索。
1、Introduction to Computers and ProgrammingProf. I. K. LundqvistLecture 6Mar 30 2004Some slides adapted from:6.034 Tomas Lozano Perez,Russell and Norvig AIMA and16.410 Brian C. Williams2Today Problem Formulation Problem solving as state space search Definition of Graphs Types of Graphs Shortest Path p
2、roblems Dijkstras Algorithm3Today Problem Formulation Problem solving as state space search Definition of Graphs Types of Graphs Shortest Path problems Dijkstras Algorithm4Complex missions must carefully: Plan complex sequences of actions Schedule tight resources Monitor and diagnose behavior Repair
3、 or reconfigure hardware.? Most AI problems, like these, may be formulated as state space search.5SimpleTrivialAstronautGooseGrainFoxRover Astronaut + 1 item allowed in the rover. Goose alone eats Grain Fox alone eats GooseCan the astronaut get its produce safely across the Martian canal?6Problem So
4、lving as State Space Search Formulate Goal State Astronaut, Fox, Goose & Grain across river Formulate Problem States Location of Astronaut, Fox, Goose & Grain at top or bottom river bank Operators Move rover with astronaut & 1 or 0 itemsto other bank Generate Solution Sequence of States
5、Move(goose,astronaut), Move(astronaut), . . .7AstronautGooseGrainFoxGrainFoxAstronautGooseAstronautGrainFoxGooseGooseAstronautFoxGrainAstronautGooseGrainFoxAstronautGooseGrainFoxGrainAstronautGooseFoxAstronautGooseGrainFoxFoxAstronautGooseGrainAstronautGooseFoxGrainGooseFoxAstronautGrainGooseGrainAs
6、tronautFoxAstronautGrainGooseFoxAstronautFoxGooseGrainGooseGrainFoxAstronautGooseGrainFoxAstronaut8AstronautGooseGrainFoxGrainFoxAstronautGooseAstronautGrainFoxGooseGooseAstronautFoxGrainAstronautGooseGrainFoxAstronautGooseGrainFoxGrainAstronautGooseFoxAstronautGooseGrainFoxFoxAstronautGooseGrainAst
7、ronautGooseFoxGrainGooseFoxAstronautGrainGooseGrainAstronautFoxAstronautGrainGooseFoxAstronautFoxGooseGrainGooseGrainFoxAstronautAstronautGooseGrainFox9Today Problem Formulation Problem solving as state space search Definition of Graphs Types of Graphs Shortest Path problems Dijkstras Algorithm10Gra
8、ph A graph is a generalization of the simple concept of a set of dots (called verticesor nodes) connected by links (called edges or arcs) Example: graph with 6 vertices and 7 edges12453611Examples of GraphsSFOBostonLADallasWash DCAirline RoutesABCABCABCABCPut C on BPut C on APut B on CPut C on AABCP
9、ut A on CPlanning Actions(graph of possible states of the world)12Graphs A graph G = (V, E) is a finite nonempty set of vertices and a set of edges An empty graph is the graph whose edge set is empty The null graph is the graph whose edge set and vertex set are empty213V = 1, 2, 3E = (1, 2)2413V = 1
10、, 2, 3, 4E = (1,2)(2,3)(1,4)(2,4)1V = 1E = V = E = 13Examples of GraphsGraph AirlineRoutes is represented as the pair (V,E)V= Bos, SFO, LA, Dallas, Wash DCE= (SFO,Bos),(SFO,LA),(LA,Dallas),(Dallas,Wash DC).SFOBostonLADallasWash DCAirline Routes14Graphs A loop in a graph is an edge e in E whose endpo
11、ints are the same vertex. A simple graph is a graph with no loops, and there is at most one edge between any pair of vertices.124536A simple graph withV = 1, 2, 3, 4, 5, 6E = (1,2), (1,4), (2,3), (2,4), (3,5), (5,6), (4,5)15Graphs A multigraph has two or more edges that connect the same pair of vert
12、ices A cycle is a path that begins and ends with the same vertex A cycle of length 1 is a loop (1, 2, 3, 5, 4, 2, 1) is a cycle of length 612453616Vertices Two vertices, u and v in an undirected graph G are called adjacent (or neighbors) in G, if (u,v) is an edge of G. The degree of a vertex in an u
13、ndirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex.12453617Adjacency Matrix A finite graph is often represented by its adjacent matrix. An entry in row I and column j gives the number of edges from the ithto the jthv
14、ertex.1245360 1 0 1 0 01 0 1 1 0 00 1 0 0 1 01 1 0 0 1 0 0 0 1 1 0 10 0 0 0 1 018Layout of Graphs78694213501359248067S246871350919Walks and Paths A walk is a sequence of vertices (v1, v2, , vk) in which each adjacent vertex pair is an edge A path is a walk with no repeated vertices23142314Walk (1,2,
15、3,4,2)Path (1,2,3,4)20“The 1stproblem in Graph Theory”Seven Bridges of Knigsberg The city of Knigsberg was set on the River Pregel, and included two large islands which were connected to each other and the mainland by seven bridges. Was it possible to walk a route that crossed each bridge exactly on
16、ce, and return to the starting point?21 An Eulerian path in a graph is a path that uses each edge precisely once. If such path exists, the graph is called traversable Euler showed that an Eulerian cycle exists if and only if all vertices in the graph are of even degree. “The 1stproblem in Graph Theo
17、ry”Seven Bridges of Knigsberg22Weighted Graph A weighted graph associates a value (weight) to every edge in the graph. A weight of a path in a weighted graph is the sum of the weights of the traversed edges. Directed graph (digraph) is a graph with one-way edgesABDECF211137223Today Problem Formulati
18、on Problem solving as state space search Definition of Graphs Types of Graphs Shortest Path problems Dijkstras Algorithm24Shortest Path Problems The shortest path from v1to v2 Is the path of the smallest weight between the two vertices Shortest may be least number of edges, least total weight, etc.
19、The weight of that path is called the distance between them25Shortest Path Problems Example: the weight can be mileage, fares, etc.BOSJFKATLMIALAXSFODENORD957860191109076059560672225341855908245183434926Shortest Path Problems Dijkstras algorithm Finds shortest path for a directed and connected graph
20、 G(V,E) which has non-negative weights. Applications: Internet routing Road generation within a geographic region 27Dijkstras AlgorithmDijkstra(G,w,s) Init_Source(G,s)S := empty set Q := set of all vertices whilewhile Q is not an empty set looploopu := Extract_Min(Q) S := S union u forfor each verte
21、x v which is a neighbor of u loopRelax(u,v,w) 28Dijkstras AlgorithmInit_Source(G,s) forfor each vertex v in VG looploopdv := infinite previousv := 0 ds := 0 v = Extract_Min(Q) searches for the vertex v in the vertex set Q that has the least dv value. That vertex is removed from the set Q and then re
22、turned. Relax(u,v,w)if if dv du + w(u,v) thenthendv := du + w(u,v) previousv := u 29Dijkstras Algorithm010194672325sabdcV = a, b, c, d, sE = (s,c), (c,d), (d,b), (b,d), (c,b), (a,c), (c,a), (a,b), (s,a)S = Q = s, a, b, c, d000000d=prev=30Dijkstras Algorithm010194672325sabdcS = sQ = a, b, c, dExtract
23、_Min (Q) ? sNeighbors of s = a, cRelax (s,c,5)Relax (s,a,10)000000d=prev=0000?105ss10531Dijkstras Algorithm105010194672325sabdcS = s, cQ = a, b, dExtract_Min (Q) ? cNeighbors of c = a, b, dRelax (c,a,3)Relax (c,b,9)Relax (c,d,2)01050s0s0d=prev=050s?8147ccc814732Dijkstras Algorithm81457010194672325sa
24、bdcS = s, c, dQ = a, bExtract_Min (Q) ? dNeighbors of d = bRelax (d,b,6)0814570ccscd=prev=08570csc?13d1333Dijkstras Algorithm81357010194672325sabdcS = s, c, d, aQ = bExtract_Min (Q) ? aNeighbors of a = b, cRelax (a,b,1)Relax (a,c,3)0813570cdscd=prev=0870cc?95as934Dijkstras Algorithm8957010194672325sabdcS = s, c, d, a, bQ = Extract_Min (Q) ? bNeighbors of b = dRelax (b, d, 4)089570cascd=prev=08950cas?7c