DIR Return Create A Forum - Home
---------------------------------------------------------
knight tours
HTML https://knighttours.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: general Hamiltonian cycles problem
*****************************************************
#Post#: 7--------------------------------------------------
testing HCP-solvers , challenges, competitions
By: gsgs Date: March 6, 2023, 2:56 am
---------------------------------------------------------
graph libraries, repositories
HTML https://arxiv.org/pdf/2006.12741
A survey of repositories in graph theory
TSPLIB,FHCP,McKay,Royle,G&G,Foster,DIMACS
FHCP , 1001 Hamilton-difficult graphs :
HTML https://sites.flinders.edu.au/flinders-hamiltonian-cycle-project/fhcp-challenge-set/
programs
HTML https://arxiv.org/pdf/2208.02153
HTML https://downloads.hindawi.com/journals/jopti/2018/9328103.pdf
concorde
hybridham
snake and ladder
linkern
warnsdorf
Helsgaun’s LKH
HTML http://webhotel4.ruc.dk/~keld/research/LKH/
--------------------------
fascinating, the only known really hard Hamiltonian cycle
instances are these
naturally occurring graphs made from Stedman and Erin triples
derived from an old church-bell-ringing problem , 1700s , first
paper in 1886
HTML https://arxiv.org/pdf/1702.02623
What is Change Ringing?
HTML https://www.ringing.org/change-ringing/
#Post#: 8--------------------------------------------------
Re: testing HCP-solvers , challenges, competitions
By: gsgs Date: March 7, 2023, 1:28 pm
---------------------------------------------------------
how does the Warnsdorf rule compare to modern solvers ?
It is rarely mentioned in the papers about modern approaches,
except maybe, when it's especially about knight tours.
1.) normal, original Warnsdorf rule, starting at a vertex of
minimal degree.
When there are several equal possibilities, choose the first
one.
2.) same as 1.) , but choose the last one
3.) proceed from both ends of the partially finished tour.
At each step choose the end with fewest free neighbors
and go to the one which itself has the fewest free neighbors.
Take the first vertex, if there are equal choices.
4.) join paths.
Start with all vertices as paths of length 1.
At each step choose the path and the end with the fewest
free neighbors (=path-ends)
and join it with the one which itself has the fewest free
neighbors
Take the first vertex, if there are equal choices.
In the first 250 instances of the FHCP-challenge set :
{HP = Hamiltonian path , HC=Hamiltonian cycle}
1.) finds 0 HPs and 0 HCs in 40s
2.) finds 3 HPs and 0 HCs in 40s
3.) finds 54 HPs and 11 HCs in 53s (surprisingly good !)
4.) finds 34 HPs and 11 HCs in 122s
10 randomized runs of 3.) gave 175 different HPs and 16
different HCs in 13min
10 randomized runs of 4.) gave 162 different HPs and 19
different HCs in 30min
to compare :
"unbounded heuristics" finds 43 HPs and 88 HCs in ~500s
"fast unbounded heuristics" finds 120 HPs and 11 HCs in ~ 5s
"HybridHAM" finds 62 HPs and 13 HCs in ~20min
graphs as TSP : distance = 1-adjacency-matrix
"linkern" finds 102 HPs and 5 HCs in 20min
"concorde -B" finds 126 HPs and 23 HCs in 100min
manually interrupted on 74,87,109,145,179,227,242
concorde with default parameters was just too slow here
-B means : don't branch"
graphs as TSP : distance = length of shortest path
linkern finds 112 HPs and 17 HCs in 20min
concorde -B finds 146 HPs and 53 HCs in 100min
manually interrupted on #74,87,173,199,224,226,250
*****************************************************