1
$\begingroup$
  • I am familiar with mathematical (gradient-based) optimisation methods, some heuristic methods like GAs or linear programming methods like simplex algorithm.
  • I am not too familiar with graphs / trees and their search.
  • But it does seem like all possible solutions can be represented as a graph and a graph search algorithm can then be used to explore the space and determine the "shortest" (or could be some other criterion) path. It seems that this is what Breadth First Searcha and Dijkatra algorithm are doing. Is this correct? Is tree search actually linked to a more general concept of optimisation?
$\endgroup$
  • 1
    $\begingroup$ What do you precisely mean by 'optimisation'? As far as I'm aware, simply maximising any function can already be called optimisation, but you seem to use it differently. Also, does your third point ask whether BFS or Dijkstra can be thought of as some search over neighbours in a solution space? $\endgroup$ – Discrete lizard Dec 28 '17 at 11:30
  • $\begingroup$ Additionally, Dijkstra can be done over a general graph. What do you mean by 'tree search'? $\endgroup$ – Discrete lizard Dec 28 '17 at 12:17
  • $\begingroup$ @Discrete Lizard I would call optimisation any process of find a single argument from a domain (discrete or continuous) of arguments that gives the maximum/minimum in the codomain (so essientially yes -- a min/max of any function). $\endgroup$ – A.L. Verminburger Dec 28 '17 at 14:12
2
$\begingroup$

Although I'm not sure what you're calling 'optimisation', I can tell you that both Dijkstra's algorithm and BFS are not some form of searching a solution space. If they were, they would start with an initial solution, i.e. some path from A to B, and eventually find the shortest path between A and B after considering multiple such paths. But this is not the case, as these algorithms both construct partial solutions before eventually getting a complete solution.

On other hand, it is true that locally, the distance to some node is at first estimated by some path and possibly later improved, so there is some similarity here. However, the incremental approach to a solution is an important aspect in these algorithms, which doesn't occur in gradient-based optimisation, as these cases usually don't even have a concept of a partial solution which can be extended into a full solution.

$\endgroup$
  • $\begingroup$ OK, so essentially, yes it is optimisation, but we build up the solution gradually, rather than trying a bunch of complete solutions until we find the right one. $\endgroup$ – A.L. Verminburger Dec 28 '17 at 14:13
  • $\begingroup$ Indeed, this is optimisation, but the techniques to get a solution differ a lot from the techniques you're familiar with. $\endgroup$ – Discrete lizard Dec 28 '17 at 14:46

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.