To Study Flashcards
What is a state-search problem
It systematically explores all possible states from an initial state to find a goal state without prior knowledge of the path.
What is the difference between completeness vs optimality conditions of a search strategy ?
Completeness of a search strategy ensures that it will find a solution if one exists, while optimality ensures that it will find the least-cost solution among all possible solutions.
How does the look ahead tree search work?
an agent starts from an initial state, considers possible actions, uses a transition model to determine resulting states, and applies a goal test to identify the target state.
What’s the difference between a tree and a graph search?
In a tree search, the structure is a hierarchical tree with a single path from the root to any node, while in a graph search, the structure can have cycles and multiple paths between nodes, requiring handling of previously visited nodes to avoid infinite loops.
Consider the search-tree below.
n1
n2 n3
n4 n5 n6 n7
What order would the nodes be encountered if the graph was searched
(a) depth first left-to-right?
(b) breadth-first right-to-left?
Depth-First Search (left-to-right): n1, n2, n4, n5, n3, n6, n7
Breadth-First Search (right-to-left): n1, n3, n2, n7, n6, n5, n4
Summarise the advantages of depth-first
Memory Efficient: Uses less memory (O(bm)).
Path Finding: Quickly finds deep solutions in narrow trees.
Simple Implementation: Easily implemented with recursion.
How does iterative deepening search obtain the advantages of both methods
while avoiding their disadvantages?
Memory Efficient: Uses low memory like DFS.
Complete and Optimal: Like BFS, ensures finding shortest path.
Avoids DFS Disadvantages:
Doesn’t get stuck in deep branches by incrementally increasing depth limits.
Avoids BFS Disadvantages:
Avoids high memory usage by using depth-first search at each iteration.
Summarise the advantages of breadth-first search.
Complete: Guarantees finding a solution if one exists.
Optimal: Finds the shortest path in unweighted graphs.
Systematic: Explores all nodes level by level.
