Day 5 Flashcards
Problem-solving agents are the goal-based agents and use atomic representation
True
False
True
Properties of Search Algorithms:
o Completeness
o Optimality
o Time Complexity
o Space Complexity
Completeness: A search algorithm is said to be complete if it guarantees to return a
solution if at least any solution exists for any random input.
True
False
True
Optimality: If a solution found for an algorithm is guaranteed to be the best solution
(lowest path cost) among all other solutions, then such a solution for is said to be an
optimal solution.
True
Time Complexity: Time complexity is a measure of time for an algorithm to complete its task.
True
Space Complexity: It is the maximum storage space required at any point during the
search, as the complexity of the problem.
A search problem can have three main factors:
➢ Search Space: Search space represents a set of possible solutions, which a system may have.
➢ Start State: It is a state from where agent begins the search.
➢ Goal test: It is a function which observe the current state and returns whether the goal state is achieved or not.
—————- represents a set of possible solutions, which a system may have.
Search space
———– It is a state from where agent begins the search.
Start State
——— It is a function which observe the current state and returns whether the goal state is achieved or not.
➢ Goal test
➢Start State
➢ Search Space
➢ Goal test
Search tree: A tree representation of search problem is called Search tree. The root of the search tree is the root node which is corresponding to the initial state.
True
False
True
Actions: It gives the description of all the available actions to the agent.
Actions: It gives the description of all the available actions to the agent.
Transition model: A description of what each action do, can be represented as a transition model.
—————- It is a function which assigns a numeric cost to each path.
Path Cost:
———– It is an action sequence which leads from the start node to the goal node.
Solution
————— If a solution has the lowest cost among all solutions.
Optimal Solution
search algorithms terminologies: 1-Search Space 2-Start state 3-Goal solution 4-Search tree 5-Actions 6-Transition Model 7-Path coast 8-Solution 9-Optimal Solution
Based on the search problems we can classify the search algorithms into uninformed (Blind search) search and informed search (Heuristic search) algorithms.
True
—————– search does not contain any domain knowledge such as closeness, the
location of the goal. It operates in a brute-force way as it only includes information about
how to traverse the tree and how to identify leaf and goal nodes. so, it is also called blind
search. It examines each node of the tree until it achieves the goal node
The uninformed
————– search algorithms use domain knowledge. In an ————- search, problem information is available which can guide the search. ———— search strategies can find a solution more efficiently than an uninformed search strategy. ——— search is also called a Heuristic search.
Informed
A heuristic is a way which might always be guaranteed for best solutions but guaranteed to find a good solution in reasonable time.
True
False
False
A heuristic is a way which might not always be guaranteed for best solutions but guaranteed to find a good solution in reasonable time.
uninformed search:
1-Breadth first search 2-Depth first search 3-Uniformed coast search 4-Depth limited search 5-Iterative deeping depth first search 6-Bidirectional Search
Informed Search
Best First Search
A* Search
Breadth-first search is the most common search strategy for traversing a tree or graph.
This algorithm searches breadthwise in a tree or graph, so it is called breadth-first search
