OK, it looks like I just implemented a slight variation of DSATUR ( http://fr.wikipedia.org/wiki/DSATUR) heuristic (but it should be most_constrained instead of first_fail). Sergii. On Tue, Apr 2, 2013 at 6:21 PM, Sergii Dymchenko <kit1980_at_...6...> wrote: > Hi again, > > I managed to solve my problem using this method: > > Colors array :: 1..4. > Bunch of Colors[I] #\= Colors[J] constraints. > search(Colors, 0, first_fail, indomain_min, complete, []). > The answer (minimal number of colors needed) is max value in Colors. > > I'm just not sure why this works correctly and if it works in general case > or for my instances only (around 100 tests with 100 nodes and around 100 > tests with 1000 nodes). > > The good thing is that it works fast (less than 30 sec for 100 tests of > 1000 nodes on my laptop). > > Sergii. > > > On Tue, Apr 2, 2013 at 4:34 PM, Mark Wallace <mark.wallace_at_...269...>wrote: > >> For variable choice use first-fail and for value choice use either >> indomain_random or a user-defined labelling which rotates the colours so >> the first guess for each variable is different from the last 3 (where 4 is >> the number of colours) >> >> >> >> On 3 April 2013 10:22, Sergii Dymchenko <kit1980_at_...6...> wrote: >> >>> Hi! >>> >>> Any suggestions how should I approach a graph coloring problem in >>> ECLiPSe? I'd want to do graph coloring for planar graphs of hundreds of >>> nodes. >>> >>> I tried naive encoding with ic library and bunch of #\= constraints, but >>> it works forever for graphs with one hundred nodes. >>> >>> Sergii. >>> >>> >>> >>> ------------------------------------------------------------------------------ >>> Minimize network downtime and maximize team effectiveness. >>> Reduce network management and security costs.Learn how to hire >>> the most talented Cisco Certified professionals. Visit the >>> Employer Resources Portal >>> http://www.cisco.com/web/learning/employer_resources/index.html >>> _______________________________________________ >>> ECLiPSe-CLP-Users mailing list >>> ECLiPSe-CLP-Users_at_lists.sourceforge.net >>> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users >>> >>> >> >> >> -- >> Professor Mark Wallace >> >> Faculty of Information Technology >> Level 6, Building H, Monash University >> 900 Dandenong Road, Caulfield East >> VIC 3145. Australia >> (03) 9903 4276 >> > >Received on Wed Apr 03 2013 - 03:06:49 CEST
This archive was generated by hypermail 2.3.0 : Tue Apr 16 2024 - 09:13:20 CEST