Re^12: Travelling problem (Anyone better 86850?)

in reply to Re^11: Travelling problem (Anyone better 86850?)
in thread Travelling problem

successfully completed the restricted branching based on the shortest two or three next available edges

My threaded C version has now completed restricted branching at shortest 2,3,4,5,6,7 available edges and the best it found are:

2 - 134842    1s  14e5 perms.
3 - 114847    23s 30e6 perms.
4 - 102428    4m  .5e9 perms. 
5 -  99505    15m  5e9 perms.
6 -  99056 1h 53m 30e9 perms.
7 -  92705 4h  7m 69e9 perms.
[download]

Note: The numbers are provisional in as much as I have repeated them to check they are repeatable; given the possibility of non-determinacy due to threading.

I'll leave it running overnight on 8.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

Comment on Re^12: Travelling problem (Anyone better 86850?) Download Code

Replies are listed 'Best First'.
Re^13: Travelling problem (Anyone better 86850?) by hdb (Monsignor) on Dec 28, 2013 at 07:41 UTC
My Perl code does find 84860 when restricting to the 2 or 3 shortest edges, so something seems to be wrong with your code...	[reply]
Re^14: Travelling problem (Anyone better 86850?) by BrowserUk (Patriarch) on Dec 28, 2013 at 14:11 UTC
Hm. If we sort the edges of the OP data [ [[ 0, 0],[ 3812, 1], [ 3267, 20], [ 5015, 5], [ 5230, 6], [ +5409, 16], [ 6170, 11], [ 6812, 12], [ 7575, 10], [ 8030, 15], [ 8619 +, 3], [ 9487, 13], [ 9615, 7], [10624, 8], [11078, 23], [11223, 22 +], [12822, 18], [12882, 21], [13346, 9], [13902, 2], [15811, 4], [ +17136, 19], [17959, 17], [18135, 14]], [[ 0, 1],[ 3764, 10], [ 3812, 0], [ 4519, 6], [ 5154, 15], [ +6668, 11], [ 7056, 20], [ 7266, 23], [ 8057, 5], [ 8276, 16], [ 8761 +, 7], [ 9367, 18], [ 9698, 21], [10603, 12], [11117, 13], [11527, 2 +], [12431, 3], [12569, 9], [13603, 22], [14398, 8], [14805, 14], [ +14840, 19], [15446, 4], [18175, 17]], [[ 0, 2],[ 3236, 18], [ 3457, 19], [ 4611, 7], [ 6381, 15], [ +6655, 23], [ 6859, 14], [ 7602, 17], [ 8226, 11], [ 8675, 6], [ 8798 +, 10], [ 8830, 21], [10220, 4], [11223, 16], [11527, 1], [11970, 9 +], [12993, 8], [13638, 3], [13902, 0], [14535, 20], [14748, 22], [ +15087, 12], [16591, 13], [18405, 5]], [[ 0, 3], [ 1926, 12],[ 2157, 8], [ 5402, 20], [ 5555, 5], [ +5737, 16], [ 5765, 22], [ 7111, 13], [ 8619, 0], [ 9378, 17], [ 9609 +, 11], [ 9965, 4], [10917, 9], [11256, 6], [11549, 7], [11899, 19 +], [12431, 1], [12565, 14], [13638, 2], [14906, 15], [15921, 21], [ +16194, 10], [16868, 18], [19675, 23]], [[ 0, 4], [ 2940, 9],[ 3517, 14], [ 3627, 17], [ 5155, 22], [ +6374, 13], [ 6475, 21], [ 7077, 19], [ 7873, 8], [ 9965, 3], [10220 +, 2], [10235, 23], [10307, 18], [11057, 12], [11122, 5], [13119, 10 +], [14478, 20], [14599, 7], [14973, 15], [15446, 1], [15565, 16], [ +15811, 0], [17793, 11], [18683, 6]], [[ 0, 5],[ 3811, 12], [ 3881, 20], [ 4858, 13], [ 5015, 0], [ +5555, 3], [ 6210, 22], [ 6744, 8], [ 7186, 16], [ 8057, 1], [ 9617 +, 9], [10109, 6], [10270, 11], [11122, 4], [11348, 10], [12658, 21 +], [12975, 15], [13212, 17], [13856, 7], [14138, 23], [14594, 14], [ +17106, 19], [17301, 18], [18405, 2]], [[ 0, 6],[ 2299, 11], [ 3741, 15], [ 4519, 1], [ 4584, 7], [ +5230, 0], [ 5549, 16], [ 6018, 10], [ 6865, 20], [ 8377, 18], [ 8600 +, 23], [ 8675, 2], [10109, 5], [10267, 12], [11256, 3], [11981, 19 +], [12543, 21], [13284, 8], [14709, 13], [15205, 14], [15863, 17], [ +16177, 22], [16923, 9], [18683, 4]], [[ 0, 7], [ 3619, 11],[ 4584, 6], [ 4611, 2], [ 4627, 15], [ +6102, 18], [ 6948, 16], [ 7523, 19], [ 8240, 10], [ 8550, 23], [ 8761 +, 1], [ 9615, 0], [ 9992, 20], [11282, 17], [11444, 14], [11549, 3 +], [11888, 12], [12321, 21], [12503, 8], [13856, 5], [14599, 4], [ +16548, 9], [16782, 22], [18524, 13]], [[ 0, 8], [ 2157, 3], [ 3813, 12],[ 4374, 22], [ 6447, 13], [ +6744, 5], [ 7340, 17], [ 7492, 20], [ 7735, 16], [ 7873, 4], [ 9231 +, 9], [10421, 19], [10427, 14], [10624, 0], [11405, 11], [12503, 7 +], [12993, 2], [13284, 6], [14151, 21], [14398, 1], [15982, 18], [ +16699, 15], [18070, 10], [18092, 23]], [[ 0, 9],[ 2940, 4], [ 4874, 13], [ 5008, 21], [ 5170, 22], [ +5269, 14], [ 6543, 17], [ 9146, 23], [ 9231, 8], [ 9458, 19], [ 9617 +, 5], [10709, 18], [10917, 3], [11052, 10], [11199, 12], [11970, 2 +], [12569, 1], [13346, 0], [13488, 20], [14093, 15], [16358, 16], [ +16548, 7], [16923, 6], [19220, 11]], [[ 0, 10], [ 3508, 23],[ 3614, 15], [ 3764, 1], [ 5954, 18], [ +6018, 6], [ 6649, 21], [ 7575, 0], [ 8220, 11], [ 8240, 7], [ 8798 +, 2], [10801, 20], [11052, 9], [11186, 14], [11306, 16], [11348, 5 +], [11533, 19], [12490, 13], [13119, 4], [14354, 12], [14452, 17], [ +14987, 22], [16194, 3], [18070, 8]], [[ 0, 11], [ 2299, 6], [ 3619, 7],[ 3975, 16], [ 5330, 15], [ +6170, 0], [ 6469, 20], [ 6668, 1], [ 8220, 10], [ 8226, 2], [ 9100 +, 18], [ 9124, 12], [ 9609, 3], [10270, 5], [10326, 23], [10994, 19 +], [11405, 8], [14165, 17], [14453, 21], [15059, 14], [15115, 13], [ +15268, 22], [17793, 4], [19220, 9]], [[ 0, 12],[ 1926, 3], [ 3728, 20], [ 3811, 5], [ 3813, 8], [ +5168, 16], [ 6168, 22], [ 6645, 13], [ 6812, 0], [ 9124, 11], [10267 +, 6], [10603, 1], [11057, 4], [11153, 17], [11199, 9], [11888, 7 +], [13808, 19], [13999, 15], [14126, 14], [14354, 10], [15087, 2], [ +15782, 21], [17749, 23], [17968, 18]], [[ 0, 13], [ 2621, 22], [ 4858, 5],[ 4874, 9], [ 6374, 4], [ +6447, 8], [ 6645, 12], [ 7111, 3], [ 8652, 20], [ 9157, 21], [ 9288 +, 17], [ 9487, 0], [ 9754, 14], [11117, 1], [11588, 16], [12490, 10 +], [12782, 23], [13331, 19], [14709, 6], [15115, 11], [15400, 18], [ +15942, 15], [16591, 2], [18524, 7]], [[ 0, 14],[ 3379, 17], [ 3517, 4], [ 4250, 19], [ 5269, 9], [ +5311, 21], [ 6859, 2], [ 6883, 18], [ 7729, 23], [ 8643, 22], [ 9754 +, 13], [10427, 8], [11186, 10], [11444, 7], [11725, 15], [12565, 3 +], [14126, 12], [14594, 5], [14805, 1], [15059, 11], [15205, 6], [ +16484, 16], [17835, 20], [18135, 0]], [[ 0, 15], [ 3614, 10], [ 3741, 6],[ 4627, 7], [ 4874, 18], [ +5003, 23], [ 5154, 1], [ 5330, 11], [ 6381, 2], [ 8030, 0], [ 9122 +, 21], [ 9173, 16], [ 9780, 19], [10451, 20], [11725, 14], [12975, 5 +], [13841, 17], [13999, 12], [14093, 9], [14906, 3], [14973, 4], [ +15942, 13], [16699, 8], [18555, 22]], [[ 0, 16],[ 3450, 20], [ 3975, 11], [ 5168, 12], [ 5409, 0], [ +5549, 6], [ 5737, 3], [ 6948, 7], [ 7186, 5], [ 7735, 8], [ 8276 +, 1], [ 9173, 15], [11223, 2], [11293, 22], [11306, 10], [11588, 13 +], [12642, 19], [12955, 18], [13413, 17], [14142, 23], [15565, 4], [ +16358, 9], [16484, 14], [17931, 21]], [[ 0, 17], [ 3379, 14], [ 3627, 4],[ 4145, 19], [ 6543, 9], [ +7147, 22], [ 7340, 8], [ 7602, 2], [ 8581, 21], [ 9181, 18], [ 9288 +, 13], [ 9378, 3], [10945, 23], [11153, 12], [11282, 7], [13212, 5 +], [13413, 16], [13841, 15], [14165, 11], [14452, 10], [14775, 20], [ +15863, 6], [17959, 0], [18175, 1]], [[ 0, 18], [ 3236, 2], [ 3419, 23], [ 4874, 15], [ 5593, 19], [ +5954, 10], [ 6102, 7],[ 6278, 21], [ 6883, 14], [ 8377, 6], [ 9100 +, 11], [ 9181, 17], [ 9367, 1], [10307, 4], [10709, 9], [12822, 0 +], [12955, 16], [15242, 20], [15400, 13], [15447, 22], [15982, 8], [ +16868, 3], [17301, 5], [17968, 12]], [[ 0, 19],[ 3457, 2], [ 4145, 17], [ 4250, 14], [ 5593, 18], [ +7077, 4], [ 7523, 7], [ 8453, 23], [ 8478, 21], [ 9458, 9], [ 9780 +, 15], [10421, 8], [10994, 11], [11291, 22], [11533, 10], [11899, 3 +], [11981, 6], [12642, 16], [13331, 13], [13808, 12], [14840, 1], [ +15914, 20], [17106, 5], [17136, 0]], [[ 0, 20], [ 3267, 0], [ 3450, 16], [ 3728, 12],[ 3881, 5], [ +5402, 3], [ 6469, 11], [ 6865, 6], [ 7056, 1], [ 7492, 8], [ 8652 +, 13], [ 9326, 22], [ 9992, 7], [10451, 15], [10801, 10], [13488, 9 +], [14308, 23], [14478, 4], [14535, 2], [14775, 17], [15242, 18], [ +15624, 21], [15914, 19], [17835, 14]], [[ 0, 21],[ 4139, 23], [ 5008, 9], [ 5311, 14], [ 6278, 18], [ +6475, 4], [ 6649, 10], [ 8478, 19], [ 8581, 17], [ 8830, 2], [ 9122 +, 15], [ 9157, 13], [ 9698, 1], [10157, 22], [12321, 7], [12543, 6 +], [12658, 5], [12882, 0], [14151, 8], [14453, 11], [15624, 20], [ +15782, 12], [15921, 3], [17931, 16]], [[ 0, 22],*[ 2621, 13], [ 4374, 8], [ 5155, 4], [ 5170, 9], [ +5765, 3], [ 6168, 12], [ 6210, 5], [ 7147, 17], [ 8643, 14], [ 9326 +, 20], [10157, 21], [11223, 0], [11291, 19], [11293, 16], [13603, 1 +], [14265, 23], [14748, 2], [14987, 10], [15268, 11], [15447, 18], [ +16177, 6], [16782, 7], [18555, 15]], [[ 0, 23], [ 3419, 18], [ 3508, 10], [ 4139, 21], [ 5003, 15], [ +6655, 2], [ 7266, 1], [ 7729, 14], [ 8453, 19], [ 8550, 7], [ 8600 +, 6], [ 9146, 9], [10235, 4], [10326, 11], [10945, 17], [11078, 0 +], [12782, 13], [14138, 5], [14142, 16], [14265, 22], [14308, 20], [ +17749, 12], [18092, 8], [19675, 3]], ] [download] And consider the values for 84860: `84860 [ 0 1 10 15 7 6 11 16 20 5 12 3 8 22 13 9 4 14 17 19 2 18 21 23 +]` [download] We find that the 18-21 edge is ranked 8th. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l] [select]
Re^15: Travelling problem (Anyone better 86850?) by LanX (Saint) on Dec 28, 2013 at 14:26 UTC
The n shortest remaining edges�! You don't wanna visit a node again you've already seen. So it's not 8th cause the previous ones aren't possible anymore. - marks already excluded nodes ! marks target node `84860 [ 0 1 10 15 7 6 11 16 20 5 12 3 8 22 13 9 4 14 17 19 2 18 21 23 +] [ - [ 0, 18], - [ 3236, 2], ! [ 3419, 23], - [ 4874, 15], - [ 5593, 19], - [ 5954, 10], - [ 6102, 7], * [ 6278, 21], ... [ 6883, 14], [ 8377, 6], [ 9100, 11], [ 9181, 17], [ 9367, 1], [103 +07, 4], [10709, 9], [12822, 0], [12955, 16], [15242, 20], [15400, +13], [15447, 22], [15982, 8], [16868, 3], [17301, 5], [17968, 12] ],` [download] So it's effectively the shortest remaining possibility. Cheers Rolf ( addicted to the Perl Programming Language) �) successively take the shortest edge to a yet unvisited node	[reply] [d/l]
Re^13: Travelling problem (Anyone better 86850?) by LanX (Saint) on Dec 28, 2013 at 07:41 UTC
Something seems wrong, plz compare hdb's results taking 2 shortest edges: Re^5: Travelling problem (Anyone better 86850?) edit And keep in mind that the result for one shortest edge can't be better then yours for 6 ... Re: Travelling problem Cheers Rolf ( addicted to the Perl Programming Language)	[reply]

In Section Seekers of Perl Wisdom

edit