03 Uninformed Search Algorithms Flashcards
How do you define a search problem?
…
Initial State: where the agent starts i
…
Transition Model Result(s, a): returns result of action a in state s
Goal Test Is-Goal(s): …
…
State Space: set of possible states
Actions(s): possible actions that are applicable in a state s
checks whether s is a goal state
Action Cost (s, a, s’): cost of applying action a in state s to reach s’
(Examplifying the concepts on slides)
Tree-Like Search Algorithm
function Tree-Like-Search (problem) returns a solution or failure initialize the frontier using the initial state of problem
loop do
if the frontier is empty then return failure
choose a leaf node and remove it from the frontier
if the node contains a goal state then return the corresponding solution expand the chosen node, adding the resulting nodes to the frontier
Is it possible that graph search is slower than tree-like search?
…
What is the maximum number of steps required in graph search (according to slide 21)?
…
You have to assemble parts, and each part exists only once. What search technique would you use?
…
Yes, in graph search, each node is tracked to avoid revisiting nodes, which adds computational overhead to keep track of visited nodes==> graph search generally slower, but often more efficient in terms of memory usage and prevents redundant exploration of the same paths.
The number of edges of the graph.
In graph search, the worst-case scenario involves traversing all edges in the graph before reaching the goal. This is because graph search must explore every possible path without revisiting nodes unnecessarily, which could require examining each edge once.
Since each part exists only once, revisiting nodes would be redundant. Graph search is suitable here because it avoids re-exploring already-visited nodes, ensuring that each part is only considered once in the assembly sequence.
Generating a search tree
We are searching for an action sequence to a goal state. The possible actions from the initial state form the search tree:
Root: Initial state.
Branches: Actions.
Nodes: Reached states.
Leaves: Unexpanded nodes. We call the set of leaves the frontier.
Avoiding cycles in the search tree
Problem: In the previous example, we went back to Arad from Sibiu: Expanding from Arad only contains repetitions of previous possibilities.
Only expand nodes that have not been visited before. Reached states are stored in a reached set.
Idea is referred to as graph search
Graph Search vs Search tree
see slides
Measuring Problem-Solving Performance
Search Algorithms
We can evaluate the performance of a search algorithm using the following criteria:
Completeness: Is it guaranteed that the algorithm finds a solution if one exists?
Optimality: Does the strategy find the optimal solution (minimum costs)?
Time complexity: How long does it take to find a solution?
Space complexity: How much memory is needed to perform the search?
Structure of a node n
n.STATE: …
n.PARENT: The node in the search tree that generated this node;
n.ACTION: …
n.PATH-COST: The cost, traditionally denoted by g(n), of the path from the initial state to the node.
The state in the state space to which the node corresponds;
The action that was applied to the parent to generate the node;
Operations on a queue (required for the frontier)
Empty(queue): Returns true if ….
Pop(queue): Removes the …
Add(node, queue): Inserts a node and …
queue is empty;
first element of the queue and returns it;
returns the resulting queue.
Uninformed Search vs. Informed Search
Uninformed search
No additional information besides the problem statement (states, initial state, actions, transition model, goal test, action cost) is provided.
Uninformed search can only produce next states and check whether it is a goal state.
Informed search
Strategies know whether a state is more promising than another to reach a goal.
Informed search uses measures to indicate the distance to a goal.
