Search AI

Question 1

What are AI search Algorithms useful for?

Answer 1

Search Algorithms help machines to navigate through complex search spaces to find optimal solutions to a wide range of problems.

1. Problem-solving
   
   • Route planning
2. Efficiency
3. Automation
4. Decision-making
5. Innovation

Question 2

Vad är en “Fringe”?

Answer 2

En lista av noder som väntas på att bli checked

• inom tree search

Question 3

Vad är att “expandera en nod”?

Answer 3

Att generera alla dess barn

Question 4

Vad krävs för att kunna bygga ett system för att lösa ett specifikt problem?

Answer 4

1. Define the problem
   
   • Needs precise specifications of INITAL SOLUTION & FINAL SOLUTION
2. Analyze the problem
   
   • Select important features
3. Isolate and represent
   
   • convert the features into knowledge representation
4. Problem solving techniques
   
   • Choose technique and apply

Question 5

What is a search space? and a search tree?

Answer 5

The search space is all the possible conditions and solutions. A search tree is a tree representaiton of search space, showing possible solutions from initial state

Question 6

What is the basic idea of tree search algorithms?

Answer 6

A simulated exploration of state space by generating successors of already explored states

Question 7

What is a Search Strategy?

Answer 7

A strategy to contain the search, it is defined by picking the order of node expansion.

Strategies are evaluated along the following dimensions

Completeness
Time complexity
Space complexity
Optimality

Question 8

What are uninformed search strategies?

Answer 8

They use only the information available in the problem definition

1. Breadth-first search
2. Uniform-cost search
3. Depth-first

Question 9

How does Breadth-Frist Search work?

Answer 9

Expand the shallowest unexpanded node

The fringe is a FIFO queue, new successors go at the end

Question 10

What are the properties of Breadth-First Search?

Answer 10

Complete? Yes if the tree is finite
Space? Keeps every node in memory

Optimal? Yes if the cost =1 per step

Question 11

How does a Depth-First Search Work?

Answer 11

Expand the deepest unexpanded node

The Fringe is a LIFO queue, the successors are put at front

Question 12

What are the properties of depth-first search

Answer 12

Complete? No: Fails in infinite-depth spaces, or spacies with loops

Optimal? No, or at least not guaranteed

Question 13

When is Breadth-First or Depth-First best suited?

Answer 13

BFS is best suited for finding the shortest path or all possible solutions.

DSF is better for problems where any solution is acceptable or where the solution is likely to be found closer to the starting point.

Question 14

How does Uniform-Cost Search Work?

Answer 14

Chooses the option with the lowest Cost.

• Priority Queue

Question 15

What is informed search?

Answer 15

Informed search uses additional information such as heuristic functions.

Question 16

What are Heuristic Functions?

Answer 16

Heuristic Functions is a function estimating the cost of reaching a goal state from a given state

Question 17

What is the A* Algorithm?

Answer 17

The A* Algorithm uses Heuristic functions to estimate the promise of a child with. an Evaluation function

Question 18

What is the A* evalution function?

Answer 18

f(n) = g(n) + h(n)

f(n) = cost(start, n) + straight-line-distance(n, goal)
- The estimated cost for the rest

g(n) = Cost so far to reach n
h(h) = estimated cost from n to goal
f(n) = estimated total cost of path through n to goal

Question 19

What are the properties of A* algorithm?

Answer 19

A* always find the shortest path
- Type of Best-First-Search Algorithm

Combines the advantages of Breadth First and Depth first

A* is more efficient than breadth-first

A* GUARANTEES TO FIND THE SHORTEST PATH between the start node and the goal node

Question 20

What are Local search Algorithms?

Answer 20

In many optimization problems, the path to the goal is irrelevant; the goal state itself is the solution

Hill-climbing search