Search Trees And Blind Searches Flashcards
(25 cards)
What is the travelling salesman problem
A salesperson must visit n cities
Start at any city but must finish at the same city, must visit each city only once
Solving TSP - to find the minimum distance/cost solution
Combinatorial Explosion Problem - travelling salesman
10 city TSP has 181,000 possible solutions
20 city TSP has 10,000,000 billion possible solutions
Combinational Explosion Problem is one of the major unsolved theoretical problems in computer science
Combinatorial Explosion definition
The feature where the number of solutions for a problem grows exponentially with problem size
Problem search space
The concept of search is important in science and engineering
A lot of problems can be seen as a search for the right answer
The concept of search space, the set of all possible solutions to a problem
What do search algorithms do
Input - a problem
Return - a solution to the problem
Defining a problem using a search tree
States - nodes
Search Space - all nodes in the tree
Operator - branches
What are states/nodes when defining a problem
The possible states of the problem
What is the search space when defining a problem
All the nodes in the tree
The set of states reachable from the initial state
What are the operator/branches when defining a problem
A set of actions that move one state to another
Search tree - neighbourhood
All possible states reachable from a given state
Search tree - goal test
A test state to tell of the search reached a state that solves the problem
Search trees - path cost
How much it costs to take a particular path
What are the issues with search trees
Tree size
Branching factor - average number of branches of all nodes in a tree
What is the depth of a node
How many steps away it is from the starting node
what is the depth of a tree
How many steps from starting node to furthest finishing node
What does the general search algorithm return
Solution or failure
General search algorithm (general template - p and queuing)
P - problem/input
QUEUING-FN - different queuing functions define different types of search techniques
General search algorithm (loop)
First we take the initial state of problem p and create a data structure called node
Then make a data structure called queue and add the node to the queue
Once in the loop, explore the tree
Check that nodes actually have stuff in, if empty we have exhausted all nodes in the tree and not found a solution
Take the first node in nodes (queue called nodes) r
Test to see if this is the goal, if its solved then we return that node and its path as a solution
If not then we add the next node to the queue and remove the first node and then restart the loop
Breadth first search (BFS) - method
Expands root node first
Expands all the node at level 1 before expanding level 2
What are fringe nodes (open nodes)
Nodes in the queue
Have been discovered but not processed
Not yet tested if they are the goal
What are visited nodes (closed nodes)
Have been processed
Tested if they match the goal
What are undiscovered nodes
Nodes that have not yet been discovered
Search techniques evaluation 4 criteria
Completeness - guaranteed to find a solution if one exists
Time complexity - how long does it take to find a solution
Space complexity - how much memory is required to perform the search
Optimality - does it find the optimal solution (one or all)
Depth first search - method
Expand root node first
Explore one branch before exploring another branch
Queuing function - adds nodes at the front of the queue
