Loading ...
Sorry, an error occurred while loading the content.

min-conflicts possible bug

Expand Messages
  • Ivan Villanueva
    Hello, I think I have found a Problem in the min-conflicts algorithm on page 151 of the international edition. For example, when the assignment for the
    Message 1 of 1 , Jan 28, 2005
    • 0 Attachment
      Hello,

      I think I have found a Problem in the min-conflicts algorithm on page
      151 of the international edition.

      For example, when the assignment for the Australian problem is:
      WA=green, NT=blue, Q=red, NSW=green, V=red, SA=blue, T=whatever

      the algorithm selects NT or SA, because they are the only two conflicted
      variables.
      NT=green has one conflict
      NT=red has one conflict
      NT=blue has one conflict
      Also the algorithm has to choose the minimum of this 3, and it could
      choose always blue because it is the last one.

      When SA is selected:
      green=2
      red=2
      blue=1
      Also blue is choosen.

      Because neither the assignment of NT nor the assignment of SA changes,
      the algorithm gets stuck.

      The easiest way, not the best, to solve the problem would be to
      select a random value when there are more than one minimum.
      CONFLICTS(...) in the pseudo code should be:
      select_random_value_among_minima

      Iván Villanueva
    Your message has been successfully submitted and would be delivered to recipients shortly.