Teorifrågor från gamla tentor Flashcards
The basic backtracking algorithm used for CP solving is essentially a depth-first search. Why is that? Why would not breadth-first search be a better choice?
Depth-first is the best choice here, because each “level” corresponds to one variable and we want to find assignments to all variables as quickly as possible. A breadth-first search would search over the domain values for each variable first, which is not what we want.
When solving both MILP and CSP problems there needs to be selected the next variable to treat, and to choose a domain value for it. We know that solvers have lots of tricks and heuristics implemented for this, but let us consider the school book case that we have looked at. How is this selection of variable and value done for:
a) MILP solving, and
b) CSP solving, respectively?
c) Compare the two approaches of selecting variable and domain value. Can the approach of one be used in solving the other? What are the benefits, and the drawbacks?
In MILP solving (or rather the Simplex algorithm) looks at the objective function to find which variable affects it the most, either the one with the largest positive (for maximization) or negative (for minimization) coefficient. This finds the variable (the pivot column). To find its value, we choose the smallest value at which some constraint is “touched”. This also tells
us which other variable to take out (the pivot row).
In CP solving, there are several heuristics to use when choosing the variable, with the “minimum remaining value” heuristic choosing the variable with the smallest domain. For choosing the value of that variable then, the “least constraining value” heuristic is often used, as it tries to leave the greatest flexibility for the other variables.
Interchanging the approaches is typically not a good idea, as it would mean that in MILP we would take as small steps towards the optimum as possible, and so would need many more iterations. And using the MILP approach in CSP solving would instead reduce the domains as little as possible on each iteration, which is the exact opposite of what we want to do.
What is the significance of the fact that we can in principle always convert any CSP to a binary one?
As we understand from how the conversion works, we can always in principle convert back to the original non-binary CSP. Thus, the significance of the fact that we can always convert an arbitrary CSP to a binary one (and back), is that we only need to prove whatever we want to prove for binary CSPs. This is typically easier than having to deal with non-binary constraints.
When are A* and Dijkstra’s algorithms equivalent?
A* and Dijkstra’s algorithms are equivalent when A’s heuristic h(n) is always zero. With h(n) = 0, A relies only on the actual path cost g(n), just like Dijkstra’s, so they expand nodes in the same order and find the same shortest path.
