Perl Monk, Perl Meditation | |
PerlMonks |
comment on |
( [id://3333]=superdoc: print w/replies, xml ) | Need Help?? |
(I considered submitting this as a meditation, but due to my lack of knowledge on the topic, I thought better of posting there.) Recently I was thinking about a problem. Specifically, I was considering the idea from the point of view of "ants" (for lack of a better term) following all of the possible paths, and trying to think through how to determine if a path has been completed. As a starting thought experiment, I considered 6 points, with ants moving from each point to each remaining point. I thought of 5 different cases that could occur (points labeled '1'..'6', paths written ordered least to greatest):
The cases map out (roughly) as follows: Case 1: 1 - 2 - 3 6 5 4 Case 2: 1 - 2 - 3 \ 6 - 5 - 4 Case 3: 1 - 2 - 3 \ 6 - 5 - 4 \ / + Case 4: 1 - 2 - 3 \ \ 6 - 5 - 4 Case 5: 1 - 2 - 3 \ / | \ 6 - 5 - 4 \ / + (I realized as I was writing this that being able to find that a path might not be as useful as I thought, but that does not take *that much* away from this question.) I'm not aware of (or at least remember) dealing with graphs in the CS classes I took (years ago), so there may be a nice theory or approach I am not aware of. What I came up with was to create a matrix containing the number of connections between between points. (By writing all of the connections in least-greatest ordering, only half the matrix had to be used, as illustrated by the following. Unfilled entries are noted as '-', otherwise the count of connections is filled in in row-column order.) Case 1 Case 2 Case 3 Case 4 Case 5 X 1 2 3 4 5 6 X 1 2 3 4 5 6 X 1 2 3 4 5 6 X 1 2 3 4 5 6 X 1 2 3 4 5 6 1 - 1 0 0 0 0 1 - 1 0 0 0 1 1 - 1 0 0 0 1 1 - 1 0 0 0 1 1 - 1 0 0 0 1 2 - - 1 0 0 0 2 - - 1 0 0 0 2 - - 1 0 0 0 2 - - 1 0 0 0 2 - - 1 0 0 0 3 - - - 0 0 0 3 - - - 0 0 0 3 - - - 0 0 0 3 - - - 1 0 0 3 - - - 1 1 1 4 - - - - 0 0 4 - - - - 1 0 4 - - - - 1 1 4 - - - - 1 0 4 - - - - 1 1 5 - - - - - 0 5 - - - - - 1 5 - - - - - 1 5 - - - - - 1 5 - - - - - 1 6 - - - - - - 6 - - - - - - 6 - - - - - - 6 - - - - - - 6 - - - - - - What I noticed was that in the cases (1-3) where a connection did not exist, there was at least one row in which the sum of entries on the row was zero, but in cases where a full path existed all rows had a non-zero sum. Is this approach too simplistic-minded (or did I just stumble upon something I should have known)? Sample code:
Output: $ ./test.pl test_1 Missing row 3 Missing row 4 Missing row 5 test_2 Missing row 3 test_3 Missing row 3 test_4 test_5 Thank you for your attention and insights. (And my apologies if I have wasted your time.) Update: 2018-07-16 Thank you for your feedback. To answer OM and tobyink, yes, apparently what I am looking for is a Hamiltonian path through the set. (I didn't know the proper term(s) to use to search, among other things.) To answer bliako, yes, I know ants would have started from each point, but for simplicity I showed only completed paths of equal length. To apply this to the original problem, I can see two ways: a) follow the idea of an actual ant, and track each ant's actual position, or b) knowing the edges and their lengths, I would probably look to move down the list of all edges (tracking the sum total) and update the matrix form (above, or other method) to check if a complete path exists. In reply to Is this a valid approach to finding if a path through a set of points has completed? by atcroft
|
|