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

backtracking minimum remaining values USA map

Expand Messages
  • Ivan Villanueva
    Hello, after having programming a backtracking with minimum remaining values, and tested it with a map coloring problem with the USA map, it comes out that the
    Message 1 of 3 , Jan 17, 2005
    View Source
    • 0 Attachment
      Hello,
      after having programming a backtracking with minimum remaining values,
      and tested it with a map coloring problem with the USA map, it comes out
      that the algorithm requires 5409 consistency checks, and not more than
      1,000,000 as printed on page 143 of the international edition.

      I wonder if somebody else have applied that algorithm to that problem
      and got similar results, or my result is faulty:

      [{LA=red, DC=red, MN=red, WA=red, DE=red, WV=red, KA=red, TN=red,
      RI=red, MT=re , OK=blue, VT=red, AL=blue, UT=red, WY=blue, MO=green,
      IA=blue, SC=red, VA=blue GA=green, OH=blue, KY=yellow, IL=red, OR=blue,
      NM=red, MA=blue, MS=green, HI=red, FL=red, SD=green, AK=red, ID=green,
      NY=green, NC=yellow, NH=green, WI=green, CO=green, NE=yellow, NV=yellow,
      MD=green, MI=red, TX=green, AZ=blue, IN=blue, C=red, PA=yellow,
      ND=blue, AR=yellow, CT=green, NJ=blue, ME=red}]

      Regards,
      Iván Villanueva
    • Ivan Villanueva
      ... It seems that the above result has been a lucky coincidence. After changing a little bit the code, the algorithm doesn t find the solution any more. I
      Message 2 of 3 , Jan 18, 2005
      View Source
      • 0 Attachment
        On Mon, Jan 17, 2005 at 12:24:58PM +0100, Ivan Villanueva wrote:
        >
        > Hello,
        > after having programming a backtracking with minimum remaining values,
        > and tested it with a map coloring problem with the USA map, it comes out
        > that the algorithm requires 5409 consistency checks, and not more than
        > 1,000,000 as printed on page 143 of the international edition.
        >
        > I wonder if somebody else have applied that algorithm to that problem
        > and got similar results, or my result is faulty:
        >
        > [{LA=red, DC=red, MN=red, WA=red, DE=red, WV=red, KA=red, TN=red,
        > RI=red, MT=re , OK=blue, VT=red, AL=blue, UT=red, WY=blue, MO=green,
        > IA=blue, SC=red, VA=blue GA=green, OH=blue, KY=yellow, IL=red, OR=blue,
        > NM=red, MA=blue, MS=green, HI=red, FL=red, SD=green, AK=red, ID=green,
        > NY=green, NC=yellow, NH=green, WI=green, CO=green, NE=yellow, NV=yellow,
        > MD=green, MI=red, TX=green, AZ=blue, IN=blue, C=red, PA=yellow,
        > ND=blue, AR=yellow, CT=green, NJ=blue, ME=red}]

        It seems that the above result has been a lucky coincidence. After
        changing a little bit the code, the algorithm doesn't find the solution
        any more. I suppose that the first version of my algorithm (just by
        chance) chose the right variables at the beginning of the search, and/or
        the right values.

        Iván Villanueva
      • Ivan Villanueva
        ... I apology for using this mailing list as a blog, but maybe some day some one is interested in this issue. Forget the last paragraph, the program was buggy.
        Message 3 of 3 , Jan 24, 2005
        View Source
        • 0 Attachment
          On Tue, Jan 18, 2005 at 06:59:59PM +0100, Ivan Villanueva wrote:
          > On Mon, Jan 17, 2005 at 12:24:58PM +0100, Ivan Villanueva wrote:
          > >
          > > Hello,
          > > after having programming a backtracking with minimum remaining values,
          > > and tested it with a map coloring problem with the USA map, it comes out
          > > that the algorithm requires 5409 consistency checks, and not more than
          > > 1,000,000 as printed on page 143 of the international edition.
          > >
          > > I wonder if somebody else have applied that algorithm to that problem
          > > and got similar results, or my result is faulty:
          > >
          > > [{LA=red, DC=red, MN=red, WA=red, DE=red, WV=red, KA=red, TN=red,
          > > RI=red, MT=re , OK=blue, VT=red, AL=blue, UT=red, WY=blue, MO=green,
          > > IA=blue, SC=red, VA=blue GA=green, OH=blue, KY=yellow, IL=red, OR=blue,
          > > NM=red, MA=blue, MS=green, HI=red, FL=red, SD=green, AK=red, ID=green,
          > > NY=green, NC=yellow, NH=green, WI=green, CO=green, NE=yellow, NV=yellow,
          > > MD=green, MI=red, TX=green, AZ=blue, IN=blue, C=red, PA=yellow,
          > > ND=blue, AR=yellow, CT=green, NJ=blue, ME=red}]
          >
          > It seems that the above result has been a lucky coincidence. After
          > changing a little bit the code, the algorithm doesn't find the solution
          > any more. I suppose that the first version of my algorithm (just by
          > chance) chose the right variables at the beginning of the search, and/or
          > the right values.

          I apology for using this mailing list as a blog, but maybe some day some
          one is interested in this issue. Forget the last paragraph, the program was buggy.

          I have changed again my program. Now it chooses randomly the order of
          the variables. Here are the results of two representative runs:

          [ivan@golem:classes]$ java com/artificialidea/problemsolving/constraintsearch/EfficientBacktrackingSearch
          Solving USA example with forward checking and minimum remaining value:
          Consistency checks: 4819
          Milliseconds needed: 1424
          Solving USA example with minimum remaining value:
          Consistency checks: 5407
          Milliseconds needed: 1433
          Solving USA example with forward checking:
          Consistency checks: 552
          Milliseconds needed: 1111
          [ivan@golem:classes]$ java com/artificialidea/problemsolving/constraintsearch/EfficientBacktrackingSearch
          Solving USA example with forward checking and minimum remaining value:
          Consistency checks: 4633
          Milliseconds needed: 1379
          Solving USA example with minimum remaining value:
          Consistency checks: 5402
          Milliseconds needed: 1436
          Solving USA example with forward checking:
          Consistency checks: 1360121
          Milliseconds needed: 2358269

          As you can see, minimum remaining values solves the problem much more
          faster than pointed out in the book, but forward checking can take a
          eternity to solve it, or can be very fast (it depends of the order of
          the variables; here they were randomly chosen, thus the huge difference
          between the two runs for forward checking).

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