DOC PREVIEW
MIT 16 01 - Introduction to Computers and Programming

This preview shows page 1-2-3-4-5-6 out of 17 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 problems– Dijkstra’s Algorithm3Today• Problem Formulation– Problem solving as state space search• Definition of Graphs–Types of Graphs• Shortest Path problems– Dijkstra’s Algorithm4Complex missions must carefully:• Plan complex sequences of actions• Schedule tight resources• Monitor and diagnose behavior• Repair or reconfigure hardware.Ö Most AI problems, like these, may be formulated as state space search.5Simple TrivialAstronautGooseGrainFoxRover• 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 Solving 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• Move(goose,astronaut), Move(astronaut), . . .7AstronautGooseGrainFoxGrainFoxAstronautGooseAstronautGrainFoxGooseGooseAstronautFoxGrainAstronautGooseGrainFoxAstronautGooseGrainFoxGrainAstronautGooseFoxAstronautGooseGrainFoxFoxAstronautGooseGrainAstronautGooseFoxGrainGooseFoxAstronautGrainGooseGrainAstronautFoxAstronautGrainGooseFoxAstronautFoxGooseGrainGooseGrainFoxAstronautGooseGrainFoxAstronaut8AstronautGooseGrainFoxGrainFoxAstronautGooseAstronautGrainFoxGooseGooseAstronautFoxGrainAstronautGooseGrainFoxAstronautGooseGrainFoxGrainAstronautGooseFoxAstronautGooseGrainFoxFoxAstronautGooseGrainAstronautGooseFoxGrainGooseFoxAstronautGrainGooseGrainAstronautFoxAstronautGrainGooseFoxAstronautFoxGooseGrainGooseGrainFoxAstronautAstronautGooseGrainFox9Today•Problem Formulation– Problem solving as state space search• Definition of Graphs– Types of Graphs• Shortest Path problems– Dijkstra’s Algorithm10Graph• 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 edges1 24 53611Examples of GraphsSFOBostonLADallasWash DCAirline RoutesA B CA BCA BCABCPut C on BPut C on APut B on CPut C on AABCPut 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, 3}E = {(1, 2)}241 3V = {1, 2, 3, 4}E = {(1,2)(2,3)(1,4)(2,4)}1V = {1}E = {∅}V = {∅}E = {∅}13Examples of GraphsGraph AirlineRoutes is represented as the pair (V,E)V= {Bos, SFO, LA, Dallas, Wash DC}E= {(SFO,Bos),(SFO,LA),(LA,Dallas),(Dallas,Wash DC)...}SFOBostonLADallasWash DCAirline Routes14Graphs•A loop in a graph is an edge e in E whose endpoints 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.1 24 536A simple graph withV = {1, 2, 3, 4, 5, 6}E = {(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 vertices•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 61 24 53616Vertices•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 undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex.1 24 53617Adjacency 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 jthvertex.1 24 5360 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 Graphs78 69 42 1 3 501 3 5 9 248 0 67S246871350919Walks 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 vertices231 4231 4Walk (1,2,3,4,2)Path (1,2,3,4)20“The 1stproblem in Graph Theory”Seven Bridges of Königsberg• The city of Königsberg 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 once, 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 Theory”Seven Bridges of Königsberg22Weighted 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 edgesA BD ECF211137223Today•Problem Formulation– Problem solving as state space search• Definition of Graphs–Types of Graphs• Shortest Path problems– Dijkstra’s 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.– The weight of that path is called the distance between them25Shortest Path Problems• Example: the weight can be mileage, fares, etc.BOSJFKATLMIALAXSFO DENORD957860191109076059560672225341855908245183434926Shortest Path Problems• Dijkstra’s algorithm– Finds shortest path for a directed and connected graph G(V,E) which has non-negative weights.– Applications: • Internet routing• Road generation within a geographic region•…27Dijkstra’s Algorithm• Dijkstra(G,w,s) Init_Source(G,s)S := empty set Q := set of all vertices while Q is not an empty set loopu := Extract_Min(Q) S := S union {u} for each vertex v which is a neighbor of u loopRelax(u,v,w) 28Dijkstra’s Algorithm• Init_Source(G,s) for each vertex v in V[G] loopd[v] := infinite previous[v] := 0 d[s] := 0 •v = Extract_Min(Q) searches


View Full Document

MIT 16 01 - Introduction to Computers and Programming

Documents in this Course
Fluids

Fluids

3 pages

Fluids

Fluids

4 pages

Fluids

Fluids

4 pages

Fluids

Fluids

5 pages

Load more
Download Introduction to Computers and Programming
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Introduction to Computers and Programming and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Introduction to Computers and Programming 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?