I don't use Python very often - so my broader knowledge is lacking - but I think this deserves a proper answer none-the-less!
Efficiency
You haven't explicitly asked about efficiency, but if you need A* then you probably care about it, and there is plenty to be said. I'm starting with it because it influences some decisions I'll make later on about other stuff
Frontier search
As Rejith Raghavan indicates, you currently keeping the frontier nodes in a data-structure without any information about their cost, and the g_h
method is expected to find the node with the smallest heuristic, which is does by effectively flattening it. There are a couple of inefficiencies here:
You are recalculating the path-cost and heuristic cost of each frontier node every time step. Your path_cost
method is a very expensive non-constant time operation! As a simple rule of thumb, sqrt
is slow, and any trig function requires a sqrt
. If you are deep into the search, the path lengths will become steadily longer. Recommendation: store the path cost and its sum with the heuristic cost in a data-structure, so you only have to compute it once. An added benefit is that when you create/update a node with the next segment, you need only compute the cost of that segment, and add it to the existing cost (and then add on the new heuristic).
Finding the 'smallest' element in an unsorted list is a linear-time cost (if the list has n
elements, you have to look at all n
of them to find the smallest). Using a priority queue of some sort (e.g. a Heap) will reduce this to a logarithmic lookup. This would require rethinking how you store the frontier, and implementing the above suggestion of storing the costs. More advanced priority queues (with update
methods) will allows you to effectively preserve your system of keeping the best route to each known node, but I'm afraid I don't know if there are any options built into Python. Unless memory is severely limited, you will probably benefit even by having a growing heap of 'dead' nodes (which can be detected by re-purposing your explored
set to check if explore
is in explored
at the start of the while loop).
g_h
(which is a terrible name) itself isn't very efficient, as it constructs a whole new dictionary, and then interrogates that, rather than performing a simple enumeration and pulling out the smallest entry. This won't, however, significantly effect your time-complexity (unless you are unlikely with your hash functions, in which case it could), so perhaps go for readability rather than racing speed here (hopefully some of the changes below will make it more readable).
cleanse_frontier
This method is quite horrifying... Basically, it looks for nodes which have already been expanded. Much better, would be to simply keep a dictionary that maps a node to a cost, and maintain this cost as the smallest recognised for that node (no entry implies it hasn't been seen yet). Then, when you add a node to a frontier, just check that the cost of the candidate is less than the recorded cost, and if it isn't, don't record the new candidate. This would replace the (broken) i not in frontier.keys()|explored
check, which currently rejects candidates where a (potentially worse) candidate is already given: I've not run your code, but I don't think it is a correct implementation of A* for this reason.
Path List
I would be inclined to switch your lists of segments from a conventional list to an immutable linked list. Unless I have forgotten everything about Python, I think [stuff]+[stuff]
will result in the allocation of a new contiguous list. This means that every time you create a new path, you are allocating more memory and performing a copy. An immutable linked list (e.g. as found in 'functional' languages) would allow you to more efficiently represent what is really an upside down 'tree' of paths, without the cost of copying the whole path for every new frontier path. I'm not sure what options you might have for this, and I wouldn't worry about this too much.
Points
You are currently storing the path to a frontier node as a list of indexes into a table of lists of coordinates.
You are currently storing your intersection locations as lists. Your code explicitly supports having exactly 2 coordinates (x
, y
), but this isn't conveyed anywhere in your code. I could try to feed your program 3 coordinates (x
, y
, z
), and it would run just fine, only it wouldn't be using the third coordinate and I would be completely unaware. You expect a coordinate pair, so require a coordinate pair: use a class with explicit x
and y
attributes, and give it a sensible name:
class Point:
def __init__(self, x, y):
this.X = x
this.Y = y
_(You'll have to forgive any syntax aberrations, or failure to adhere to conventions: I thankfully don't have to use Python much these days. If anyone feels like tidying my code up for the common good, I'd welcome it)
This will turn this line:
((M[path[i]][0]-M[path[i+1]][0])**2+(M[path[i]][1]-M[path[i+1]][1])**2)**0.5
Into this:
((M[path[i]].X-M[path[i+1]].X)**2+(M[path[i]].Y-M[path[i+1]].Y)**2)**0.5
Effectively the same piece of code appears twice (once in heuristic(,,)
and once in path_cost(,,)
. It is a classic exploitation of Pythagoras's theorem, which everyone happens to know we use for computing line distances in Euclidean space. But your code doesn't say any of this (granted, there is a comment above expressing the intent, which is good), it is just some maths which we hope has brackets in the right places.
Now that we have a Point
class, it doesn't seem unreasonable to add a method to compute the distance between two points.
def DistanceTo(self, other):
squareDistance = (self.X - other.X)**2 + (self.Y - other.Y)**2
return quareDistance**0.5
This means we can rewrite heuristic(,,)
thus:
# Euclidean Heuristic from the node to the goal node
def heuristic(node, goal, M):
return M.intersections[node].DistanceTo(M.intersections[goal])
A similar change can be made in path_cost
. You'll note that I have renamed your parameters, and removed the M=M.intersections
call. Your function is mathematically symmetric, but anyone calling the method will have no clue what p1
and p2
mean (which is the goal?). You seem to do a lot of M=M.intersections
, presumably to avoid cluttering code with long attribute names. Now that we have the DistanceTo
method, the line is much easier to read, and there is no need for a shorter name. Even if a shorter name was warranted, reassigning M
is misleading (it took me completely by surprise), and I would avoid doing this.
By using a Point
class, you'd need to update the code to build the Map
. I'm afraid I don't understand what it is currently doing, so I can't advise how to do that.
Paths
You are storing your paths as lists also. Above I suggested you record the costs of the path along with the path itself (in the interests of efficiency).
class Path:
def init(self, pathSegments, pathCost, heuristicCost):
this.PathSegments = pathSegments
this.PathCost = pathCost
this.HeuristicCost = pathCost + heuristicCost
This will make it much more obvious what your frontier
dictionary is recording.
Misc
I won't discuss the exposed API, because I don't understand Python's module system, but some sort of documentation is warranted (e.g. to describe the shape of G
(which needs a better name (graph
?) before building a Map
(what type is "pos"
?)). Ideally only the shortest_path
function and any public types (Map
, Point
, and perhaps Path
) would be exposed, as the other methods are all implementation details.
You are inconsistent with your padding of function parameters with spaces (e.g. shortest_path(M, start, goal):
vs. path_cost(path,M,cost=0):#
). I don't know what the conventions are in Python, but you should be consistent. personally, I would always pad definitions and calls: it helps to break up the arguments, making the code easier to scan. I'd also put a space before any end-of-line comments, and I'd add a couple of line-breaks in to break up dense methods a bit. Some more spaces in dense expressions would also be appreciated.
I completely missed the return condition when skimming shortest_code
. Move the return onto a new line. You don't have a return statement for when the search fails (there is no path). This might be OK, but I'd prefer an explicit acknowledgement. I would much prefer, also, an explicit if goal == start:
statement. Currently that check is hidden off the right of the screen beside a nasty looking list-comprehension, uses the horrible ternary if, and it is less than clear how the check is meant to work, all of which makes it a maintenance concern.
The return in cleanse_frontier
is redundant, because it modifies the dictionary passed to it. This creates a confusing API, as it implies that it will be returning a modified clone of the parameter.
I've mentioned naming throughout this, so I'll just say here that naming is really important if you want maintainability.