AI Problem Solving Part 1 PDF

By Dr. Mohamed Kazim Khalil Know the concept of Problem Solving. Know what Evolutionary Computation is. Remember processes of Problem Solving. Remember main components that define a problem. Know Search Algorithms types. Differentiate between Informed and Uninformed Search. Differentiate between Li...

By Dr. Mohamed Kazim Khalil Know the concept of Problem Solving. Know what Evolutionary Computation is. Remember processes of Problem Solving. Remember main components that define a problem. Know Search Algorithms types. Differentiate between Informed and Uninformed Search. Differentiate between Linear and Non-linear Data Structures. Differentiate between Queue and Stack Data Structures. Differentiate between Common Types of Graph. Remember basic terminologies in Tree Data Structure. Differentiate between Graph and Tree Data Structures. Differentiate between Traversal and Search. Main Concepts  Problem Solving Problem-solving is the activity of finding sequences of action that will most likely lead to desirable states of the environment (solutions). The agents can be informed or uninformed based on the knowledge they have about how to search for the solution. Human problem solving involves search. Therefore, to simulate human problem solving in a computer we need to develop algorithms for search. In artificial intelligence, problems can be solved by using searching algorithms, evolutionary computations, knowledge representations, etc.  Evolutionary Computation Evolutionary computation is a sub-field of AI and is used extensively in complex optimization problems and for continuous optimization. It is used to solve problems that have too many variables for traditional algorithms. The computational models using evolutionary algorithms apply evolutionary processes in order to solve complex problems. These evolutionary processes are inspired by biological evolution theory. Computers performing evolutionary computing run such evolutionary algorithms as genetic algorithms, evolutionary programming, genetic programming and swarm intelligence models like (ant colony optimization or particle swarm optimization).  Problem Solving Processes 1) Define the problem. 2) Analyze the problem. 3) Identification of possible solutions. 4) Choosing the optimal solution. 5) Implementation.  Problem Formulation Problem formulation involves deciding what actions and states to consider, given the goal. A problem can be defined formally by the following components: Initial State  The state from which the agent infers that it is at the beginning (Starting point) Goal state  The solution or desired outcome. Operators  The possible moves the allow the agent to get from the initial to the goal state. (Actions)  It is description of possible actions (that change the state of the world) and their outcome. State Space  All states reachable from initial by any sequence of actions.  A path: is any sequence of actions that lead from one state to another  It is the desired end result that the system aims to reach. Goal test  In AI problem-solving, finding a path from the initial state to the goal state is the main objective of the state space search process. Cost  What costs of moving from moving from each state (making an action) Heuristics  Guides of the search process.  Types of Search Algorithms Search Algorithms Uninformed Search Informed Search Depth-First Breadth- Uniform Greedy Graph A* Search Search First Search Cost Search Search Search  Difference between Informed and Uninformed Search Uninformed search:  It also called Blind search.  It is a search that has no information about its domain.  It not has additional information about state or search space other than how to traverse the tree, so it is also called blind search.  The plans to reach the goal state from the start state differ only by the order and length of actions.  The only thing that a blind search can do is distinguish a non-goal state from a goal state.  Example: Depth First Search, Breadth-First Search and Uniform Cost Search.  Difference between Informed and Uninformed Search Informed Search:  It has information on the goal state which helps in more efficient searching. This information is obtained by a function that estimates how close a state is to the goal state.  Example: A* Search, Greedy Search and Graph Search.  Difference between Informed and Uninformed Search Uninformed Search Informed Search It doesn’t use knowledge for searching It uses knowledge for the searching process. process. It finds solution slow as compared to It finds solution more quickly. informed search. It is mandatory efficient. It is highly efficient. Cost is high. Cost is low. It consumes less time. It consumes moderate time. No suggestion is given regarding the It provides the direction regarding the solution in it. solution. It is more lengthy while implementation. It is less lengthy while implementation. Depth First Search, Breadth First Search Greedy Search, A* Search, Graph Search Linear and Non-linear Data Structures  Linear vs. Non-linear Data Structures Before knowing about the graph and tree data structure, we should know the linear and non- linear data structures.  What is Linear Data Structure? Linear data structure is a structure in which all the elements are arranged sequentially or linearly where each and every element is attached to its previous and next adjacent is called a linear data structure. In linear data structure, single level is involved. Therefore, we can traverse all the elements in single run only. Linear data structures are easy to implement because computer memory is arranged in a linear way. Its examples are array, linked list, stack, queue, etc.  Types of Linear Data Structure  Array:  It is the most basic and fundamental data structures.  Array is a type of data structure that stores elements of the same type.  An Array is a collection of items stored at contiguous memory locations.  Data stored in each position of an array is given a positive value called the index of the element. The index helps in identifying the location of the elements in an array.  Types of Linear Data Structure  Linked List:  A Linked List is a linear data structure, in which the elements are not stored at contiguous memory locations.  Linked lists are the types where the data is stored in the form of nodes which consist of an element of data and a pointer.  The use of the pointer is that it points or directs to the node which is next to the element in the sequence. The data stored in a linked list might be of any form, strings, numbers, or characters.  Types of Linear Data Structure  Stack:  Stack is a linear data structure which follows a particular order in which the operations are performed.  The order may be LIFO (Last In-First Out) or FILO (First In-Last Out).  Types of Linear Data Structure  Stack:  Push operation is used for adding an element of data on a stack, and the pop operation is used for deleting the data from the stack.  Types of Linear Data Structure  Stack:  This can be explained by the example of books stacked together. In order to access the last book, all the books placed on top of the last book have to be safely removed.  Types of Linear Data Structure  Queue:  A Queue is defined as a linear data structure which is open at both ends and the operations are performed in FIFO (First-In First-Out) or LILO (Last-In Last-Out) order.  The element which is first pushed into order, the operation is first performed on that. This means that the first added element is to exit the queue first.  Types of Linear Data Structure  Queue:  Front and Rear are the two terms to be used in a queue.  The data structure might be explained with the example of people queuing up to ride a bus. The first person in the line will get the chance to exit the queue while the last person will be the last to exit.  What is Non-linear Data Structure? Data structures where data elements are not arranged sequentially or linearly are called non-linear data structures. In a non-linear data structure, single level is not involved. Therefore, we can’t traverse all the elements in single run only. Non-linear data structures are not easy to implement in comparison to linear data structure. It utilizes computer memory efficiently in comparison to a linear data structure. Its examples are trees and graphs.  Types of Non-linear Data Structure  Trees:  A tree data structure consists of various nodes linked together.  The structure of a tree is hierarchical that forms a relationship like that of the parent and a child.  The structure of the tree is formed in a way that there is one connection for every parent-child node relationship.  Only one path should exist between the root to a node in the tree.  Types of Non-linear Data Structure  Graph:  Graphs are those types of non-linear data structures which consist of a definite quantity of vertices and edges.  The vertices or the nodes are involved in storing data and the edges or the path show the vertices relationship.  The difference between a graph to a tree is that in a graph there are no specific rules for the connection of nodes.  Real-life problems like social networks, telephone networks, etc. can be represented through the graphs. Graphs and Trees  What is Graph A Graph is a non-linear data structure consisting of a set of vertices (V) and edges (E). The vertices are sometimes also referred to as nodes. The edges are lines or arcs that connect any two nodes in the graph. The graph is denoted by G(V, E).  What is Graph Graph data structures are a powerful tool for representing and analyzing complex relationships between objects or entities. They are particularly useful in fields such as social network analysis, recommendation systems, and computer networks.  Applications of the Graphs Graphs are used to solve many real-life problems. Graphs are utilized to represent the networks. These networks may include telephone or circuit networks or paths in a city.  Applications of the Graphs For example, we could use Graphs to design a transportation network model where the vertices display the facilities [‫ ]المرافق‬that send or receive the products, and the edges represent roads or paths connecting them. The following is a pictorial representation of the same:  Common Types of Graph Undirected Graph: A graph in which edges do not have any direction. That is the nodes are unordered pairs in the definition of every edge. Directed Graph: A graph in which edge has direction. That is the nodes are ordered pairs in the definition of every edge.  Common Types of Graph Connected Graph: The graph in which from one node we can visit any other node in the graph is known as a connected graph. Disconnected Graph: The graph in which at least one node is not reachable from a node is known as a disconnected graph.  Common Types of Graph Weighted Graph:  A graph in which the edges are already specified with suitable weight is known as a weighted graph.  A Graph is said to be Weighted if each edge is assigned a 'weight'. The weight of an edge can denote distance, time, or anything that models the 'connection' between the pair of vertices it connects.  Weighted graphs can be further classified as directed weighted graphs and undirected weighted graphs.  What is Tree data structure? A tree data structure is a hierarchical structure that is used to represent and organize data in a way that is easy to navigate and search. It is a collection of nodes that are connected by edges and has a hierarchical relationship between the nodes.  What is Tree data structure? The topmost node of the tree is called the root, and the nodes below it are called the child nodes. Each node can have multiple child nodes, and these child nodes can also have their own child nodes, forming a recursive structure. Only one path should exist between the root to a node in the tree. We can also say that tree data structure has roots, branches, and leaves connected with one another. Basic Terminologies in Tree Data Structure  Basic Terminologies in Tree Data Structure  Parent Node:  The node which is a predecessor [‫ ]سابقة‬of a node is called the parent node of that node.  {B} is the parent node of {D, E}.  Child Node:  The node which is the immediate successor [‫ ]تخلف‬of a node is called the child node of that node.  Examples: {D, E} are the child nodes of {B}.  Basic Terminologies in Tree Data Structure  Root Node:  The topmost node of a tree or the node which does not have any parent node is called the root node.  {A} is the root node of the tree. A non-empty tree must contain exactly one root node and exactly one path from the root to all other nodes of the tree.  Leaf Node or External Node:  The nodes which do not have any child nodes are called leaf nodes.  {K, L, M, N, O, P, G} are the leaf nodes of the tree.  Basic Terminologies in Tree Data Structure  Ancestor [‫ ]أسالف‬of a Node:  Any predecessor nodes [‫ ]عقد سابقة‬on the path of the root to that node are called Ancestors of that node.  {A, B} are the ancestor nodes of the node {E}  Descendant [‫]األحفاد‬:  Any successor node on the path from the leaf node to that node.  {E,I} are the descendants of the node {B}.  Sibling ]‫ [األشقاء‬:  Children of the same parent node are called siblings.  {D,E} are called siblings.  Basic Terminologies in Tree Data Structure  Level of a node:  The count of edges on the path from the root node to that node.  The root node has level 0.  Internal node:  A node with at least one child is called Internal Node.  Neighbour of a Node:  Parent or child nodes of that node are called neighbors of that node.  Subtree:  Any node of the tree along with its descendant.  Graph Vs. Tree In the programming world, trees and graphs are important factors and depict nonlinear data. A tree is an exceptional case of a graph which does not loop whereas graphs can have loops. Both graph and tree share some common features, but they do have some differences.  Difference between Graph and Tree Graph Tree It is a non-linear data structure. It is also a non-linear data structure. A graph is a set of A tree is a set of nodes and edges. vertices/nodes and edges. In the graph, there is no unique In a tree, there is a unique node node which is known as root. which is known as root. Each node can have several Usually, a tree can have several child edges. nodes, and in the case of binary trees, each node consists of two child nodes. Graphs can form cycles. Trees cannot form a cycle.  Traversal vs. Search Traversal is a process to visit all the nodes of a tree and may print their values too. So, it involves examining every node in the tree. Search involves visiting nodes in a graph in a systematic manner, and may or may not result into a visit to all. If Search results into a visit to all the vertices, it is called Traversal. ‫وباهلل التوفيق‬