AI problem solving

Question 1

How do you make use of the different techniques? In what order?

Answer 1

Do you think the problem might be polynomial, then go for no less than a perfect solution
- Your main alternatives: 1. D&C, 2. DP, 3. greedy

If you think the problem is exponential, you will probably have to accept some compromises:
- Use an exponential algorithm and avoid solving large problems. If you tune it, maybe you will be able to solve your problem.
- or use a heuristic that is faster but may give lower quality

If you have no idea try all methods (in several ways) and then analyze your algorithms!

Question 2

List the five main discrete algorithm design techniques

Answer 2

1. Divide and conquer
2. Dynamic programming
3. Greedy algorithm/heuristic.
   [ Do what seems best in every step. Is often heuristic. ]
4. Combinatorial search
   [Test all possibilities or a subset of them. Use “branch and bound” to speed up]
5. Local search
   [Take a solution and repeatedly improve it by making small changes. Is often heuristic]

Question 3

What is constraint programming?

Answer 3

A paradigm for solving combinatorial problems that draw on a wide range or techniques.
Declaring constraints on the feasible solutions for a set of decision variables.

Some are: AI, computer science, and operations research

Question 4

What are the alternatives to constraint programming?
AND how is constraint programming different?

Answer 4

Differs from common primitives of imperative programming in that they specify the properties of the solution rather than the step or sequence of steps to execute.