Combinatorial Search

Question 1

List and describe the two search problems

Answer 1

1. A Decision Problem

This attempts to find a solution that satisfies all constraints.

2. An Optimization Problem

This must find a solution that minimizes or maximizes the value of a given objective
function, whilst still satisfying all constraints

Question 2

What is an AND Node?

Answer 2

A (sub-)problem is only solves when all of its children are solved

Example: Divide and Conquer

Question 3

What is an OR Node?

Answer 3

A (sub-)problem is solved when any of its children are solved.

Examples: Backtracking, Branch and Bound

Question 4

Explain the Divide and Conquer Algorithm

Answer 4

This is a recursive method of searching by which problems are broken into sub-problems, and those into sub-problems etc etc. This ends up where those solutions are combined to form a global solution.

Question 5

Explain how the Divide and Conquer Algorithm works on a Centralised Processor as opposed to a Multicomputer

Answer 5

We use a centralised multiprocessor setup as the list of unsolved sub-problems can be kept on a single stack and manipulated by all the processors. Processors needing work can access the stack, and place work onto the stack if they have excess amounts. This allows us to balance load effectively.

With multi-computers​ , we need to share/scatter the memory of sub-problems to the individual processing workers. This means that work is more statically assigned.

Question 6

Explain Backtrack Search

Answer 6

Uses a depth-first search to consider a tree with many solutions. It generates all of its children and chooses one to continue on given a rule. Children are possible variants of the parent given a change in constraints (One move further)

Once it has either ​ reached a node with no children​ or all of the nodes children have
been explored​, a node will backtrack to its parent node, who will then either follow a
different sub-problem, or do the same thing.

Question 7

Explain Branch and Bound

Answer 7

We use branch and bound to find ​ optimal solutions​. It is a variant of the backtrack search. This uses information about optimality to reduce the number of partial solutions we need to explore. We prune off unexplored sub-problems based on the information that they cannot be
optimal.

We know what optimal value we would like to reach so we introduce bounds past which we would not want a solution.

Question 8

Explain Minimax Algorithm

Answer 8

The Minimax algorithm is a form of a depth-first search where each node holds the value of a position from the point of view of Player 1 determined by a given evaluation function. Player 1 wants to maximise the value while player 2 wants to minimise the value. (We basically want the best worst case scenario)

Question 9

Explain Alpha Beta pruning

Answer 9

Alpha-Beta pruning​ is the process of pruning branches when their optimal value falls below the current optimal value for that level. This significantly speeds up the Minimax algorithm but has no effect on its decision making.

Question 10

Which is better for the Divide and Conquer algorithm, a Centralised Multiprocessor or a Multicomputer.

Answer 10

Divide-and-conquer algorithms are more easily implemented on Centralised multiprocessors