3 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". Obv
by 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.