Nama : Komalasari
Nim : 2681483783
Prodi : Bisnis Digital
Question :
- 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
Answer :
1.The primary difference lies in the use of additional information (heuristics). Uninformed search algorithms (such as BFS and DFS) rely solely on the problem definition—initial state, actions, and goal—without any knowledge of how close a node is to the goal. Informed search algorithms (such as A*) use a heuristic function
h(n)
h(n) that estimates the cost from the current node to the goal, making the search more directed and efficient.
2.DFS is more efficient when memory is limited and the solution lies deep in the search tree. For example, exploring a large maze or a decision tree in chess. BFS must store an entire layer of nodes in memory (
O(bd)
O(b
d
)), while DFS only stores the current path (
O(bm)
O(bm)). If the solution is found deep in a branch, DFS can be far more memory- and time-efficient.
3.A heuristic function
h(n)
h(n) is an estimate of the cost from node
n
n to the goal. In A, the heuristic acts as a “compass” guiding the search. The A formula is:
f(n)=g(n)+h(n)
f(n)=g(n)+h(n)
where
g(n)
g(n) is the actual cost from the start to
n
n, and
h(n)
h(n) is the estimated cost to the goal. If the heuristic is admissible (never overestimates the true cost), A* is guaranteed to find the optimal solution. A good heuristic makes A* much faster than BFS because it prioritizes promising paths.
4.PS navigation is a classic example of a search algorithm application. The road map is modeled as a graph, where intersections are nodes and roads are weighted edges (distance or travel time). The agent’s goal is to find the fastest route from the current location to the destination.
- Initial state: The user’s current location.
- Actions: Move to a connected intersection.
- Goal test: Whether the destination address has been reached.
- Cost function: Travel time or distance.
- Heuristic: Straight-line distance to the destination (admissible because it can never be shorter than the actual road).
A* is used because it combines the actual cost already traveled (g) with the estimated remaining distance (h), producing an optimal route without having to explore the entire map like BFS.
status : terselesaikan 100%