40 Questions
What is the major drawback of Greedy search in terms of optimality?
It may get stuck in local optima.
What is the primary advantage of Greedy search in terms of time complexity?
It is often computationally fast, especially for small search spaces.
What is the key strategy used in Greedy search to guide the search?
Heuristic function evaluation.
What is the major limitation of Greedy search in terms of completeness?
It is not guaranteed to find a solution.
What type of search strategy is Greedy search classified as?
Informed search strategy.
What is the primary advantage of Iterative Deepening Search compared to Depth-First Search?
Retains the memory efficiency of DFS while guaranteeing the completeness of BFS
What is the main disadvantage of Iterative Deepening Search in very large search spaces?
Redundant exploration of nodes at lower levels, increasing time complexity
What is the primary reason why Depth-Limited Search is preferred over Depth-First Search in cyclic search spaces?
DLS prevents getting stuck in infinite loops
What is a common limitation of Depth-Limited Search?
It may miss the solution if the depth limit is too shallow
Which of the following search strategies is not guaranteed to find the shortest path in all cases?
Depth-First Search
What is the primary concern of Uniform Cost Search in terms of path cost?
Finding the path with the lowest total cost
What is a key characteristic of uninformed search strategies?
They use only the information available in the problem definition
What dimension of evaluation measures the maximum number of nodes in memory?
Space complexity
What is the time complexity of Uniform Cost Search?
High due to the possibility of expanding many nodes with low costs
Which of the following is a characteristic of a complete search strategy?
It always finds a solution if one exists
Which search strategy is optimal in terms of the total cost?
Uniform Cost Search (UCS)
What is the primary advantage of using Breadth-First Search (BFS) over other search strategies?
It guarantees the shortest path to the goal in terms of number of edges
What is the primary difference between Uniform Cost Search and Depth-First Search?
UCS uses a priority queue, while DFS uses a LIFO stack
What is an advantage of Depth-First Search over Breadth-First Search?
It requires less memory compared to BFS
What is the primary disadvantage of using Breadth-First Search (BFS) in large search spaces?
It requires significant memory space to store the frontier nodes
What is the primary goal of a heuristic function in informed search algorithms?
To produce a solution in a reasonable time frame that is good enough
Which of the following is a characteristic of a heuristic function in informed search algorithms?
It approximates the exact solution
What is the relationship between the optimal solution cost of a relaxed problem and the optimal solution cost of the real problem?
The relaxed problem cost is no greater than the real problem cost
Why are heuristics useful in search algorithms?
Because they produce a good enough solution in a reasonable time frame
What is the purpose of using heuristics in conjunction with optimization algorithms?
To improve the time complexity of the search
What characteristic of A* search guarantees that it finds the optimal solution if one exists?
It is both complete and optimal
What is the primary advantage of using A* search over Greedy search in terms of optimality?
A* search is guaranteed to find the optimal solution, while Greedy search is not
Which of the following statements is true about A* search?
It is a combination of the cost-so-far and the estimated cost-to-go
What is the role of the heuristic function in A* search?
It guides the search by biasing it towards nodes that appear to be more promising
What is the main difference between A* search and Greedy search in terms of decision-making?
A* search considers the entire search space, while Greedy search considers only local information
What is the primary reason why A* search is considered optimal?
The heuristic function never overestimates the true cost
What is the consequence of using an inconsistent heuristic function in A* search?
The search becomes non-optimal
How does the heuristic function influence the search process in A* search?
It guides the search towards states that appear more promising
What is a necessary condition for A* search to be complete?
The search space is finite
How does the complexity of the heuristic function affect the memory and computation resources required by A* search?
It increases the required resources
What is the primary advantage of A* search in terms of optimality?
It always finds the optimal solution with the minimum total cost
What is the role of the heuristic function in A* search?
It estimates the cost or utility of reaching a goal state from a given state
What is the consequence of using an inadmissible heuristic function in A* search?
The search becomes non-optimal
How does the efficiency of A* search compare to greedy search?
A* search combines the efficiency of greedy search with the optimality of uniform-cost search
What is the primary advantage of A* search in terms of time complexity?
It combines the efficiency of greedy search with the optimality of uniform-cost search
Study Notes
Strategies and Dimensions
- Strategies are evaluated along the dimensions of completeness, time complexity, space complexity, and optimality
- Time and space complexity are measured in terms of b (maximum branching factor of the search tree), d (depth of the least-cost solution), and m (maximum depth of the state space)
Uninformed Strategies
Breadth-First Search (BFS)
- Explores all neighbor nodes at the present depth level before moving to the nodes at the next level
- Uses a FIFO (First-In-First-Out) queue to store the frontier nodes
- Guarantees the shortest path to the goal in terms of the number of edges
- Requires significant memory space to store the frontier nodes, especially for large search spaces
Uniform-Cost Search (UCS)
- Expands the node with the lowest path cost (i.e., cumulative cost from the initial state) rather than just the shallowest node
- Uses a priority queue ordered by the cumulative path cost to store the frontier nodes
- Finds the optimal solution in terms of the least total cost
- May expand many nodes with low costs before finding the optimal solution, leading to high time complexity
Depth-First Search (DFS)
- Explores as far as possible along each branch before backtracking
- Uses a LIFO (Last-In-First-Out) stack to store the frontier nodes
- Requires less memory compared to BFS as it only needs to store nodes along the current path
- Not guaranteed to find the shortest path, can get stuck in infinite loops if the search space contains cycles
Depth-Limited Search (DLS)
- Begins at the base node and recursively examines every node at its current level before heading to the next level
- Terminates the search when it reaches a specified depth limit, preventing infinite loops
- Prevents DFS from getting stuck in infinite loops in cyclic search spaces
- May miss the solution if the depth limit is too shallow
Iterative Deepening Search (IDS)
- Combines DFS and DLS
- Repeatedly performs DFS with increasing depth limits until the goal state is found
- Retains the memory efficiency of DFS while guaranteeing the completeness of BFS
- Redundant exploration of nodes at lower levels can increase time complexity, especially in large search spaces
Best-First Search
- Looks for the fastest/slowest growth/descent towards the goal node before the expansion
- Selects the node that appears to be the most promising at each step
- Prioritizes nodes that are closest to the goal state according to a heuristic function
- Does not guarantee optimality or completeness
- May get stuck in local optima or fail to find the optimal solution if the heuristic function is not admissible or leads the search down the wrong path
A* Search
- Combines the efficiency of greedy search with the optimality of uniform-cost search
- Uses a heuristic function that estimates the cost or distance from a given state to the goal state
- Selects the node with the lowest combination of the cost-so-far (g-value) and the estimated cost-to-go (h-value) at each step
- Prioritizes nodes that have a lower total estimated cost (f-value = g-value + h-value), aiming to minimize the total cost to reach the goal state
- Is complete and optimal, guaranteeing to find the optimal solution with the minimum total cost if the heuristic function is admissible and consistent
Learn about the Greedy search algorithm, a heuristic-based search method that prioritizes nodes closest to the goal state without considering the entire path or cost incurred. Understand its strategy and application in AI and computer science.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
