Finding a Hamiltonian Path Efficiently - ADVANCED

[stauffski]

Hello Fellow Code Ninjas,

Working on a humdinger here. I'm getting stuck trying to come up with a solution to finding a Hamiltonian Path. I managed to solve it recursively but the time complexity or the time cost of recursion makes the solution unviable. I've found a few resources online, but I am having trouble telling if the topic is over my head or the resources are poorly assembled.

First, I'll give you my working recursive code so you can get an idea of what I'm doing:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89

import cProfile import io import pstats import sys   sys.setrecursionlimit(10 ** 6)  # this is a recursive solution that creates n stacks for solve(n), raise the ceiling     # decorator for you to profile my code with def profile(function):     def inner(*args, **kwargs):         profiler = cProfile.Profile()           profiler.enable()         returnValue = function(*args, **kwargs)         profiler.disable()           stream_ = io.StringIO()         pstats.Stats(profiler, stream=stream_).sort_stats('cumulative').print_stats()         print(stream_.getvalue())           return returnValue       return inner     def solve(n):  # this function runs all the code and returns a hamiltonian path     return findHamiltonianPath(getSquareSumsGraph(n))     # generate undirected graph of numbers in a range # connect all vertices v1 and v2 that sum to a perfect square, where sqrt(v1 + v2) = an integer # example: given 6 and 10, sqrt(6 + 10) = 4, therefore connect vertex(6) to vertex(10) def getSquareSumsGraph(n):     squares = {x for x in range(4, 2 * n) if (x ** (1 / 2)).is_integer()}  # generate perfect squares in range 2n     graph = {}  # initialize an empty dictionary       for vertex in range(1, n + 1):  # iterate the range 1 -> n, each is a vertex (v1)         subVertices = []  # this empty array will represent the vertices connected to vertex         for square in squares:  # iterate the pre-calculated squares             candidate = square - vertex  # since v1 + v2 (candidate) = square; v2 = square - v1             if 0 < candidate <= n and candidate != vertex:  # confirm that candidate exists in the range and != v1                 subVertices.append(candidate)  # keep candidate (v2)         graph[vertex] = subVertices  # all vertices connected to vertex have been collected, store them in the graph       return graph     # return the first hamiltonian path found in the graph # if no path found, return False def findHamiltonianPath(graph):     graphLength = len(graph)  # store the graph length for optimization     subGraph = graph.copy()  # copy the graph. subGraph will be used to add and remove connections as we iterate     path = []  # path will store our final result       # recursive child function handles searching for the path     def search(options):         if len(path) == graphLength:  # if path and graph are the same length, Hamiltonian Path has been found             return path  # return the Hamiltonian Path         options = sorted(options, key=lambda option: len(graph[option]))  # sort by shortest subVertices - optimization         for option in options:  # iterate all the options. we are starting with the vertices that have the least options             path.append(option)  # add the option to the path             for vertex in graph[option]:  # now that option is in the path, remove it from connected subVertices                 subGraph[vertex].remove(option)             if search(subGraph[option]):  # recurse from the next vertex of position option                 return path  # a member of the stack has found a path, return the path             path.pop()  # path was not found with that option, remove it from the path             for vertex in graph[option]:  # put the option back in all the subVertices it should be connected to                 subGraph[vertex].append(option)         return False  # no path was found, return False       return search([*range(1, graphLength + 1)])  # seed the search with the full range of options     @profile def rangeTest(a, b):     for n in range(a, b):  # iterate this solution for a -> n         path = solve(n)  # find Hamiltonian Path for n         print(f'N = {n}: Path = {path}')  # print n and path   @profile def singleTest(n):     path = solve(n)  # find Hamiltonian Path for n     print(f'N = {n}: Path = {path}')  # print n and path     singleTest(15)  # this is the smallest n that has a hamiltonian path, use this test to debug and walk through the code singleTest(1000)  # this test would fall without the recursion ceiling extension rangeTest(100, 300)  # this test needs to complete in at least 20% less time than it currently does

The commenting is extremely verbose, so read that to follow what's going on. In summary: We are testing findHamiltonianPath() by sending it an undirected graph that associates all the numbers in the range 1->n that sum to a perfect square. More on the square sums problem: Square Sums Problem

My code works flawlessly (I think) to solve the problem, but the issue I'm having is the amount of time it takes. Now, there are many very inefficient ways to solve this problem, but this is not one of those. However, I know for sure that there is a way to make the solution faster either by optimization or a complete rewrite (maybe a dynamic solution?). Problem is, there's a ton of resources talking about really slow solutions (not this one) and only a small handful of resources that even acknowledge the problem can be solved faster.

Now, I only need to improve the speed of the program by about 20%, but I've already profiled my code and optimized everything I can think of. Granted, I'm very new at Python so perhaps one of you Gurus can point me in the right direction. Alternatively, if anyone can link me to a good resource that talks about a dynamic solution, that would be awesome. The only dynamic solution that I've found so far is this (and it's despicably slow): Dynamic Programming - Hamiltonian Path

The dynamic solution is presented in section 2.) when you scroll down. The code is in C++ but I translated it to Python. It's been many years since I've worked in C++ and being new to Python, I would not be shocked if I made a translation error. That said, here's my translation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

# Note: This code only returns True or False. I'll implement the rest if I can get it to work faster def checkHamiltonian(adj, n):     dp = [[False for i in range(1 << n)] for j in range(n)]     for i in range(n):         dp[i][1 << i] = True     for i in range(2 ** n):         for j in range(n):             if i & (1 << j):                 for k in range(n):                     if i & (1 << k) and adj[k][j] and k != j and dp[k][i ^ (1 << j)]:                         dp[j][i] = True                         break     for i in range(n):         if dp[i][(2 ** n) - 1]:             return True     return False

A couple of issues I'm running into with that code:
The author does not talk about the parameter requirements for the function, which I find odd. So

• I'm not sure if I'm implementing it correctly. I'm assuming that adj is supposed to be an adjacency matrix and n is the length of the path you're trying to find. I could be wrong.
  
• It seems like the author's first language is not English, so I can't tell if I'm having trouble understanding what he is saying or if it's just over my head.
  

In any case, since I don't entirely understand the dynamic solution yet, I'm not sure how or if I can optimize it.

Here's a translation of my own code to create an adjacency matrix to test the dynamic solution with instead of the graph:

1 2 3 4 5 6 7 8 9 10 11

def getSquareSumsAdjacencyMatrix(n):     squares = {x for x in range(4, 2 * n) if (x ** (1 / 2)).is_integer()}     adjacencyMatrix = [[0 for i in range(n)] for j in range(n)]       for vertex in range(1, n + 1):         for square in squares:             candidate = square - vertex             if 0 < candidate <= n and candidate != vertex:                 adjacencyMatrix[vertex - 1][candidate - 1] = True       return adjacencyMatrix

Alright guys, fingers crossed that someone can help me. The question is two-fold. Either help me optimize my code or understand/fix/find the/a dynamic solution. Also, feel free to make any corrections on the way that I use Python or propper conventions. As I said I'm new and would love to learn whatever you have to offer.

Cheers
~Stauffski

Note: precalculating the answer is not an option

[ndc85430]

Also posted here.

[stauffski]

Also posted here.

Yes... I posted the same question on two forums.

[stauffski]

Update: My code was running fast enough. Turns out I was encountering a slowdown at fault of the server. Therefore now I no longer need help. However! I would still love anybody's input on any of the three points:

• Further optimization of my code
  
• A faster dynamic solution
  
• Corrections on my usage of Python
  

Cheers!