Anonymous user
Talk:Solve a Hidato puzzle: Difference between revisions
→Any good general algorithm?
Line 72:
== Any good general algorithm? ==
I added a larger example in the C code, which is meant to make brute force search miserable. The C code can solve it, but it takes quite long; I expect D to behave similarly. The Perl/Python/Tcl code should be able to solve it, if only taking forever, since they all use the same exhaustive search method (Tcl is forced into such a situation, but anyway). The Mathprog code gives up on it on my machine, rather quickly, which can be said to be the bright side. --[[User:Ledrug]]
:You do not indicate how glpk gives up on your machine, I am guessing numerical instability. Evil Case 2 makes the problem much larger. I have added examples of using Mathprog suitable for this large example. Note the model is the same, I just used a basis recommended for large multi indexed problems with a nested structure. In all three cases the solution then takes less than 1 second.--[[User:Nigel Galloway|Nigel Galloway]] 15:38, 4 May 2012 (UTC)
:: The earlier Mathprog code failed with something like "no possible solutions", without more explicit explanations. The current code still fails on the "evil 2" example, after about a gadzillion lines of instability warnings, then this:<lang>Error: unable to factorize the basis matrix (1)
Sorry, basis recovery procedure not implemented yet
glp_intopt: cannot solve LP relaxation</lang>
:: My glpsol version string is <code>GLPSOL: GLPK LP/MIP Solver, v4.45</code>, which might be why it doesn't have <code>--minisat</code>. Examples were run without it, not sure if that switch was crucial or not. --[[User:Ledrug|Ledrug]] 19:53, 4 May 2012 (UTC)
Note that that example is trivial for a human. Does anyone have any clever way to deal with such cases? --[[User:Ledrug|Ledrug]] 00:59, 3 May 2012 (UTC)
| |||