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

CSP problem MRV can be implemented independently?

Expand Messages
  • chenyu468
    Hello everyone, I have downloaded AIMA version 2 sample chapter 5 and am doing its exercises. In exercise 5.7, it requires to compare the algorithms of MRV,
    Message 1 of 2 , Dec 30, 2003
    • 0 Attachment
      Hello everyone,
      I have downloaded AIMA version 2 sample chapter 5 and am doing its
      exercises.

      In exercise 5.7, it requires to compare the algorithms of MRV,
      forward checking, FC+MRV, Min-conflicts.
      But I wonder is it possible to implement MRV independently without FC?
      My impossible reasons are as follows:
      1. MRV means "minimium remaining values". It means the unassigned
      variable with "minimium remaining values" should be selected firstly.
      The 2 implementation ideas are
      1. to filter unassigned variables' domain everytime after
      assigning a variable.
      or
      2. calculate the every unassigned variable's legal domains
      everytime before select.

      The above 2nd implemenation is low efficient for repeat calculation
      on legal domains, therefore, it is a bad idea.

      So only the 1st implementation is accepted. It seems the exercise 5.7
      should be modified to "compare the algorithms of FC,FC+MRV,Min-
      conflicts.

      What's about your idea?


      Thank you for your attention.
      Best regards/chenyu
    • Brandon Corfman
      Page 144 of your d/l copy refers to the method of BT + MRV, meaning that FC is not needed. However, they work like hand in glove. At the bottom of the same
      Message 2 of 2 , Dec 31, 2003
      • 0 Attachment
        Page 144 of your d/l copy refers to the method of BT + MRV, meaning
        that FC is not needed. However, they work like hand in glove. At the
        bottom of the same page, the book says FC is an efficient way to
        compute MRV. Otherwise, finding the MRV involves many redundant
        computations, as you've noticed.

        For a more in-depth explanation, see
        http://www.cs.toronto.edu/~fbacchus/Papers/BvRCP95.pdf
        and look at pages 6 & 7.

        Best regards,
        Brandon

        --- In aima-talk@yahoogroups.com, "chenyu468" <chenyu468@y...> wrote:
        > Hello everyone,
        > I have downloaded AIMA version 2 sample chapter 5 and am doing its
        > exercises.
        >
        > In exercise 5.7, it requires to compare the algorithms of MRV,
        > forward checking, FC+MRV, Min-conflicts.
        > But I wonder is it possible to implement MRV independently without
        FC?
        > My impossible reasons are as follows:
        > 1. MRV means "minimium remaining values". It means the unassigned
        > variable with "minimium remaining values" should be selected
        firstly.
        > The 2 implementation ideas are
        > 1. to filter unassigned variables' domain everytime after
        > assigning a variable.
        > or
        > 2. calculate the every unassigned variable's legal domains
        > everytime before select.
        >
        > The above 2nd implemenation is low efficient for repeat calculation
        > on legal domains, therefore, it is a bad idea.
        >
        > So only the 1st implementation is accepted. It seems the exercise
        5.7
        > should be modified to "compare the algorithms of FC,FC+MRV,Min-
        > conflicts.
        >
        > What's about your idea?
        >
        >
        > Thank you for your attention.
        > Best regards/chenyu
      Your message has been successfully submitted and would be delivered to recipients shortly.