Lecture notes on Artificial Intelligence

what is artificial intelligence and its applications, what is artificial intelligence and expert systems, what is artificial intelligence characteristics pdf free download
Dr.DavisHardy Profile Pic
Published Date:22-07-2017
Your Website URL(Optional)
Paper Code : MCA 402 Author :Om Parkash Lesson No. 01 Vettor : Saroj Lesson Name: Scope of Artificial Intelligence ____________________________________________________ Structure 1.0 Objectives 1.1 Introduction 1.2 Applications of AI 1.2.1 Games 1.2.2 Theorem Proving 1.2.3 Natural Language Processing 1.2.4 Vision and Speech Processing 1.2.5 Robotics 1.2.6 Expert Systems 1.3 AI Techniques 1.3.1 Knowledge Representation 1.3.2 Search Technique 1.4 Search Knowledge 1.5 Abstraction 1.5 Summary 1.6 Self Assessment Questions 1.0 Objective The objective of this lesson is to provide an introduction to the definitions, techniques, components and applications of Artificial Intelligence. Upon completion of this lesson students should able to answer the AI problems, Techniques, and games. This lesson also gives an overview about expert system, search knowledge and abstraction. 1.1 Introduction Artificial Intelligence (AI) is the area of computer science focusing on creating machines that can engage on behaviors that humans consider intelligent. The ability to create intelligent machines has intrigued humans since ancient times, and today with the advent of the computer and 50 years of research into AI programming techniques, the dream of smart machines is becoming a reality. Researchers are creating systems which can mimic human thought, understand speech, beat the best human chess player, and countless other feats never before possible. What is Artificial Intelligence (AI)? According to Elaine Rich, “Artificial Intelligence “ “Artificial Intelligence is the study of how to make computers do things at which, at the moment, people are better”. 1 In what way computer & Human Being are better? Computers Human Being 1. Numerical Computation is fast 1. Numerical Computation is slow 2. Large Information Storage Area 2. Small Information Storage Area 3. Fast Repetitive Operations 3. Slow Repetitive Operations 4. Numeric Processing 5. Symbolic Processing 5.Computers are just Machine 4. Human Being is intelligent (make (Performed Mechanical “Mindless” sense from environment) Activities) Other Definitions of Artificial Intelligence According to Avron Barr and Edward A. Feigenbaum, “ The Handbook of Artificial Intelligence”, the goal of AI is to develop intelligent computers. Here intelligent computers means that emulates intelligent behavior in humans. “Artificial Intelligence is the part of computer science with designing intelligent computer systems, that is, systems that exhibit the characteristics we associate with intelligence in human behavior.” Other definitions of AI are mainly concerned with symbolic processing, heuristics, and pattern matching. Symbolic Processing According to Bruce Buchanan and Edward Shortliffe” Rule Based Expert Systems” (reading MA: Addison-Wesley, 1984), p.3. “Artificial Intelligence is that branch of computer science dealing with symbolic, non algorithmic methods of problem solving.” Heuristics According to Bruce Buchanan and Encyclopedic Britannica, heuristics as a key element of a Artificial Intelligence: “Artificial Intelligence is branch of computer science that deals with ways of representing knowledge using symbols rather than numbers and with rules-of-thumb or heuristics, methods for processing information.” A heuristics is the “rule of thumb” that helps us to determine how to proceed. Pattern Matching 2According to Brattle Research Corporation, Artificial Intelligence and Fifth Generation Computer Technologies, focuses on definition of Artificial Intelligence relating to pattern matching. “In simplified terms, Artificial Intelligence works with the pattern matching methods which attempts to describe objects, events, or processes in terms of their qualitative features and logical and computational relationships.” Here this definition focuses on the use of pattern matching techniques in an attempt to discover the relationships between activities just as human do. 1.2 Application of Artificial Intelligence Games Game playing is a search problem Defined by – Initial state – Successor function – Goal test – Path cost / utility / payoff function Games provide a structured task wherein success or failure can be measured with latest effort. Game playing shares the property that people who do them well are considered to be displaying intelligence. There are two major components of game playing, viz., a plausible move generator, and a static evaluation function generator. Plausible move generator is used to expand or generates only selected moves. Static evaluation function generator, based on heuristics generates the static evaluation function value for each & every move that is being made. Chess AI-based game playing programs combine intelligence with entertainment. On game with strong AI ties is chess. World-champion chess playing programs can see ahead twenty plus moves in advance for each move they make. In addition, the programs have an ability to get progressably better over time because of the ability to learn. Chess programs do not play chess as humans do. In three minutes, Deep Thought (a master program) considers 126 million moves, while human chessmaster on average considers less than 2 moves. Herbert Simon suggested that human chess masters are familiar with favorable board positions, and the relationship with thousands of pieces in small areas. Computers on the other hand, do not take hunches into account. The next move comes from exhaustive searches into all moves, and the consequences of the moves based on prior learning. Chess programs, running on Cray super computers have attained a rating of 2600 (senior master), in the range of Gary Kasparov, the Russian world champion. 3 Characteristics of game playing 9 “Unpredictable” opponent. Solution is a strategy specifying a move for every possible opponent reply. 9 Time limits. Unlikely to find goal, must approximate. 1.2.2 Theorem Proving Theorem proving has the property that people who do them well are considered to be displaying intelligence. The Logic Theorist was an early attempt to prove mathematical theorems. It was able to prove several theorems from the Qussells Principia Mathematica. Gelernters’ theorem prover explored another area of mathematics: geometry. There are three types of problems in A.I. Ignorable problems, in which solution steps can be ignored; recoverable problems in which solution steps can be undone; irrecoverable in which solution steps cannot be undone. Theorem proving falls into the first category i.e. it is ignorable suppose we are trying to solve a theorem, we proceed by first proving a lemma that we think will be useful. Eventually we realize that the lemma is not help at all. In this case we can simply ignore that lemma, and can start from beginning. There are two basics methods of theory proving. 9 Start with the given axioms, use the rules of inference and prove the theorem. 9 Prove that the negation of the result cannot be TRUE. 1.2.3 Natural Language Processing The utility of computers is often limited by communication difficulties. The effective use of a computer traditionally has involved the use of a programming language or a set of commands that you must use to communicate with the computer. The goal of natural language processing is to enable people and computer to communicate in a “natural “(human) language, such as a English, rather than in a computer language. The field of natural language processing is divided into the two sub-fields of: 9 Natural language understanding, which investigates methods of allowing computer to comprehend instruction given in ordinary English so that computers can understand people more easily. 49 Natural language generation, which strives to have computers produce ordinary English language so that people can understand computers more easily. 1.2.4 Vision and Speech Processing The focus of natural language processing is to enable computers to communicate interactively with English words and sentences that are typed on paper or displayed on a screen. However, the primary interactive method of communication used by humans is not reading and writing; it is speech. The goal of speech processing research is to allow computers to understand human speech so that they can hear our voices and recognize the words we are speaking. Speech recognition research seeks to advance the goal of natural language processing by simplifying the process of interactive communication between people and computers. It is a simple task to attach a camera to computer so that the computer can receive visual images. It has proven to be a far more difficult task, however, to interpret those images so that the computer can understand exactly what it is seeing. People generally use vision as their primary means of sensing their environment; we generally see more than we hear, feel, smell or taste. The goal of computer vision research is to give computers this same powerful facility for understanding their surroundings. Currently, one of the primary uses of computer vision is in the area of robotics. 1.2.5 Robotics A robot is an electro-mechanical device that can be programmed to perform manual tasks. The Robotic Industries Association formally defines a robot as “a reprogrammable multi-functional manipulator designed to move material, parts, tools or specialized devices through variable programmed motions for the performance of a variety of tasks.” An “intelligent” robot includes some kind of sensory apparatus, such as a camera, that allows it to respond to changes in its environment, rather than just to follow instructions “mindlessly.” 1.2.6 Expert System An expert system is a computer program designed to act as an expert in a particular domain (area of expertise). Also known as a knowledge-based system, an expert system typically includes a sizable knowledge base, consisting of facts about the domain and heuristics (rules) for applying those facts. Expert system currently is designed to assist experts, not to replace them. They have proven to be useful in diverse areas such as computer system configuration. 5A ``knowledge engineer'' interviews experts in a certain domain and tries to embody their knowledge in a computer program for carrying out some task. How well this works depends on whether the intellectual mechanisms required for the task are within the present state of AI. When this turned out not to be so, there were many disappointing results. One of the first expert systems was MYCIN in 1974, which diagnosed bacterial infections of the blood and suggested treatments. It did better than medical students or practicing doctors, provided its limitations were observed. Namely, its ontology included bacteria, symptoms, and treatments and did not include patients, doctors, hospitals, death, recovery, and events occurring in time. Its interactions depended on a single patient being considered. Since the experts consulted by the knowledge engineers knew about patients, doctors, death, recovery, etc., it is clear that the knowledge engineers forced what the experts told them into a predetermined framework. In the present state of AI, this has to be true. The usefulness of current expert systems depends on their users having common sense. 1.3 AI Techniques There are various techniques that have evolved that can be applied to a variety of AI tasks - these will be the focus of this course. These techniques are concerned with how we represent, manipulate and reason with knowledge in order to solve problems. 1.3.1 Knowledge Representation Knowledge representation is crucial. One of the clearest results of artificial intelligence research so far is that solving even apparently simple problems requires lots of knowledge. Really understanding a single sentence requires extensive knowledge both of language and of the context. For example, today's (4th Nov) headline ``It's President Clinton'' can only be interpreted reasonably if you know it's the day after the American elections. Yes, these notes are a bit out of date. Really understanding a visual scene similarly requires knowledge of the kinds of objects in the scene. Solving problems in a particular domain generally requires knowledge of the objects in the domain and knowledge of how to reason in that domain - both these types of knowledge must be represented. Knowledge must be represented efficiently, and in a meaningful way. Efficiency is important, as it would be impossible (or at least impractical) to explicitly represent every fact that you might ever need. There are just so many potentially useful facts, most of which you would never even think of. You have to be able to infer new facts from your existing knowledge, as and when needed, and capture general abstractions, which represent general features of sets of objects in the world. Knowledge must be meaningfully represented so that we know how it relates back to the real world. A knowledge representation scheme provides a mapping from features of the world to a formal language. (The formal language will just 6capture certain aspects of the world, which we believe are important to our problem - we may of course miss out crucial aspects and so fail to really solve our problem, like ignoring friction in a mechanics problem). Anyway, when we manipulate that formal language using a computer we want to make sure that we still have meaningful expressions, which can be mapped back to the real world. This is what we mean when we talk about the semantics of representation languages. 1.3.2 Search Another crucial general technique required when writing AI programs is search. Often there is no direct way to find a solution to some problem. However, you do know how to generate possibilities. For example, in solving a puzzle you might know all the possible moves, but not the sequence that would lead to a solution. When working out how to get somewhere you might know all the roads/buses/trains, just not the best route to get you to your destination quickly. Developing good ways to search through these possibilities for a good solution is therefore vital. Brute force techniques, where you generate and try out every possible solution may work, but are often very inefficient, as there are just too many possibilities to try. Heuristic techniques are often better, where you only try the options, which you think (based on your current best guess) are most likely to lead to a good solution. 1.4 Search Knowledge In order to solve the complex problems encountered in artificial intelligence, one needs both a large amount of knowledge and some mechanisms for manipulating that knowledge to create solutions to new problems. That is if we have knowledge that it is sufficient to solve a problem, we have to search our goal in that knowledge. To search a knowledge base efficiently, it is necessary to represent the knowledge base in a systematic way so that it can be searched easily. Knowledge searching is a basic problem in Artificial Intelligence. The knowledge can be represented either in the form of facts or in some formalism. A major concept is that while intelligent programs recognize search, search is computationally intractable unless it is constrained by knowledge about the world. In large knowledge bases that contain thousands of rules, the intractability of search is an overriding concern. When there are many possible paths of reasoning, it is clear that fruitless ones not be pursued. Knowledge about path most likely to lead quickly to a goal state is often called search control knowledge. 1.5 Abstraction Abstraction a mental facility that permits humans to view real-world problems with varying degrees of details depending on the current context of the problem. Abstraction means to hide the details of something. For example, if we want to compute the square root of a number then we simply call the function sort in C. 7We do not need to know the implementation details of this function. Early attempts to do this involved the use of macro-operators, in which large operators we built from smaller one’s. But in this approach, no details were eliminated from actual description of the operators. A better approach was developed in the ABSTRIPS system, which actually planned in a hierarchy of abstraction spaces, in each of which preconditions at a lower level of abstraction, was ignored. 1.6 Summary In this chapter, we have defined AI, other definitions of AI & terms closely related to the field. Artificial Intelligence (AI) is the part of computer science concerned with designing intelligent computer systems, that is, systems that exhibit the characteristics. We associate with intelligence in human behavior, other definition of AI are concerned with symbolic processing, heuristics, and pattern matching. Artificial intelligence problems appear to have very little in common except that they are hard. Areas of AI research have been evolving continually. However, as more people identify research-taking place in a particular area as AI, that are will tend to remain a part of AI. This could result in a more static definition of Artificial Intelligence. Currently, the most well known area of AI research is expert system, where programs include expert level knowledge of a particular field in order to assist experts in that field. Artificial Intelligence is best understood as an evolution rather than a revolution, some of popular application areas of AI include games, theorem proving, natural language processing, vision, speech processing, and robotics. 1.7 Key Words Artificial Intelligence (AI), Games, Theorem Proving, Vision and Processing, Natural Language Processing, Robotics, Expert System, Search Knowledge. 8 1.8 Self Assessment Questions (SAQ) Q1. A key element of AI is a/an _________, which is a “rule of thumb”. a. Heuristics b. Cognition c. Algorithm d. Digiton Q2. One definition of AI focuses on problem solving methods that process: a. Numbers b. Symbols c. Actions d. Algorithms Q3 Intelligent planning programs may be of speed value to managers with ________ Responsibilities. a. Programming b. Customer source c. Personal administration d. Decision making Q4. What is AI? Explain different definition of AI with different application of AI. Q5. Write short note on the following: - a. Robotics b. Expert system c. Natural Language Processing d. Vision of Speech Processing 9 Reference/Suggested Reading 9 Foundations of Artificial Intelligence and Expert System - V S Janakiraman, K Sarukesi, & P Gopalakrishanan, Macmillan Series. 9 Artificial Intelligence – E. Rich and K. Knight 9 Principles of Artificial Intelligence – Nilsson 9 Expert Systems-Paul Harmon and David King, Wiley Press. 9 Rule Based Expert System-Bruce G. Buchanan and Edward H. Shortliffe, eds., Addison Wesley. 9 Introduction to Artificial Intelligence and Expert System- Dan W. Patterson, PHI, Feb., 2003. 10 Paper Code : MCA 402 Author :Om Parkash Lesson No. 02 Vettor : Saroj Lesson Name: Problem Solving Structure 2.0 Objectives 2.1 Defining state space of the problem 2.2 Production Systems 2.3 Search Space Control 2.4 Breadth First Search 2.5 Depth First Search 2.6 Heuristic Search Techniques 2.7 Hill Climbing 2.8 Best First Search 2.9 Branch and Bound 2.10 Problem Reduction 2.11 Constraints Satisfaction 2.12 Means End Analysis 2.13 Summary 2.14 Self Assessment Questions 2.0 Objective The objective of this lesson is to provide an overview of problem representation techniques, production system, search space control and hill climbing. This lesson also gives in depth knowledge about the searching techniques. After completion of this lesson, students are able to tackle the problems related to problem representation, production system and searching techniques. 2.1 Introduction Before a solution can be found, the prime condition is that the problem must be very precisely defined. By defining it properly, one can convert it into the real workable states that are really understood. These states are operated upon by a set of operators and the decision of which operator to be applied, when and where is dictated by the overall control strategy. Problem must be analysed. Important features land up having an immense impact on the appropriateness of various possible techniques for solving the problem. 11Out of the available solutions choose the best problem-solving technique(s) and apply the same to the particular problem. 2.2 Defining state space of the problem A set of all possible states for a given problem is known as state space of the problem. Representation of states is highly beneficial in AI because they provide all possible states, operations and the goals. If the entire sets of possible states are given, it is possible to trace the path from the initial state to the goal state and identify the sequence of operators necessary for doing it. Example: Problem statement "Play chess." To discuss state space problem, let us take an example of “play chess”. Inspite of the fact that there are a many people to whom we could say that and reasonably expect that they will do as we intended, as our request now stands its quite an incomplete statement of the problem we want solved. To build a program that could "Play chess," first of all we have to specify the initial position of the chessboard, any and every rule that defines the legal move, and the board positions that represent a win for either of the sides. We must also make explicit the previously implicit goal of not only playing a legal game of chess but also goal towards winning the game. Figure 2.1: One Legal Chess Move Its quite easy to provide an acceptable complete problem description for the problem "Play chess,” The initial position can be described as an 8-by-8 array 12where each position contains a symbol standing for the appropriate piece in the official chess opening position. Our goal can be defined as any board position in which either the opponent does not have a legal move or opponent’s king is under attack. The path for getting the goal state from an initial state is provided by the legal moves. Legal moves are described easily as a set of rules consisting of two parts: a left side that serves as a pattern to be matched against the current board position and a right side that describes the change to be made to the board position to reflect the move. There are several ways in which these rules can be written. For example, we could write a rule such as that shown in Figure 2.1. In case we write rules like the one above, we have to write a very large number 120 of them since there has to be a separate rule for each of the roughly 10 possible board positions. Using so many rules poses two serious practical difficulties: • We will not be able to get a complete set of rules. If at all we manage then it is likely to take too long and will certainly be consisting of mistakes. • Any program will not be able to handle these many rules. Although a hashing scheme could be used to find the relevant rules for each move fairly quickly, just storing that many rules poses serious difficulties. One way to reduce such problems could possibly be that write the rules describing the legal moves in as general a way as possible. To achieve this we may introduce some convenient notation for describing patterns and substitutions. For example, the rule described in Figure 2.1, as well as many like it, could be written as shown in Figure 2.2. In general, the more efficiently we can describe the rules we need, the less work we will have to do to provide them and the more efficient the program that uses them can be. Figure 2.2: Another Way to Describe Chess Moves Problem of playing chess has just been described as a problem of moving around, in a state space, where a legal position represents a state of the board. Then we play chess by starting at an initial state, making use of rules to move from one state to another, and making an effort to end up in one of a set of final states. This state space representation seems natural for chess because the set of states, which corresponds to the set of board positions, is artificial and well organized. This same kind of representation is also useful for naturally occurring, 13less well-structured problems, although we may need to use more complex structures than a matrix to describe an individual state. The basis of most of the AI methods we discuss here is formed by the State Space representations. Its structure corresponds to the structure of problem solving in two important ways: 9 Representation allows for a formal definition of a problem using a set of permissible operations as the need to convert some given situation into some desired situation. 9 We are free to define the process of solving a particular problem as a combination of known techniques, each of which are represented as a rule defining a single step in the space, and search, the general technique of exploring the space to try to find some path from the current state to a goal state. Search is one of the important processes the solution of hard problems for which none of the direct techniques is available. 2.3 Production Systems A production system is a system that adapts a system with production rules. A production system consists of: • A set of rules, each consisting of a left side and a right hand side. Left hand side or pattern determines the applicability of the rule and a right side describes the operation to be performed if the rule is applied. • One or more knowledge/databases that contain whatever information is appropriate for the particular task. Some parts of the database may be permanent, while other parts of it may pertain only to the solution of the current problem. The information in these databases may be structured in any appropriate way. • A control strategy that specifies the order in which the rules will be compared to the database and a way of resolving the conflicts that arise when several rules match at once. • A rule applier. Production System also encompasses a family of general production system interpreters, including: • Basic production system languages, such as OPS5 and ACT • More complex, often hybrid systems called expert system shells, which provide complete (relatively speaking) environments for the construction of knowledge-based expert systems. 14• General problem-solving architectures like SOAR Laird et al., 1987, a system based on a specific set of cognitively motivated hypotheses about the nature of problem solving. Above systems provide the overall architecture of a production system and allow the programmer to write rules that define particular problems to be solved. In order to solve a problem, firstly we must reduce it to one for which a precise statement can be given. This is done by defining the problem's state space, which includes the start and goal states and a set of operators for moving around in that space. The problem can then be solved by searching for a path through the space from an initial state to a goal state. The process of solving the problem can usefully be modelled as a production system. In production system we have to choose the appropriate control structure so that the search can be as efficient as possible. 2.4 Search Space Control The next step is to decide which rule to apply next during the process of searching for a solution to a problem. This decision is critical since often more than one rule (and sometimes fewer than one rule) will have its left side match the current state. We can clearly see what a crucial impact they will make on how quickly, and even whether, a problem is finally solved. There are mainly two requirements to of a good control strategy. These are: 1. A good control strategy must cause motion 2. A good control strategy must be systematic: A control strategy is not systematic; we may explore a particular useless sequence of operators several times before we finally find a solution. The requirement that a control strategy be systematic corresponds to the need for global motion (over the course of several steps) as well as for local motion (over the course of a single step). One systematic control strategy for the water jug problem is the following. Construct a tree with the initial state as its root. Generate all the offspring of the root by applying each of the applicable rules to the initial state. Now, for each leaf node, generate all its successors by applying all the rules that are appropriate. Continuing this process until some rule produces a goal state. This process, called breadth-first search, can be described precisely in the breadth first search algorithm. 2.5 Depth First Search The searching process in AI can be broadly classified into two major types. Viz. Brute Force Search and Heuristics Search. Brute Force Search do not have any domain specific knowledge. All they need is initial state, the final 15state and a set of legal operators. Depth-First Search is one the important technique of Brute Force Search. In Depth-First Search, search begins by expanding the initial node, i.e., by using an operator, generate all successors of the initial node and test them. Let us discuss the working of DFS with the help of the algorithm given below. Algorithm for Depth-First Search 1. Put the initial node on the list of START. 2. If (START is empty) or (START = GOAL) terminate search. 3. Remove the first node from the list of START. Call this node d. 4. If (d = GOAL) terminate search with success. 5. Else if node d has successors, generate all of them and add them at the beginning of START. 6. Go to step 2. In DFS the time complexity and space complexity are two important factors that must be considered. As the algorithm and Fig. 2.3 shows, a goal would be reached early if it is on the left hand side of the tree. Root C A B J F D I E H Goal Fig: 2.3 Search tree for Depth-first search 16 The major drawback of Depth-First Search is the determination of the depth (cut-off depth) until which the search has to proceed. The value of cut-off depth is essential because otherwise the search will go on and on. 2.5 Breadth First Search Breadth first search is also like depth first search. Here searching progresses level by level. Unlike depth first search, which goes deep into the tree. An operator employed to generate all possible children of a node. Breadth first search being the brute force search generates all the nodes for identifying the goal. Algorithm for Breadth-First Search 1. Put the initial node on the list of START. 2. If (START is empty) or (START = GOAL) terminate search. 3. Remove the first node from the list of START. Call this node d. 4. If (d = GOAL) terminate search with success. 5. Else if node d has successors, generate all of them and add them at the tail of START. 6. Go to step 2. Fig. 2.4 gives the search tree generated by a breadth-first search. 17Root C A B J F D I H E Goal Fig: 2.4 Search tree for Breadth-first search Similar to brute force search two important factors time-complexity and space- complexity have to be considered here also. The major problems of this search procedure are: - 1. Amount of time needed to generate all the nodes is considerable because of the time complexity. 2. Memory constraint is also a major hurdle because of space complexity. 3. The Searching process remembers all unwanted nodes, which is of no practical use for the search. 2.6 Heuristic Search Techniques The idea of a "heuristic" is a technique, which sometimes will work, but not always. It is sort of like a rule of thumb. Most of what we do in our daily lives involves heuristic solutions to problems. Heuristics are the approximations used to minimize the searching process. The basic idea of heuristic search is that, rather than trying all possible search paths, you try and focus on paths that seem to be getting you nearer your goal 18state. Of course, you generally can't be sure that you are really near your goal state - it could be that you'll have to take some amazingly complicated and circuitous sequence of steps to get there. But we might be able to have a good guess. Heuristics are used to help us make that guess. To use heuristic search you need an evaluation function (Heuristic function) that scores a node in the search tree according to how close to the target/goal state it seems to be. This will just be a guess, but it should still be useful. For example, for finding a route between two towns a possible evaluation function might be a ``as the crow flies'' distance between the town being considered and the target town. It may turn out that this does not accurately reflect the actual (by road) distance - maybe there aren't any good roads from this town to your target town. However, it provides a quick way of guessing that helps in the search. Basically heuristic function guides the search process in the most profitable direction by suggesting which path to follow first when more than one is available. The more accurately the heuristic function estimates the true merits of each node in the search tree (or graph), the more direct the solution process. In the extreme, the heuristic function would be so good that essentially no search would be required. The system would move directly to a solution. But for many problems, the cost of computing the value of such a function would outweigh the effort saved in the search process. After all, it would be possible to compute a perfect heuristic function by doing a complete search from the node in question and determining whether it leads to a good solution. Usually there is a trade-off between the cost of evaluating a heuristic function and the savings in search time that the function provides. There the following algorithms make use of heuristic evaluation function. 9 Hill Climbing 9 Best First Search 9 Constraints Satisfaction 2.7 Hill Climbing Hill climbing uses a simple heuristic function viz., the amount of distance the node is from the goal. This algorithm is also called Discrete Optimization Algorithm. Let us discuss the steps involved in the process of Hill Climbing with the help of an algorithm. Algorithm for Hill Climbing Search 1. Put the initial node on the list of START. 2. If (START is empty) or (STRAT = GOAL) terminate search. 3. Remove the first node from the list of START. Call this node d. 194. If (d = GOAL) terminate search with success. 5. Else if node d has successors, generate all of them. Find out how far they are from the goal node. Sort them by the remaining distance from the goal and add them to the beginning of START. 6. Go to step 2. The algorithm for hill-climbing Fig. 2.5 Root 7 3 C 8 A B 2.7 2.7 2 E D F Goal Fig. 2.5 Search tree for hill-climbing procedure 20

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.