2
$\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 Answer 1

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$
4
  • $\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, 2019 at 11:25
  • $\begingroup$ @sas see the updated answer. $\endgroup$
    – OmG
    Jan 8, 2019 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, 2019 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, 2019 at 12:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .