The strategy used leads to good results but has a problem to tackle large N problems, this is because the A* is not so effective for large N, you could have tried to use a 'weight_cost = lambda a: 1' that leads to sub-optimal solutions but can compute larger N in a reasonable amount of time.
The README is very well detailed and exhaustive, the only thing i would say is that since you used 2 different algorithms, inserting the results of the greedy could have lead to a more simple comparison between the 2 algorithms.
The code is not commented at all, even though the README was very exhaustive i would have liked more details in the code on which do what and why.
Minor Issues
I would have liked to know how actual time (milliseconds/seconds) your algorithm would have taken, for both the algorithms in order to understand if one solution was faster then other
General Comments
Minor Issues