Anna University Regulation 2013 Information Technology (IT) CS6659 AI Notes for all 5 units are provided below. Download link for IT 6th SEM CS6659 Artificial Intelligence Lecture Notes are listed down for students to make perfect utilization and score maximum marks with our study materials.
Search:
Formulate a problem as a state space search by showing the legal problem states, the legal operators, and the initial and goal states .
• A state is defined by the specification of the values of all attributes of interest in the world
• An operator changes one state into the other; it has a precondition which is the value of certain attributes prior to the application of the operator, and a set of effects, which are the attributes altered by the operator
• The initial state is where you start
• The goal state is the partial description of the solution
State Space Search Notations
The set of notations involved in the state space search is :
1) An initial state is the description of the starting configuration of the agent
2) An action or an operator takes the agent from one state to another state which is called a successor state. A state can have a number of successor states.
3) A plan is a sequence of actions. The cost of a plan is referred to as the path cost.
Problem formulation & Problem Definition
Problem formulation means choosing a relevant set of states to consider, and a feasible set of operators for moving from one state to another.
Search is the process of considering various possible sequences of operators applied to the initial state, and finding out a sequence which culminates in a goal state.
A search problem consists of the following:
• S: the full set of states
• s0 : the initial state
• A:S→S is a set of operators
• G is the set of final states. Note that G ⊆S The search problem is to find a sequence of actions which transforms the agent from the initial state to a goal state g∈G.
A simple search procedure is
Do until a solution is found or the state space is exhausted.
1. Check the current state
2. Execute allowable actions to find the successor states.
3. Pick one of the new states.
4. Check if the new state is a solution state
If it is not, the new state becomes the current state and the process is repeated
Basic Search Algorithm is
Let L be a list containing the initial state (L= the fringe)
Loop if L is empty return failure
Node <- select (L)
if Node is a goal
then return Node (the path from initial state to Node)
else generate all successors of Node, and merge the newly generated states into L
End Loop
Factors to measure the search Algorithms:
1. Complete
2. Optimal
3. What is the search cost associated with the time and memory required to find a solution?
a. Time complexity b. Space complexity
The different search strategies that we will consider include the following:
1. Blind Search strategies or Uninformed search
a. Depth first search b. Breadth first search
c. Iterative deepening search d. Iterative broadening search
2. Informed Search
3. Constraint Satisfaction Search
Blind search:
Blind search or uninformed search that does not use any extra information about the problem domain.
The two common methods of blind search are:
• BFS or Breadth First Search
• DFS or Depth First Search
Search Tree is helpful for the searching the goal node. The terminologies involved in the search tree is Root Node: The node from which the search starts. Leaf Node: A node in the search tree having no children.
Ancestor/Descendant: X is an ancestor of Y is either X is Y’s parent or X is an ancestor of the parent of Y. If S is an ancestor of Y, Y is said to be a descendant of X.
Branching factor: the maximum number of children of a non-leaf node in the search tree Path: A path in the search tree is a complete path if it begins with the start node and ends with a goal node. Otherwise it is a partial path.
Breadth First Search
Let Queue be a list containing the initial state
Loop if Queue is empty return failure Node remove-first (fringe)
if Node is a goal
then return the path from initial state to Node
else generate all successors of Node, and
(merge the newly generated nodes into fringe)
add generated nodes to the back of Queue
End Loop
Advantages of Breadth First Search
Finds the path of minimal length to the goal.
Disadvantages of Breadth First Search
Requires the generation and storage of a tree whose size is exponential the the depth of the shallowest goal node
Depth First Search
Let Queue be a list containing the initial state
Loop if Queue is empty return failure
Node<-remove-first (fringe)
if Node is a goal
then return the path from initial state to Node
else generate all successors of Node,
and merge the newly generated nodes into Queue
add generated nodes to the front of Queue
End Loop
Depth Limited Search
Let fringe be a list containing the initial state
Loop if fringe is empty return failure
Node<-remove-first (fringe)
if Node is a goal
then return the path from initial state to Node
else if depth of Node = limit return cutoff
else add generated nodes to the front of fringe
End Loop
Depth-First Iterative Deepening (DFID)
CS6659 AI Unit 1 notes – Download Here
CS6659 AI Unit 2 notes – Download Here
CS6659 AI Unit 3 notes – Download Here
CS6659 AI Unit 4 notes – Download Here
CS6659 AI Unit 5 notes – Download Here
If you require any other notes/study materials, you can comment in the below section.
Related Links
For CS6659 AI Previous Year Question Papers – Click here
For CS6659 AI Question Bank/2marks 16marks with answers – Click here
For CS6659 AI Important Questions/Answer Key – Click here
Search Terms
Anna University 6th SEM IT AI Lecture Notes
CS6659 Artificial Intelligence Notes free download
Anna University IT AI Notes Regulation 2013
CS6659 Notes, AI Unit wise Lecture Notes – IT 6th Semester