Talk:Superpermutation minimisation: Difference between revisions

Content added Content deleted

Inline

Revision as of 13:46, 13 December 2014

N. Johnston's algorithm

Hi Paddy3118,

The referenced work by N. Johnston proposes an algorithm which produces strings of length sum over k=1 to n of k!. None of the Python or D solutions produce such a good result. Would it be better if the task was to implement N. Johnston's algorithm, outputting the first 5 results, and noting that after 5 shorter strings probably exist? I am surprised that you have placed so much emphasis on timings here, given that you are so quick to complain when someone who thinks a timing says something about a solution does so. (Given that I don't think these timings mean much).--Nigel Galloway (talk) 12:21, 12 December 2014 (UTC)

Hi Nigel, I decided to write the task as a means of comparing heuristics. I needed several heuristics and a weighting scheme to compare them.

N. Johnston's paper wasn't one of my early references, (indeed I have lost the reference that gave me s_perm0 - my first algorithm). Maybe either I or someone else will add that algorithm to the Python entry in the future? --Paddy3118 (talk) 15:06, 12 December 2014 (UTC)

Ambiguous

Task, as currently specified, is ambiguous. That the underlying problem may or may not be NP Complete is a part of this. --Rdm (talk) 04:51, 13 December 2014 (UTC)

Please expand. Ambiguous in what way? --Paddy3118 (talk) 06:24, 13 December 2014 (UTC)

The problem is NP Complete. The value of 872 for 6 is found by writing the problem as a TSP and using specialized TSP solvers. TSPs are NP Complete and very very very really hard to prove minimal solutions. Perhaps the ambiguity is with the tasks title, none of the algorithms used by D or Python produce minimal strings beyond 3. The C entry is new and produce results consistent with N. Johnson's algorithm (minimal to 5). I havn't checked if it is actually N. Johnson's algorithm. As above I don't understand the value of timing algorithms which do not do the same thing. Comparing C's value for 10 (4037913) and D's value (4_235_533) tell's me which algorithm is best. That D can do it in less than 9 secs mmm! --Nigel Galloway (talk) 13:46, 13 December 2014 (UTC)

@@ Line 12: / Line 12: @@
 Task, as currently specified, is ambiguous. That the underlying problem may or may not be NP Complete is a part of this.  --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 04:51, 13 December 2014 (UTC)
 :Please expand. Ambiguous in what way? --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 06:24, 13 December 2014 (UTC)
+:The problem is NP Complete. The value of 872 for 6 is found by writing the problem as a TSP and using specialized TSP solvers. TSPs are NP Complete and very very very really hard to prove minimal solutions. Perhaps the ambiguity is with the tasks title, none of the algorithms used by D or Python produce minimal strings beyond 3. The C entry is new and produce results consistent with N. Johnson's algorithm (minimal to 5). I havn't checked if it is actually N. Johnson's algorithm. As above I don't understand the value of timing algorithms which do not do the same thing. Comparing C's value for 10 (4037913) and D's value (4_235_533) tell's me which algorithm is best. That D can do it in less than 9 secs mmm! --[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 13:46, 13 December 2014 (UTC)