Inconsistent assignment

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Inconsistent assignment
Hi,

can you please explain, what exactly inconsistent assignment means, but with other words (not with the math definition)?
I have already viewed the video about it and read the notes, however I am still not able to tell what it means or to use it…

Thanks!


An assignment is a choice of values for variables. Regarding the Australia example from the slides: An assignment denotes which colors have been chosen for which state.

The assignment is inconsistent if it violates any constraint. In the Australia example the constraint is “neighbors may not be colored equally”. So assigning red to both Western Australia and Northern Territory (which are neighbors) violates the constraint. Any assignment with equal colors for neighbor states is inconsistent.

Does this help you?

Maybe the following can also help you understand the mathematical definition:

The mathematical definition wants to express that a combination of two variables break the rules if all these conditions are fufilled:

  • Both variables are already assigned. So the assignment function is defined for them. (“there are variables u,v in dom(a)”)
  • There actually exists a constraint between. So they are not independent from each other. (“C_uv in C”)
  • Their values are not in the list of allowed combinations which are defined by the constraint. (“(a(u), a(v)) in C_uv”)

Thank you! That helps me a lot.
However one thing is still unclear to me.

Does inconsistent assignment is the “same” as not allowed?
If we have constrain, so in the Australia example we have constraints that “neighbors may not be colored equally” we are actually not allowed to assign the same color color to the neighbors. So it basically means we are doing something that is not allowed. So my question is: how do we come in that situation to assign the same color to the neighbor, when that is not allowed (and we know it already)? Is it something we are “trapped in”, or do we just imagine what would be if we assign the same color to the neighbor?


It’s not allowed, if you want to satisfy all the constraints. Inconsistent assignments are „possible“, but would be wrong. You could write a program that attempts to solve the graph-coloring problem for Australia, by assigning every area the same color. But that would obivously not be what you want (unless you have a fully-unconnected graph).

Graph Coloring, which is basically the problem we discussed when talking about the map of australia, is not a trivial problem (it’s in NP), so the best general algorithm we know if is to just try out different combinations. And if you assign something that isn’t consistent (eg. New South Wales and Victoria both have the same color), then you have to back-track, and try a different approach.


Thanks!