Heuristic Search techniques Heuristics вЂў To solve larger problems, domain-specific knowledge must be provided to improve the search efficiency вЂў Heuristic вЂ“ Any advice that is often effective but is not always guaranteed to work вЂў Heuristic Evaluation Function вЂ“ Estimates cost of an optimal path between two states вЂ“ Must be inexpensive to calculate вЂ“ h(n) Heuristic Search techniques вЂў There are a number of methods used in Heuristic Search techniques вЂ“ Depth Search вЂ“ Breadth Search вЂ“ Hill climbing вЂ“ Generate-and-test вЂ“ Best-first-search вЂ“ Problem reduction вЂ“ Constraint satisfaction вЂ“ Means-ends analysis Searching and AI вЂў Searching falls under Artificial Intelligence (AI). вЂў A major goal of AI is to give computers the ability to think, or in other words, mimic human behavior. вЂў The problem is, unfortunately, computers don't function in the same way our minds do. вЂў They require a series of well-reasoned out steps before finding a solution. Searching and AI вЂў Your goal, then, is to take a complicated task and convert it into simpler steps that your computer can handle. вЂў That conversion from something complex to something simple which computer can easily solve. Searching and AI вЂў Let's first learn how we humans would solve a search problem. вЂ“ First, we need a representation of how our search problem will exist. вЂ“ We normally use search tree for representation of how search problem will exist. вЂў It is a series of interconnected nodes that we will be searching through вЂў Let us see diagram below Searching and AI вЂў In our above graph, the path connections are not two-way. All paths go only from top to bottom. In other words, A has a path to B and C, but B and C do not have a path to A. Searching and AI вЂў Each lettered circle in our graph is a node. вЂў A node can be connected to other via our edge/path, and those nodes that its connects to are called neighbors. вЂў B and C are neighbors of A. E and D are neighbors of B, and B is not a neighbors of D or E because B cannot be reached using either D or E. вЂў Our search graph also contains depth: Searching and AI Searching and AI вЂў We now have a way of describing location in our graph. вЂў We know how the various nodes (the lettered circles) are related to each other (neighbors), and we have a way of characterizing the depth each belongs in. Depth First Search вЂў Depth first search works by taking a node, checking its neighbors, expanding the first node it finds among the neighbors, checking if that expanded node is our destination, and if not, continue exploring more nodes. вЂў Consider the following demonstration of finding a path between A and F: Depth First Search Depth First Search вЂў Step 0 Let's start with our root/goal node: вЂў We can use two lists to keep track of what we are doing - an Open list and a Closed List. An Open list keeps track of what you need to do, and the Closed List keeps track of what you have already done. Right now, we only have our starting point, node A. We haven't done anything to it yet, so let's add it to our Open list. Depth First Search вЂў Open List: A вЂў Closed List: <empty> вЂў Step 1 Now, let's explore the neighbors of our A node. To put another way, let's take the first item from our Open list and explore its neighbors: Depth First Search вЂў Node A's neighbors are the B and C nodes. Because we are now done with our A node, we can remove it from our Open list and add it to our Closed List. You aren't done with this step though. You now have two new nodes B and C that need exploring. Add those two nodes to our Open list Depth First Search вЂў Our current Open and Closed Lists contain the following data: вЂ“ Open List: B, C вЂ“ Closed List: A вЂў Step 2 Our Open list contains two items. For depth first search and breadth first search, you always explore the first item from our Open list. The first item in our Open list is the B node. B is not our destination, so let's explore its neighbors: Depth First Search вЂў Because we have now expanded B, we are going to remove it from the Open list and add it to the Closed List. Our new nodes are D and E, and we add these nodes to the beginning of our Open list: вЂ“ Open List: D, E, C вЂ“ Closed List: A, B Depth First Search вЂў Because D is at the beginning of our Open List, we expand it. D isn't our destination, and it does not contain any neighbors. All you do in this step is remove D from our Open List and add it to our Closed List: вЂ“ Open List: E, C вЂ“ Closed List: A, B, D Depth First Search вЂў Step 4 We now expand the E node from our Open list. E is not our destination, so we explore its neighbors and find out that it contains the neighbors F and G. Remember, F is our target, but we don't stop here though. Despite F being on our path, we only end when we are about to expand our target Node - F in this case Depth First Search вЂў Our Open list will have the E node removed and the F and G nodes added. The removed E node will be added to our Closed List: вЂ“ Open List: F, G, C вЂ“ Closed List: A, B, D, E Depth First Search вЂў Step 5 We now expand the F node. Since it is our intended destination, we stop: Depth First Search вЂў We remove F from our Open list and add it to our Closed List. Since we are at our destination, there is no need to expand F in order to find its neighbors. вЂў Our final Open and Closed Lists contain the following data: вЂ“ Open List: G, C вЂ“ Closed List: A, B, D, E, F Depth First Search вЂў The final path taken by our depth first search method is what the final value of our Closed List is: A, B, D, E, F. Breadth First Search вЂў Depth and breadth first search methods are both similar. In depth first search, newly explored nodes were added to the beginning of your Open list. In breadth first search, newly explored nodes are added to the end of your Open list. Breadth First Search вЂў Let's see how that change will affect our results. Consider the search tree below вЂў Find a path between nodes A and E. Breadth First Search вЂў Step 0 Let's start with our root/goal node: вЂў We will continue to employ the Open and Closed Lists to keep track of what needs to be done: вЂ“ Open List: A вЂ“ Closed List: <empty> Breadth First Search вЂў Step 1 Let's explore the neighbors of our A node. So far, we are following in depth first's foot steps: вЂў Remove A from Open list and add A to Closed List. A's neighbors, the B and C nodes, are added to our Open list. They are added to the end of our Open list, but since our Open list was empty (after removing A), it's hard to show that in this step. Breadth First Search вЂў Current Open and Closed Lists contain the following data: вЂ“ Open List: B, C вЂ“ Closed List: A вЂў Step 2 Things start to diverge from depth first search method in this step. We take a look the B node because it appears first in our Open List. Breadth First Search вЂў Because B isn't intended destination, we explore its neighbors: вЂў B is now moved to Closed List, but the neighbors of B, nodes D and E are added to the end of Open list: вЂ“ Open List: C, D, E вЂ“ Closed List: A, B Breadth First Search вЂў Step 3 We expand C node: вЂў Since C has no neighbors, all we do is remove C from our Closed List and move on: вЂ“ Open List: D, E вЂ“ Closed List: A, B, C Breadth First Search вЂў Step 4 Similar to Step 3, we expand node D. Since it isn't the destination, and it too does not have any neighbors, we simply remove D from Open list, add D to Closed List, and continue on: вЂ“ Open List: E вЂ“ Closed List: A, B, C, D Breadth First Search вЂў Step 5 Because our Open list only has one item, we have no choice but to take a look at node E. Since node E is the destination, we can stop here: Breadth First Search вЂў Our final versions of the Open and Closed Lists contain the following data: вЂ“ Open List: <empty> вЂ“ Closed List: A, B, C, D, E Generate and Test вЂў The generate-and-test strategy is the simplest of all the approaches. вЂў It consists of the following steps: вЂ“ Generate a possible solution. For some problems, this means generating a particular point in the problem space. For others, it mens generating a path from a start state. вЂ“ Test to see if this is actually a solution by comparing the chosen point or the end point of the chosen path to the set of acceptable goal state. Generate and Test вЂ“ If solution has been found quit. Otherwise return to step 1. вЂў This procedure could lead to an eventual solution within a short period of time if done systematically. вЂў However if the problem space is very large, the eventual solution may be a very long time. Generate and Test вЂў The generate-and-test algorithm is a depthfirst search procedure since complete solutions must be generated before they can be tested. вЂў It can also operate by generating solutions randomly, but then there is no guarantee that a solution will be ever found. вЂў It is known as the British Museum algorithm in reference to a method of finding object in the British Museum by wandering around. Generate and Test вЂў For a simple problems, exhaustive generateand-test is often a reasonable technique. вЂў For problems much harder than this, even heuristic generate-and-test, is not very effective technique. вЂў It is better to be combined with other techniques to restrict the space in which to search even further, the technique can be very effective Hill Climbing вЂў In hill climbing the basic idea is to always head towards a state which is better than the current one. вЂў So, if you are at town A and you can get to town B and town C (and your target is town D) then you should make a move IF town B or C appear nearer to town D than town A does. Hill Climbing вЂў The hill-climbing algorithm chooses as its next step the node that appears to place it closest to the goal (that is, farthest away from the current position). вЂў It derives its name from the analogy of a hiker being lost in the dark, halfway up a mountain. Assuming that the hikerвЂ™s camp is at the top of the mountain, even in the dark the hiker knows that each step that goes up is a step in the right direction. Hill Climbing вЂў The simplest way to implement hill climbing is as follows: вЂ“ Evaluate the initial state. If it is also a goal state, then return it and quit. Otherwise continue with the initial state as the current state. вЂ“ Loop until a solution is found or until there are no new operators left to be applied in the current state. вЂў Select an operator that has not yet been applied to the current state and apply it to produce new state. вЂў Evaluate the new state Steepest Hill Climbing вЂў Consider all the moves from the current state and select the best one as te next state. вЂў In steepest ascent hill climbing you will always make your next state the best successor of your current state, and will only make a move if that successor is better than your current state. Best-First Search вЂў Is the new method which combine the advantages of both depth-first and breadthfirst search into single method. вЂў At each step of the best-first-search process, we select the most promising of the nodes generated. вЂў This is done by applying appropriate heuristic function to each of them. Best-First Search вЂў Then expand the chosen node by using the rules to generate its successors. вЂў If one of them is a solution we can quit, if not, all those new nodes are added to the set of nodes generated so far. вЂў Again the most promising node is selected and the process continues. Best First Search вЂў Usually a bit of depth-first searching occurs as the most promising branch is explored. вЂў Example below shows the beginning of bestfirst search. Best First Search

1/--страниц