IT445 – Discussion 2
To help you understand the major differences between blind searching (uniformed search) and heuristic searching (informed search).
Topic of Discussion
Total Marks: 1.5
Content :Informed Search Vs Uninformed Search
|Basis for comparison||Informed Search||Uninformed Search|
|Basic||Uses knowledge to find the steps to the solution.||No use of knowledge|
|Efficiency||Highly efficient as consumes less time and cost.||Efficiency is mediatory|
|Performance||Finds solution more quickly||Speed is slower than informed search|
|Algorithms||Heuristic depth first and breadth-first search, and A* search||Depth-first search, breadth-first search and lowest cost first search|
Definition of Informed search
The informed search technique utilizes the problem specific knowledge in order to give a clue to the solution of the problem. This type of search strategy actually prevents the algorithms from stumbling about the goal and the direction to the solution. Informed search can be advantageous in terms of the cost where the optimality is achieved at lower search costs.
To search an optimal path cost in a graph by implementing informed search strategy the most promising nodes n are inserted to the heuristic function h(n). Then the function returns a non-negative real number which is an approximate path cost calculated from node n to the target node.
Here the most important part of the informed technique is the heuristic function which facilitates in imparting the additional knowledge of the problem to the algorithm. As a result, it helps in finding the way to the goal through the various neighboring nodes. There are various algorithms based on the informed search such as heuristic depth-first search, heuristic breadth-first search, A*search, etcetera. Let’s now understand heuristic depth-first search.
Heuristic Depth First Search
Similar to depth-first search method given below heuristic depth first search chooses a path but traverse all paths from the selected path prior to choosing another path. However, it chooses the best path locally. In cases where the smallest heuristic value is the priority for the frontier, then it is known as best first search.
Another informed search algorithm is A* search which merges the concept of lowest cost first and best first searches. This method considers both path cost and heuristic information in the process of searching and selecting the path to be expanded. An estimated total path cost used for each path residing on the frontier from the start to the target node. Therefore it uses two functions at the same time – cost (p) is the cost of the discovered path and h (p) is the estimated value of the path cost from the starting node to the goal node.
Definition of Uninformed search
The uninformed search is different from informed search in the way that it just provides the problem definition but no further step to finding the solution to the problem. The primary objective of uninformed search is to differentiate between the target and non-target state, and it totally ignores the destination it is heading towards in the path until it discovers the goal and reports successor. This strategy is also known as a blind search.
There are various search algorithms under this category such as depth-first search, uniform cost search, breadth-first search, and so on. Let us now understand the concept behind the uninformed search with the help of depth-first search.
Depth First Search
In depth first search, a Last in first out stack is used to add and remove the nodes. Only one node is added or removed at a time and the first element removed from the frontier of the stack would be the last element added to the stack. By employing stack in the frontier results in the searching of paths proceeded in depth first manner. When a shortest and optimal path being searched using depth-first search, the path created by the adjacent nodes is completed first even if it is not the desired one. Then the alternative path is searched through backtracking.
In other words, the algorithm chooses the first alternative at each node then backtracks to another alternative until it has traversed all paths from first selection. This also raises a problem where the search may cease to stop because of infinite loops (cycles) present in the graph.
Key Differences between Informed and Uninformed Search
The informed search provides the direction regarding the solution while in uninformed search no suggestion is given regarding the solution. This makes uninformed search lengthier when the algorithm is implemented.
Response Commenting on the Post
This paper has presented the detailed comparison between the informed search and the uninformed search. This post has provided a comparison chart that is easy or the users to understand the main components of the post. These charts have provided the executive summary of this paper.
This post has well described definitions of the informed search, the Heuristic Depth first search, uninformed search and the depth first search. This post has also provided a conclusion regarding the discussed details. The informed search provides the direction concerning the solution and on the other hand the uninformed search provides no suggestions are provided on the solutions.
However, I recognize that this paper should mention or discuss the limitations of both depth first search and unformed search methods. This paper should also provide the key similarities between the informed and the uninformed search to allow the reader of the post to understand how these two search methods differ and the similarities.
Such a cheap price for your free time and healthy sleep
All online transactions are done using all major Credit Cards or Electronic Check through PayPal. These are safe, secure, and efficient online payment methods.