4. Uninformed Search Flashcards
What is the goal of problem-solving in AI?
To find the best solution among possible options.
What are the basic requirements for solving a problem automatically?
A representation of the problem and algorithms with a strategy to solve it.
What is a search space?
The set of all feasible solutions among which the desired solution resides.
What is a state space graph?
A mathematical representation of states in a search strategy, where nodes represent state configurations and edges represent actions.
What is a search tree?
An instantiation of the state space graph representing possible outcomes.
What are the five components of a search problem?
- Initial state, 2. Actions, 3. Successor function, 4. Goal test, 5. Path cost function.
What are the key concepts of a search approach?
Frontier (partial plans under consideration), Expansion (expanding plans), and Exploration strategy (minimizing nodes explored).
What properties are used to evaluate search algorithms?
Completeness, Optimality, Time Complexity, and Space Complexity.
What is the general tree search algorithm?
A strategy where a frontier is initialized with the initial state, nodes are expanded, and solutions are found through iteration.
What is Depth-First Search (DFS)?
A search strategy that expands the deepest node first using a Last-In-First-Out (LIFO) stack.
Is DFS complete and optimal?
DFS is complete only if the search depth is finite, but it is not optimal as it finds the left-most solution regardless of cost.
What is Breadth-First Search (BFS)?
A search strategy that expands the shallowest node first using a First-In-First-Out (FIFO) queue.
Is BFS complete and optimal?
BFS is complete if the branching factor is finite and optimal if all costs are equal.
What are the time and space complexities of BFS?
Both are O(b^m), where b is the branching factor and m is the depth.
What is Uniform-Cost Search (UCS)?
A search algorithm that expands the node with the cheapest cost first, using a priority queue.
What data structure does UCS use?
A priority queue, where nodes with the lowest path cost are expanded first.
Is UCS complete and optimal?
Yes, if the smallest cost is positive (ε > 0).
How does UCS differ from Dijkstra’s algorithm?
UCS finds the single best path to the goal, while Dijkstra’s algorithm finds the shortest paths to all nodes.
