2

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?

nbro
  • 39,006
  • 12
  • 98
  • 176
Questioner
  • 283
  • 1
  • 10

1 Answers1

1

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).

OmG
  • 1,731
  • 10
  • 19
  • Thank you. So what is your opinion about this article: ([link](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.720.9953&rep=rep1&type=pdf)), 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 – Questioner Jan 08 '19 at 11:25
  • @sas see the updated answer. – OmG Jan 08 '19 at 11:56
  • 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. – Questioner Jan 08 '19 at 12:00
  • 1
    @sas Yes. it depends on the setting of that algorithm and you can't find in it theoretically. – OmG Jan 08 '19 at 12:07