StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<h3>General notes</h3> <p>Dijkstra's algorithm and it optimised variant A* find the path with "the" minimal cost through your graph. The important things are a) defining your graph correctly and b) defining an appropriate cost function.</p> <p>In the face of a changing cost function Dijksta requires one to re-calculate the solution.</p> <p>For load-balancing I would extend Dikstra to not only calculate the optimal path, but use some kind of flood-fill behaviour to create a set of possible paths (sorted by cost) to find alternatives. Only knowledge about the specific problem and cost function can answer whether and how this might work.</p> <p><a href="http://www.scholarpedia.org/article/Ant_colony_optimization" rel="noreferrer">Ant Colony Optimisation</a> on the other hand seems to be much more flexible in adapting to a changing cost function, by continuing the iteration after/while the cost function changes.</p> <h3>Efficiency</h3> <p>This depends very much on your problem domain. If you have a good heuristic (see the <a href="http://en.wikipedia.org/wiki/A-star_algorithm#Complexity" rel="noreferrer">Complexity section of the A* article</a>) and seldom cost changes then A*'s polynomial runtime might favour repeated re-calculations. ACO on the other hand has to iterate over and over again before converging on an approximate solution. If cost changes occur very frequently, continuing the iteration at a constant rate might be more efficient than updating the A*-solution, since information is retained within the state of the algorithm. ACO doesn't promise <strong>the</strong> optimal solution, though and <strong>probably</strong> has higher start-up costs before converging onto a "good" solution. Again that very much depends on your specific domain, graph and cost function as well as your requirements on optimality.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload