[ACCEPTED]-What is the most efficient way of finding a path through a small world graph?-path-finding

General notes

Dijkstra's algorithm and it optimised variant 33 A* find the path with "the" minimal 32 cost through your graph. The important things 31 are a) defining your graph correctly and 30 b) defining an appropriate cost function.

In 29 the face of a changing cost function Dijksta 28 requires one to re-calculate the solution.

For 27 load-balancing I would extend Dikstra to 26 not only calculate the optimal path, but 25 use some kind of flood-fill behaviour to 24 create a set of possible paths (sorted by 23 cost) to find alternatives. Only knowledge 22 about the specific problem and cost function 21 can answer whether and how this might work.

Ant Colony Optimisation on 20 the other hand seems to be much more flexible 19 in adapting to a changing cost function, by 18 continuing the iteration after/while the 17 cost function changes.

Efficiency

This depends very 16 much on your problem domain. If you have 15 a good heuristic (see the Complexity section of the A* article) and seldom cost 14 changes then A*'s polynomial runtime might 13 favour repeated re-calculations. ACO on 12 the other hand has to iterate over and over 11 again before converging on an approximate 10 solution. If cost changes occur very frequently, continuing 9 the iteration at a constant rate might be 8 more efficient than updating the A*-solution, since 7 information is retained within the state 6 of the algorithm. ACO doesn't promise the optimal 5 solution, though and probably has higher start-up 4 costs before converging onto a "good" solution. Again 3 that very much depends on your specific 2 domain, graph and cost function as well 1 as your requirements on optimality.

With A*, the path cost does not need to 13 be constant, so you could start with the 12 following graph:

A---1---B---1---C
|               |
\-------1-------/

where we want to go from 11 A to C. Initially, the path finding algorithm 10 will choose the A-C path since A-B-C is 9 2 whereas A-C is 1. We can add an extra 8 term to the paths:

A---r---B---r---C
|               |
\-------r-------/

with

r(NM) = k(NM) + users(NM) / 10

where

r(NM) is the cost for a connection between N and M,
k(NM) is the constant cost for a connection between N and M,
users(NM) is the number of objects using the connection

As users are 7 added to the system, the route A-C will 6 become more expensive than A-B-C at twenty 5 users (1 + 20/10) = 3, A-B-C is 2. As users 4 are removed from the system, the A-C route 3 will become the best option again.

The real 2 power of the A* is the heuristic you use 1 to calculate the cost of each connection.

The most commonly used algorithm for this 8 problem is A* (A Star), which is a generalized Dijkstra's algorithm search 7 with added heuristics - the purpose of the 6 heuristics is to direct the search towards 5 the search goal so that typical searches 4 finish faster.

This algorithm has many variants, derived 3 versions and improvements, Google search 2 or the Wikipedia page should be a good starting 1 point.

Definitely A*. A* will either find the best 23 path possible or no path at all if no path 22 exists. E.g. the path of this boat has been 21 calculated using A*

_{(source: cokeandcode.com)}

Here's an interactive Java Demo to play 20 with. Please note that this algorithm is 19 slowed down by sleeps, so you see it performing. Without 18 this slow down it would find the path in 17 less than a second.

The algorithm is simple, yet 16 powerful. Each node has 3 values, g is the 15 cost up to this node. h is the estimated 14 cost from this node to the target and f 13 is the sum of both (it's a guess for the 12 full path). A* maintains two lists, the 11 Open and the Closed list. The Open list 10 contains all nodes that have not been explored 9 so far. The Closed list all nodes that have 8 been explored. A node counts as explored 7 if the algorithm has already tested every 6 node connected to this node (connected could 5 only mean horizontally and vertically, but 4 also diagonal if diagonal moves between 3 nodes are allowed).

The algorithm could be 2 described as

1. Let P be the starting point
2. Assign g, h, and f values to P
3. Add P to the open list (at this point P is the only node on that list).
4. Let B be the best node from the Open list (best == lowest f value)
   • If B is the goal node -> quit, you found the path
   • If the Open list is empty -> quit, no path exists
5. Let C be a valid node connected to B
   • Assign g, h, and f to C
   • Check if C is on the Open or Closed List
     • If yes, check whether new path is most efficient (lower f-value)
       • If so, update the path
     • Else add C to the Open List
   • Repeat step 5 for all nodes connected to B
6. Add B to the Closed list (we explored all neighbors)
7. Repeat from step 4.

Also have a look at Wikipedia for implementation 1 details.

Would a common Dijkstra's not be sufficient?

http://improve.dk/generic-dijkstras-algorithm/

0

I have heard of a NN implementation to handle 12 this kind of problem as well. So if you 11 want to use NNs you will eventually find 10 your way ;-) but they must be inferior in 9 comparison to "genetic algorithms".

If the 8 computational/time consumption is an issue, I 7 would highly suggest using genetic algorithms. This 6 is excactly the type of problems they are 5 exceptional at.

GAs are based on a function 4 that describes your satisfaction for any 3 given solution. You can modify this function 2 to suit your needs (ie. you can include 1 not only path cost but any factor you wish).

Dijkstras algorithm, small example for you

graph = {}

graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["finish"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["finish"] = 5
graph["finish"] = {}

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["finish"] = infinity
print "The weight of each node is: ", costs

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["finish"] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

node = find_lowest_cost_node(costs)
print "Start: the lowest cost node is", node, "with weight",\
    graph["start"]["{}".format(node)]

while node is not None:
    cost = costs[node]
    print "Continue execution ..."
    print "The weight of node {} is".format(node), cost
    neighbors = graph[node]
    if neighbors != {}:
        print "The node {} has neighbors:".format(node), neighbors
    else:
        print "It is finish, we have the answer: {}".format(cost)
    for neighbor in neighbors.keys():
        new_cost = cost + neighbors[neighbor]
        if costs[neighbor] > new_cost:
            costs[neighbor] = new_cost
            parents[neighbor] = node
    processed.append(node)
    print "This nodes we researched:", processed
    node = find_lowest_cost_node(costs)
    if node is not None:
        print "Look at the neighbor:", node

# to draw graph
import networkx
G = networkx.Graph()
G.add_nodes_from(graph)
G.add_edge("start", "a", weight=6)
G.add_edge("b", "a", weight=3)
G.add_edge("start", "b", weight=2)
G.add_edge("a", "finish", weight=1)
G.add_edge("b", "finish", weight=5)

import matplotlib.pyplot as plt
networkx.draw(G, with_labels=True)
plt.show()

print "But the shortest path is:", networkx.shortest_path(G, "start", "finish")

0