Module Question 2
- Explain the primary difference between an uninformed and an informed search algorithm.
- In what scenario would Depth-First Search be more efficient than Breadth-First Search?
- What is a heuristic function, and what role does it play in the A* algorithm?
- Describe a real-world problem (e.g., GPS navigation) that can be solved using a search algorithm.
Status: 100% sudah tercapai
Keterangan: saya sudah mengerjakan dengan baik dan benar
bukti:
Answers:
1.The main difference is the information they use to find a solution.
-Uninformed search does not have additional knowledge about which path is likely to be better. It searches using only the information provided by the problem itself. Examples include Breadth-First Search (BFS) and Depth-First Search (DFS).
-Informed search uses additional knowledge, usually called a heuristic, to guide the search toward a promising solution. An example is the A* algorithm.
In simple terms, uninformed search explores without knowing which direction is best, while informed search uses an estimate to make better decisions.
2.Depth-First Search (DFS) can be more efficient when the solution is likely to be deep in the search tree and there are many possible paths at each level.
For example, if you are searching through a large maze and the correct path is far from the starting point, DFS can follow one path deeply without having to explore every nearby path first. DFS also generally requires less memory than BFS because it mainly stores the current path and unexplored alternatives.
However, DFS does not necessarily find the shortest solution. BFS is preferable when the shortest path is important and all steps have the same cost.
3.A heuristic function, usually written as h(n), estimates the cost of reaching the goal from the current state or node.
In the A* algorithm, the heuristic helps determine which node should be explored next. A* commonly uses:
f(n) = g(n) + h(n)
-g(n) = the actual cost from the starting point to the current node.
-h(n) = the estimated cost from the current node to the goal.
-f(n) = the estimated total cost of the solution through that node.
The heuristic makes A* more efficient by directing the search toward nodes that appear more promising instead of exploring possibilities randomly.
4.PS navigation is a common example. When a user wants to travel from one location to another, the navigation system represents locations as nodes and roads as connections or edges. A search algorithm can explore different routes to find an appropriate path.
For example, A* can use the distance between the current location and the destination as a heuristic. It can combine this estimate with the distance already traveled to identify an efficient route. This allows navigation systems to find routes while considering factors such as distance, travel time, or road conditions.