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

Re: [aima-talk] backtracking minimum remaining values USA map

Expand Messages
  • 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 1 of 3 , Jan 18, 2005
    • 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 2 of 3 , Jan 24, 2005
      • 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.