From: Warwick Harvey <wh_at_icparc.ic.ac.uk>

Date: Wed 25 Oct 2000 05:25:49 PM GMT

Message-ID: <39F7179D.3FD36AE4@icparc.ic.ac.uk>

Date: Wed 25 Oct 2000 05:25:49 PM GMT

Message-ID: <39F7179D.3FD36AE4@icparc.ic.ac.uk>

Hi Farouk, I'm afraid I'm still struggling to figure out what you're trying to do (and looking at your code hasn't really helped). You wrote: > To answer your questions, actually what I would like to implement is a > case where I have n-nodes of a graph with costs Ci, i = 1,..,n > associated with the edges of the graph. Cij are costs of going from node i > to node j. The ordering I need to implement is just like a sequence of the > edges such that the costs for traversing edge i (Ci) is the accumulated > cost of all the edges traversed so far plus the cost of going from the > second node of the previous edge to the first node of the current edge > plus the cost of traversing the current edge itself. This description doesn't seem to make sense. You say you have a graph with n nodes. You then say that you have costs Ci corresponding to the edges of the graph, with i ranging from 1 to n. This implies you have exactly the same number of edges in the graph as you do nodes. Is this the case? If so, you seem to have left out some important information about the graph. If not, then please explain what you really mean. You then say Cij is the cost of going from node i to node j. How is this different from Ci? Are they related? Hang on, I think I've just figured out an important piece of the puzzle. I was assuming you were starting with some graph, and trying to find a path through that graph which satisfies some properties you're interested in. This is how it's normally formulated for this kind of graph-based problem. But it seems you've been thinking of it as starting with a bunch of nodes and adding in some edges (rather than selecting some edges from a given set). What is still rather unclear is how you know/record where edge `i' goes --- given you didn't specify this, I assumed it was known because edge `i' was fixed, which is how I came to be assuming you were selecting edges from an existing graph. I think the main problem you have here is that you don't have a good, solid explanation of the problem you're trying to solve, nor of how the variables you're using relate to this problem description. Whenever I'm trying to solve a constraint problem where the solution is not immediately obvious, the first thing I do is try to write down a precise description of the problem, including what information I'm given, and what information I'm trying to figure out. I then think about what variables/values/data structures I think I will need to represent that problem, and write them down, including exactly what they represent. I then try to write down all the constraints I think I will need, plus any other relevant notes or explanations I think somebody else will need to understand what I'm trying to do. This then gives me a precise, concrete model I can use to start trying to implement. Doing this often shows up problems or flaws in the way I've decided to represent something, and I'll go back and revise it, sometimes 3 or 4 or more times. It's *much* easier to fix conceptual problems at this point than when you're in the middle of trying to code it and you're distracted by a lot of incidental details. It also means that if you need to ask somebody for help down the track, you have a nice description you can give them to help them understand what you're trying to do. After having spent several hours on this, I believe I have figured out just what it is you're trying to do, so I'm going to try to get you started on such a description for your program: We have a graph containing N nodes, labelled 1 to n. The graph is complete, meaning there is an arc from every node to every other node. The cost of traversing the arc from node i to node j is given, and may be different from the cost of traversing the arc in the opposite direction. We want to find a Hamiltonian cycle [this is what you want right? a path that visits every node and ends up back where it started?] that satisfies [insert your criteria here --- are we minimising cost? you can talk more about side constraints later]. As well as the cost for traversing an arc, there is a cost for visiting each node. Note that while this does not affect which cycle(s) have minimal cost (since all nodes are visited by all possible cycles), it can affect whether a cycle is feasible, since there may be constraints on the cumulative cost at various points in the cycle. [etc.] Flesh this out (correcting anything I've got wrong), talking about what kinds of constraints there are, etc. If you like, post it back to the mailing list when you're done and I'll give you some feedback. Then you can move on to the next step, which is identifying which variables you need (because you have explicit constraints on them) and just how you're going to represent the cycle, etc., and how you're going to tie it all together. Once you've got that right, then we can worry about how to express it in ECLiPSe. Note that there is a *lot* of literature out there on Hamiltonian cycles and the Travelling Salesman Problem (TSP). I strongly suggest you go have a look at some of it to see how other people have modelled this kind of stuff --- maybe you'll get some inspiration. I'm sure somebody in your department can give you some pointers as to where to start looking. I have also attached to this email a real example of the above process from when I was solving the "domino" puzzle Doug Edmunds posted at the start of the year. I include this particular example because it shows that most of the way through, I realised I had made a poor choice of data structure (a list of lists), and revised that choice (used an array). And of course, once you've gone to the trouble of producing this description, the final version should of course be included with the program as documentation. :) Cheers, Warwick > Message-ID: <000d01bf561a$6b3f1d20$818a41d8@daehp> > From: "Doug Edmunds" <edmunds@pacifier.com> > To: "eclipse-users" <eclipse-users@icparc.ic.ac.uk> > Subject: domino puzzle > Date: Mon, 3 Jan 2000 10:42:04 -0800 > > Happy New Year! > > Can anyone suggest an approach to solving this type of puzzle? > > There are 28 dominos 0-0 to 6-6 ( 0-0, 0-1,0-2,..., 5-5,5-6,6-6). > > They are layed out randomly on a rectangular shape so that > there are 8 numbers across and 7 down. There is no relation > between adjoining tiles. > > Tiles can appear left-right or up-down: 3-5 can be positioned > 3-5, 5-3, > 3 > 5, > or as > 5 > 3. > > The object is to reconstruct the tile-boundaries, using eclipse. > No tile is used twice. Each number in the grid is part on only > one tile. > > Puzzle pattern: > > 3 1 2 6 6 1 2 2 > 3 4 1 5 3 0 3 6 > 5 6 6 1 2 4 5 0 > 5 6 4 1 3 3 0 0 > 6 1 0 6 3 2 4 0 > 4 1 5 2 4 3 5 5 > 4 1 0 2 4 5 2 0 > > > Doug Edmunds > edmunds@pacifier.com > 3 Jan 2000 Proposed model: Have a set of boolean variables, one for each boundary between adjacent squares, indicating whether or not a tile lies across that boundary. We then have two sets of constraints. 1) Each square must have exactly one boundary with a tile lying across it. 2) For each pair of numbers from [0..6], exactly one boundary having these numbers on either side must have a tile lying across it. If the squares are labelled (1,1) through (7,8), then label the boundaries as follows: 1,1 H11 1,2 H12 1,3 H13 1,4 H14 1,5 H15 1,6 H16 1,7 H17 1,8 V11 V12 V13 V14 V15 V16 V17 V18 2,1 H21 2,2 H22 2,3 H23 2,4 H24 2,5 H25 2,6 H26 2,7 H27 2,8 V21 V22 V23 V24 V25 V26 V27 V28 3,1 H31 3,2 H32 3,3 H33 3,4 H34 3,5 H35 3,6 H36 3,7 H37 3,8 V31 V32 V33 V34 V35 V36 V37 V38 4,1 H41 4,2 H42 4,3 H43 4,4 H44 4,5 H45 4,6 H46 4,7 H47 4,8 V41 V42 V43 V44 V45 V46 V47 V48 5,1 H51 5,2 H52 5,3 H53 5,4 H54 5,5 H55 5,6 H56 5,7 H57 5,8 V51 V52 V53 V54 V55 V56 V57 V58 6,1 H61 6,2 H62 6,3 H63 6,4 H64 6,5 H65 6,6 H66 6,7 H67 6,8 V61 V62 V63 V64 V65 V66 V67 V68 7,1 H71 7,2 H72 7,3 H73 7,4 H74 7,5 H75 7,6 H76 7,7 H77 7,8 The constraint 1) for the square (i,j) is then Hi(j-1) + Hij + V(i-1)j + Vij = 1 where for convenience we define Hi0 = Hi8 = V0j = V7j = 0 for all i, j. For constraint 2, we collect all horizontal and vertical boundaries between squares matching each pair of numbers, sum them, and equate to 1. Store Hij's and Vij's in lists of lists, where i selects the sublist and j selects the element. i.e. [[H11, H12, ..., H17], [H21, ..., H27], ..., [H71, ..., H77]] [[V11, V12, ..., V18], [V21, ..., V28], ..., [V61, ..., V68]] To construct the constraints 1), iterate over i, keeping the "previous" sublist of V(i-1)j's (initially a list of zeros). Then iterate over j, keeping the "previous" Hi(j-1) (initially zero). - have to handle the case where we run out of H's (Hi8 = 0) - have to handle the case where we run out of Vi's (V7j = 0) ... Actually, scrap the above and use arrays! :-) It would then be better if the Hs were H12 .. H78 and the Vs were V21 .. V78 so that Hi1 and V1j can be set to 0, and the array indexing works out. This yields: If the squares are labelled (1,1) through (7,8), then label the boundaries as follows: 1,1 H12 1,2 H13 1,3 H14 1,4 H15 1,5 H16 1,6 H17 1,7 H18 1,8 V21 V22 V23 V24 V25 V26 V27 V28 2,1 H22 2,2 H23 2,3 H24 2,4 H25 2,5 H26 2,6 H27 2,7 H28 2,8 V31 V32 V33 V34 V35 V36 V37 V38 3,1 H32 3,2 H33 3,3 H34 3,4 H35 3,5 H36 3,6 H37 3,7 H38 3,8 V41 V42 V43 V44 V45 V46 V47 V48 4,1 H42 4,2 H43 4,3 H44 4,4 H45 4,5 H46 4,6 H47 4,7 H48 4,8 V51 V52 V53 V54 V55 V56 V57 V58 5,1 H52 5,2 H53 5,3 H54 5,4 H55 5,5 H56 5,6 H57 5,7 H58 5,8 V61 V62 V63 V64 V65 V66 V67 V68 6,1 H62 6,2 H63 6,3 H64 6,4 H65 6,5 H66 6,6 H67 6,7 H68 6,8 V71 V72 V73 V74 V75 V76 V77 V78 7,1 H72 7,2 H73 7,3 H74 7,4 H75 7,5 H76 7,6 H77 7,7 H78 7,8 The constraint 1) for the square (i,j) is then Hij + Hi(j+1) + Vij + V(i+1)j = 1 where for convenience we define Hi1 = Hi9 = V1j = V8j = 0 for all i, j. For constraint 2, we collect all horizontal and vertical boundaries between squares matching each pair of numbers, sum them, and equate to 1.Received on Wed Oct 25 18:26:35 2000

*
This archive was generated by hypermail 2.1.8
: Wed 16 Nov 2005 06:07:06 PM GMT GMT
*