Chapter 2 - General Representation of AI problems.pptx

Department of Computer Sciences College of Computers & Information Technology 501481-3 Artificial Intelligence Chapter 2: General Representation of AI problems 1  AI Problem As...

Department of Computer Sciences College of Computers & Information Technology 501481-3 Artificial Intelligence Chapter 2: General Representation of AI problems 1  AI Problem Assume: P is an AI problem. P has an initial configuration called the initial state (s ). The solution of P is called the goal state (G). To find a solution to the problem P: – We will start from the start state s. – Apply an action to s to get a new state s1. – Apply an action to s1 to get a new state s2. – Keep applying actions until we reach the goal G. Artificial Intelligence 2 12:32 PM  Problem Solving in AI Problem solving is a technique to reach the goal G from the start state s. A search space is all possible actions applied to a state si to get a new state sj for all states si and sj. Artificial Intelligence 3 12:32 PM  //Problem Solving in AI Problem solving can be converted into a graph where nodes are the problem states and edges are actions. All the nodes in the graph are called the search space. Search space is defined as all the possible states of the problem. Artificial Intelligence 4 12:32 PM  /Representation of search problems Graphs and Trees A search problem is represented using a: Directed graph : – The states are represented as nodes. – The allowed actions are represented as arcs. Undirected graph : – Edges does not imply directions. Weighted graph: – Edges may have weight (cost). Lecture 3: introduction to state space Artificial Intelligence search 5  Representation of search problems Graph and tree A path is a sequence of edges. – Example :p=(A,D),(D,E),(E,F),(F,B) or – Or a sequence of nodes p=A,D,E,F,F Loop (cycle) may exist in a graph. – Edges lead back to the original node. – l=(A,D),(D,E),(E,F),(F,B),(B,A) or l=A,D,E,F,F,A Graph is connected if for any pair of nodes there is a path between them. Lecture 3: introduction to state space Artificial Intelligence search 6  Other Graph representation Techniques: Adjacency Matrix  Adjacency matrix A( N x N matrix)-undirected graph  A[i, j]=1: an edge exist between nodes i and j.  A[i, j]=0: no edge exist between nodes i and j.  Row represents source, Column represents destination. Lecture 3: introduction to state space Artificial Intelligence search 7  Other Graph representation Techniques: Adjacency Matrix  Adjacency matrix for a directed graph  Rows identify source nodes.  Columns identify destination nodes. Lecture 3: introduction to state space Artificial Intelligence search 8