Exploring Search Algorithms and Heuristics

Which of the following is a common application of Dijkstra's algorithm?

• Finding the shortest path in a graph with negative weights

• Network routing protocols

• Solving the knapsack problem

• Image processing

What is the primary purpose of a heuristic in search algorithms?

• To calculate the exact cost from the start node to the goal node

• To estimate the cost from the current node to the goal node

• To determine the shortest path from the start node to the goal node

• To increase the branching factor of the search

In the context of game development, why is pathfinding important?

• It helps in rendering graphics

• It determines the shortest path for characters to move

• It is used for sound effects

• It is used for network communication

Which of the following is a key difference between A* and Dijkstra's algorithm?

• A* uses a heuristic function, while Dijkstra's does not

• Dijkstra's algorithm is faster than A* in all cases

• A* can only be used on undirected graphs

• Dijkstra's algorithm requires a heuristic function

What is the main advantage of using a heuristic in search algorithms?

• It guarantees finding the optimal solution

• It reduces the search space and improves efficiency

• It increases the accuracy of the solution

• It simplifies the implementation of the algorithm

Which of the following is a common heuristic used in the A* algorithm for pathfinding on a grid?

• Manhattan distance

• Euclidean distance

• Hamming distance

• Chebyshev distance

How does Dijkstra's algorithm handle graphs with negative weight edges?

• It can handle them without any modifications

• It cannot handle them and will produce incorrect results

• It requires a modified version to handle negative weights

• It uses a heuristic to adjust for negative weights

Which of the following is true about the A* algorithm's completeness?

• A* is complete if the heuristic is admissible

• A* is complete only if the graph is acyclic

• A* is never complete

• A* is complete only if the heuristic is consistent

What is the time complexity of Dijkstra's algorithm when implemented with a priority queue?

Which of the following is a disadvantage of using a heuristic that is not admissible in the A* algorithm?

• It may lead to longer paths being found

• It may cause the algorithm to run slower

• It may cause the algorithm to miss the optimal solution

• It may increase the branching factor