Heuristic Search
The Traveling Salesman Problem (TSP), where a salesman makes a complete tour of the cities on his route, visiting each city exactly once, while traveling the shortest possible distance, is an example of a problem which has a combinatorial explosion. As such, it cannot be solved using breadth-first or depth-first search for problems of any realistic size. Unfortunately, there are many problems which have this form and which are essentially intractable (they can’t be solved). In these cases, finding the best possible answer is not computationally feasible, and so we have to settle for a good answer. In this section we discuss several heuristic search methods which attempt to provide a practical means for approaching these kinds of search problems.
What is the Heuristic Search ?
Heuristic search methods are characterized by this sense that we have limited time and space in which to find an answer to complex problems and so we are willing to accept a good solution. As such, we apply heuristics or rules of thumb as we are searching the tree to try to determine the likelihood (احتمال) that following one path or another is more likely to lead to a solution. Note this is in stark contrast to brute-force methods which chug along merrily regardless of whether a solution is anywhere in sight.
Heuristic search methods use objective functions called heuristic functions to try to gauge the value of a particular node in the search tree and to estimate the value of following down any of the paths from the node.
Generate and Test Algorithm
It’s a very simple technique that allows us to algorithmize finding solutions:
• Define current state as an initial state
• Apply any possible operation on the current state and generate a possible solution
• Compare newly generated solution with the goal state
If the goal is achieved or no new states can be created, quit. Otherwise, return to the step 2
It works very well with simple problems. As it is an exhaustive search, it is not feasible to consider it while dealing with large problem spaces. It is also known as British Museum algorithm (trying to find an artifact in the British Museum by exploring it randomly).
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
|