4 ms·

> It's not Dijkstra's algorithm in disguise - it's not any kind of search. It's a kind of superficial statement to make: "this is not that". Obviously these th

> It's not Dijkstra's algorithm in disguise - it's not any kind of search. It's a kind of superficial statement to make: "this is not that". Obviously these things are different on the surface, but probing a bit deeper can sometimes bring similarities out. This is more interesting to me, although perhaps I am just getting old and too many neurons are interconnected and this is what makes me seek the similarities between things, instead of just saying "this is not that". As has been noted by arghbleargh [0], the simplex method can be used to implement Dijkstra. How sure are you that the converse is not also true? Will you at least admit this is an interesting question? Or even the question of how to ask this question in such a way that it is provable/disprovable. I think this is worthwile. Continuing to probe: Dijkstra (and dynamic programming, etc.) hinges crucially on the idea of a semiring, or generalized distributivity [1], [2]. In the case of a minimum weight path this boils down to noticing that a+max(b, c) = max(a+b, a+c). The plus distributes over the max (think of the usual distributivity: a(b+c)=ab+a*c). Convexity also has a kind of distributivity, which can be most easily seen by taking averages: a+(b+c)/2 = (a+b)/2 + (a+c)/2. So addition distributes additively over "averages". And this formula extends to arbitrary convex combinations. My spider sense is telling me that something interesting is going on here, and there may be some more ways to link linear programming up with dynamic programming. [0] https://news.ycombinator.com/item?id=11845375 https://news.ycombinator.com/item?id=11845375 [1] Aji, Srinivas M., and Robert J. McEliece. "The generalized distributive law." Information Theory, IEEE Transactions on 46, no. 2 (2000): 325-343. [2] Gondran, Michel, and Michel Minoux. Graphs, dioids and semirings: new models and algorithms. Vol. 41. Springer Science & Business Media, 2008.

DannyBee 10y ago
"How sure are you that the converse is not also true? Will you at least admit this is an interesting question? Or even the question of how to ask this question in such a way that it is provable/disprovable. I think this is worthwile." It's an interesting question, but one which has a sad answer: integer linear programming (and other restricted forms, such as 0-1 programming) are NP-Hard. If you could use dijkstra's algorithm to solve them, in less than exponential time, you will have proved P=NP. So i would go with "pretty sure". (now, could you do it in exponential number of dijkstra invocations? Maybe? But that is, to me, not an interesting question :P Same with could you expand the linear programming problem into an exponential size graph that was then solvable by dijkstra's algorithm - we already know that expspace is a superset of p, etc)
ColinWright 10y ago
>> It's not Dijkstra's algorithm in disguise >> - it's not any kind of search. > It's a kind of superficial statement to make: > "this is not that". Obviously these things > are different on the surface, but probing a > bit deeper can sometimes bring similarities > out. Agreed, although I was trying to answer the question as asked, and not start writing an entire essay on how instances of one type can be encoded as instances of another. MineSweeper is NP-Complete, so we can encode Hamilton Cycle (for example) in it. MineSweeper is not an instance of Hamilton Cycle, they can each be encoded in the other, this is deeply interesting, but it doesn't help someone trying to get to grips with what the Simplex Method "is". Coming to understand what it "is" is the gateway to seeing how it might, or might not, then be used to encode, and solve, other problems. > This is more interesting to me, although > perhaps I am just getting old and too many > neurons are interconnected and this is what > makes me seek the similarities between things, > instead of just saying "this is not that". I'm 55, and finding deep connections is (part of) what I do. Understanding that some things are genuinely different is, to me, an important place to start. > ... the simplex method can be used to > implement Dijkstra. How sure are you > that the converse is not also true? I'm pretty sure Dijkstra can be used to solve instances of Linear Programming, although the encoding is likely to be exponential. It might then be simplified by using the specific characteristics of linearity, etc, but that's not the same as saying that it is an instance of LP. > Will you at least admit this is an > interesting question? Absolutely - I'm not even forced to "admit" this sort of thing. It's what I spend much of my time trying to convince other people about. But Dijkstra is not the Simplex Method in disguise, not vice versa. Perfectly happy to say that each could (perhaps) be encoded in the other, and that doing so might turn out to be interesting. But just as finding a Hamilton Cycle is not the same as 3-Colouring a Graph, they are not the same. > My spider sense is telling me that > something interesting is going on > here, and there may be some more > ways to link linear programming up > with dynamic programming. I'd love to see more detailed speculations and investigations. In summary, I suspect we are in agreement, and that you're objecting to something I didn't actually say. I don't deny that there might be, or even probably are, deep connections. But for someone trying to understand what the Simplex Method is and does, I don't think that's particularly helpful. Maybe I'm wrong - I'm pleased to wrote what you did.

DannyBee 10y ago

"How sure are you that the converse is not also true? Will you at least admit this is an interesting question? Or even the question of how to ask this question in such a way that it is provable/disprovable. I think this is worthwile." It's an interesting question, but one which has a sad answer: integer linear programming (and other restricted forms, such as 0-1 programming) are NP-Hard. If you could use dijkstra's algorithm to solve them, in less than exponential time, you will have proved P=NP. So i would go with "pretty sure". (now, could you do it in exponential number of dijkstra invocations? Maybe? But that is, to me, not an interesting question :P Same with could you expand the linear programming problem into an exponential size graph that was then solvable by dijkstra's algorithm - we already know that expspace is a superset of p, etc)

ColinWright 10y ago

>> It's not Dijkstra's algorithm in disguise >> - it's not any kind of search. > It's a kind of superficial statement to make: > "this is not that". Obviously these things > are different on the surface, but probing a > bit deeper can sometimes bring similarities > out. Agreed, although I was trying to answer the question as asked, and not start writing an entire essay on how instances of one type can be encoded as instances of another. MineSweeper is NP-Complete, so we can encode Hamilton Cycle (for example) in it. MineSweeper is not an instance of Hamilton Cycle, they can each be encoded in the other, this is deeply interesting, but it doesn't help someone trying to get to grips with what the Simplex Method "is". Coming to understand what it "is" is the gateway to seeing how it might, or might not, then be used to encode, and solve, other problems. > This is more interesting to me, although > perhaps I am just getting old and too many > neurons are interconnected and this is what > makes me seek the similarities between things, > instead of just saying "this is not that". I'm 55, and finding deep connections is (part of) what I do. Understanding that some things are genuinely different is, to me, an important place to start. > ... the simplex method can be used to > implement Dijkstra. How sure are you > that the converse is not also true? I'm pretty sure Dijkstra can be used to solve instances of Linear Programming, although the encoding is likely to be exponential. It might then be simplified by using the specific characteristics of linearity, etc, but that's not the same as saying that it is an instance of LP. > Will you at least admit this is an > interesting question? Absolutely - I'm not even forced to "admit" this sort of thing. It's what I spend much of my time trying to convince other people about. But Dijkstra is not the Simplex Method in disguise, not vice versa. Perfectly happy to say that each could (perhaps) be encoded in the other, and that doing so might turn out to be interesting. But just as finding a Hamilton Cycle is not the same as 3-Colouring a Graph, they are not the same. > My spider sense is telling me that > something interesting is going on > here, and there may be some more > ways to link linear programming up > with dynamic programming. I'd love to see more detailed speculations and investigations. In summary, I suspect we are in agreement, and that you're objecting to something I didn't actually say. I don't deny that there might be, or even probably are, deep connections. But for someone trying to understand what the Simplex Method is and does, I don't think that's particularly helpful. Maybe I'm wrong - I'm pleased to wrote what you did.