Lookahead Algorithm In Python

I have a network (a graph) of 50 vertices and 70 edges. I grow this network iteratively by adding an edge between the two vertices for which a new edge improves a given fitness met

Solution 1:

If you're having trouble wrapping your head around the problem, you need to break it into smaller steps.

Think about what you're trying to acheive:

I am trying to implement a search algorithm in order to find the network's best combination of iterative changes by looking ahead n steps into the futures

And what your inputs to the system are:

• initial graph
• number of iterations n (lets say we choose 3)
• ranking function that determines fitness of a graph (or perhaps relative improvement over a previous graph)

So we need to write a function that takes these inputs and returns a new graph with the optimal edge added.

defadd_optimal_edge(graph, rank, n=1): # you don't need to pass in the rank function necessarily
    ...

Now what does this function do? Well for each future generation it has to iterate over every possible new edge, create a new graph with this edge added and compare the new graph to the old one (basically what you're already doing).

But how does it determine which edge is optimal? Well for each new edge it has to look at the new graph and iterate over all possible new edges and create new graphs for those and then iterate over all possible new edges and new graphs for those .. etc .. .and then compare each final graph to the original - selecting the optimal first step, based on the ranking of the original graph to the final generation. phew

We want some code that does something like:

for generation in range(n):
    new_graphs = (graph.add_edge(e) for e in graph.possible_new_edges())

But subsequent generations will need to do this over a list of graphs (not a single one), so perhaps start out with a list and work from there:

graphs = [graph] # start off with just one graph
for generation inrange(n):
    graphs = (graph.add_edge(e) for graph in graphs for e in graph.possible_new_edges())

This uses generator comprehensions so that memory usage doesn't balloon out of control, and it keeps overwriting graphs so that each subsequent generation is iterating over a larger set. Then compare each graph to the original and find the best:

best = max(graphs, key=lambda g: rank(graph, g)) # select best graph by ranking it against original

Okay, we've found the best, but we need to know what the first generation was that led us to get there. One way to do that would be to track the path of previous graphs as we go instead of just the latest graph, so the items we're iterating over are now lists of graphs (a path)

defadd_optimal_edge(graph, rank, n=1):
    paths = [[graph]] # start off with just one graph path, which contains a single graphfor generation inrange(n):
        # path[-1] is the latest graph for each generation
        paths = (path + path[-1].add_edge(e) for path in paths for e in path[-1].possible_new_edges())
    # select best path by comparison of final generation against original graph
    best = max(paths, lambda path: rank(graph, path[-1])) 
    return best[1] # returns the first generation graph

The final result is concise, but the inner generator comprehension is a little long winded - you could probably refactor this out to a generator function to make it more readable. If you fill in the details for the extra functions I've added, you should be well on your way to a solution.