1
$\begingroup$

Which algorithms, between ant colony or classical routing algorithms, have a better time complexity for the shortest path problem?

In general, can we compare efficiency of these two types of algorithm for the shortest path problem in a graph?

$\endgroup$
1
$\begingroup$

No. In general, you can't find a tight bound for evolutionary algorithms, and it is one of the main difference of these algorithms with the classical algorithms.

You should notice that it does not mean you can't find when the evolutionary algorithms are finished! But, you can't find a tight bound for the algorithms time complexity to reach to the optimal solution or how much that solution is near to the optimal solution (in contrast to the approximation algorithms).

$\endgroup$
  • $\begingroup$ Thank you. So what is your opinion about this article: (link), where authors have calculated the time complexity of ACO algorithms? Please see table_1 (page 5). Btw, could you please say that what is the reason of impossibility of finding a tight bound for evolutionary or swarm intelligence algorithms? And if so, how to evaluate this type of algorithms? Thank you $\endgroup$ – Questioner Jan 8 at 11:25
  • $\begingroup$ @sas see the updated answer. $\endgroup$ – OmG Jan 8 at 11:56
  • $\begingroup$ Thank you. So do you mean that we need to run the algorithm and then calculate the running time instead of calculate time complexity mathematically? Am I right now? Thanks. $\endgroup$ – Questioner Jan 8 at 12:00
  • 1
    $\begingroup$ @sas Yes. it depends on the setting of that algorithm and you can't find in it theoretically. $\endgroup$ – OmG Jan 8 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.