- 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?
$\begingroup$
$\endgroup$
3
-
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 ♦Commented Dec 28, 2017 at 11:30
-
$\begingroup$ Additionally, Dijkstra can be done over a general graph. What do you mean by 'tree search'? $\endgroup$– Discrete lizard ♦Commented Dec 28, 2017 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. VerminburgerCommented Dec 28, 2017 at 14:12
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Dec 28, 2017 at 12:20
-
$\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$ Commented Dec 28, 2017 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 ♦Commented Dec 28, 2017 at 14:46