Menu

#52 suvorov too slow

0.41
open
nobody
None
5
2013-12-16
2013-10-13
No

I thinking pruning bad solns earlier may speed things up.
Tsukamoto has only 10% success rate

Discussion

  • Jeremy Carroll

    Jeremy Carroll - 2013-10-16

    I have added some pruning by looking for unnecessary connections at vertices and blocking edges with two unnecessary connections early.

    Also need to block:

    • single vertex where all its edges have unnecessary connections
    • two vertices joined by a necessary link but where all other edges are unnecessary
    • could also precompute all sixes and block any extension of one of those
    • could also for each edge, and vertex and pair of vertices in the original graph do a precompute search for first solution, if none, then remove edge, vertex, or vertex-pair from search space.
     
  • Jeremy Carroll

    Jeremy Carroll - 2013-12-16
    • Group: 0.4 --> 0.41
     

Log in to post a comment.