Ok, now for my first REAL entry. I've been looking the Hamiltonian Path problem, recently. For those of you who don't know, this is a really hard problem in Computer Science/Graph Theory. The problem is: "Given a graph, and two nodes, does there exist a Hamiltonian Path between those two nodes?" (A Hamiltonian Path is a path that travels to every single node, and never visits the same node twice.)
The naïve solution is pretty straight-forward:
import graph
def _naive_ham_helper(g, pts, dest):
# If we have used all points in the graph, but one, then the next
# hop had better be our destination.
if len(pts) == len(g.nodes())-1:
if dest in g.neighbors(pts[-1]):
return pts + [dest]
return None
# Else, we'll test every outgoing path, so long as we haven't tried
# it already, or it's the destination. (We aren't ready for it,
# yet...)
for i in g.neighbors(pts[-1]):
if i==dest or i in pts:
continue
p = _naive_ham_helper(g, pts+[i], dest)
if p:
return p
# Else, this branch didn't find anything. Tell the parent branch to
# keep looking.
return None
# The driver for the above function...
def naive_hamiltonian(g, start, dest):
return _naive_ham_helper(g, [start], dest)
This function pushes the first node, and then keeps recursively trying new paths, until we have reached the end, and used every node. For small graphs, this algorithm is ok, but when we start working with larger graphs (ie: in the hundreds to thousands of nodes...) this algorithm will be painfully slow.
We can do several things to try to get an answer quicker. First, we can make sure the graph is connected. If it is disconnected, then a Hamiltonian Path isn't possible. We can also scan the graph for nodes with degree 1 that aren't a starting/ending point. If one of those exist, then a Hamiltonian Path isn't possible. Also, if there is a connecting node (a node such that if it is removed, then the graph gets disconnected) and both the starting/ending points are on the same side of that point, then once again, the Hamiltonian Path isn't possible. While these steps may help to quickly find an impossible case, they don't actually speed up the search for a solution.
I've been tinkering with a purely heuristic algorithm, that is able to find a solution pretty reliably in many simple cases, but definitely not all. For example:
Where the path is trying to go from node 1 to node 2, the Naïve (read: correct) solution is bolded, and my dumb-ass algorithm is in blue. (Notice that it's forgetting to go to node 7...)
More on this later. This post is long enough, and I need to work on homework... :X