{"id":66,"date":"2020-01-16T15:16:59","date_gmt":"2020-01-16T04:46:59","guid":{"rendered":"http:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/?page_id=66"},"modified":"2020-01-16T15:17:11","modified_gmt":"2020-01-16T04:47:11","slug":"snakes-and-ladders-heuristic","status":"publish","type":"page","link":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/snakes-and-ladders-heuristic\/","title":{"rendered":"Snakes and Ladders Heuristic"},"content":{"rendered":"

[vc_row][vc_column][vc_empty_space][vc_column_text]<\/p>\n

Snakes and Ladders Heuristic<\/h1>\n

The Snakes and Ladders Heuristic (SLH) is a polynomial-complexity algorithm inspired by the famous Lin-Kernighan (L-K) heuristic for solving the Travelling Salesman Problem. Although it is not guaranteed to find a Hamiltonian cycle in a Hamiltonian graph, preliminary empirical experiments on many graphs (not exceeding 5000 vertices) have succeeded in all cases. Though it is well known that L-K-type algorithms can be used to solve instances of HCP (by casting them as a TSP), SLH differs from these approaches in several fundamental ways. First, the requirement of improvement at each iteration, which is central to L-K, is removed. Second, we use some transformations not generally used in L-K (as they violate conditions of L-K, but not of\u00a0SLH) that improve the efficiency of the heuristic. Third, a stopping rule is invoked if a maximum number (set to N3 in our implementation) of iterations have been performed without any improvement. Finally, SLH runs on any prescribed starting orientation, as opposed to L-K that relies heavily on repeated randomisations. These differences are elaborated on below.<\/p>\n

The name Snakes and Ladders Heuristic comes from our representation of the heuristic. Let C be a circle, and G be a simple\u00a0undirected graph containing N vertices. Then the vertices of G can be placed on C in some order, and all edges of G between adjacent vertices on C can be represented as arcs on C. A path of k connected edges of G that form a continuous arc on C is called a “k-snake”, and an isolated vertex on C is\u00a0considered to be\u00a0a 0-snake. The arrangement on C of all the k-snakes is called a “slither”.<\/p>\n

The edges that are not a part of the slither are represented as chords of the circle, which we call “ladders”. If the total number of edges forming all the k-snakes in a slither is less than N, then we say that the slither contains at least one “gap”. A Hamiltonian cycle then is simply a slither consisting of a single N-snake, or equivalently, a slither with 0 gaps. The aim of SLH is to construct a slither with 0 gaps by monotonically reducing the number of gaps, if possible, and opening additional gaps if improvement is otherwise impossible. If N3 iterations have passed without a reduction in the number of gaps, SLH terminates and reports that the graph is likely to be non-Hamiltonian.<\/p>\n

SLH has been implemented in C++. It has been tested on all 664 graphs listed on Gordon Royle’s Extended Foster’s Census list<\/a>, and successfully solved all graphs in under 3 minutes total running time.<\/p>\n

SLH succeeded in finding Hamiltonian cycles in the famously difficult Generalized Petersen Cubic Graphs<\/a>, of up to 1000 vertices, that contain only three such cycles.<\/p>\n

SLH has also been tested on all HCP instances from the University of Heidelberg’s TSPLIB<\/a> website, where examples range from 1000 – 5000 vertices, and has successfully solved all graphs. The largest of these was solved in under 1 minute. These time results were all obtained on a Dell Optiplex 990 laptop.<\/p>\n

Interested readers are encouraged to try the SLHWeb Interface<\/a> that allows users to submit their own graphs (in edge-list format) to SLH, and displays the solution process in real-time as an animation.<\/p>\n

[\/vc_column_text][vc_empty_space][\/vc_column][\/vc_row]<\/p>\n<\/div>","protected":false},"excerpt":{"rendered":"

[vc_row][vc_column][vc_empty_space][vc_column_text] Snakes and Ladders Heuristic The Snakes and Ladders Heuristic (SLH) is a polynomial-complexity algorithm inspired by the famous Lin-Kernighan (L-K) heuristic for solving the Travelling Salesman Problem. Although it is not guaranteed to find a Hamiltonian cycle in a Hamiltonian graph, preliminary empirical experiments on many graphs (not exceeding 5000 vertices) have succeeded in […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":63,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-66","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/pages\/66","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/comments?post=66"}],"version-history":[{"count":0,"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/pages\/66\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/pages\/63"}],"wp:attachment":[{"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/media?parent=66"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}