4 ms·

I agree that the output is often wrong despite looking right, but in this instance I don't see anything wrong in this example.

jvanderbot 4y ago
Dijkstra's cannot be used as generally as described. A-star can potentially be more general, but that's highly dependent on heuristic. Dinkstras is a-star with a "min weight on shortest path first" heuristic. Because a star doesn't expand shortest paths first necessarily, it cannot necessarily find the shortest path to any node except the prescribed endpoint. Dijkstra's will find all shortest paths with cost less than the path to the endpoint, and that's helpful sometimes.
- kevinwang 4y ago
  I actually think the robot's poetic take matches my thinking more closely than this description Edit: I guess in this description dijkstras is more specific, in that dijkstras is the specific instance of A* with a zero heuristic. But I think what HAL over here was saying is that you can use dijkstras in a superset of scenarios in which you can use (non-trivial) A*, so in that sense dijkstras is more general than A*, so it's not wrong.
- lqet 4y ago
  What is your definition of "general" here? The classic shortest path problem (which the psalm addresses) is described as finding the shortest path between two nodes, and given non-negative edge weights, Dijkstra's algorithm is perfectly general here. It will find such a shortest path in any graph, no further restrictions. For A*, everything depends on the heuristic, as you said. If h(v) = 0, A* is equivalent to Dijkstra's algorithm, so potentially, it can be as general. But the wrong heuristic (inadmissible, inconsistent) will lead to wrong results, and so calling it a "specialized" tool is correct. The heuristic gives you a specialized version of Dijkstra's algorithm which is faster on specific graphs. > Dinkstras is a-star with a "min weight on shortest path first" heuristic. I am not quite sure what you mean here. Dijkstra's algorithm is A* with no heuristic. I am not sure how a "shortest path first" heuristic would look like - do you mean that Dijkstra's algorithm chooses the node to expand next based on its shortest-path cost to the target t? Even if you would construct such a heuristic h(v) = c(v, t) by explicitly calculating c(v, t) each time, this is not what Dijkstra does, as it would basically be a perfect heuristic - you would then only visit nodes on the shortest path. If you meant that Dijkstra's algorithm is A* with a "neighboring node with shortest path from start node first" heuristic, that's also not strictly true, because expanding the nearest node first is already built-in to A*. A* does not chose the next node v with the smallest h(v), but with the smallest g(v) + h(v), where g(v) is the shortest path cost from the source node to v.
  - jvanderbot 4y ago
    > Dijkstra's algorithm is a general one, That can be used in any case, I take issue with this statement. "any case" implies it's more general than A star, which is not true, it's a specialization of A star with (ok you win) h(v) set to nothing. It necessarily cannot solve as many problems as a star. And Dijkstra's won't work in "any case" at all, esp graphs with negative edge weights. The explanation struck me as glossing over too much, to the point of being misleading. Perhaps I'm being too pedantic, fine, but a more enlightened comparison would read more like our discussion than what was given.
    - endorphinbomber 4y ago
      You realize it had the constraints of a poem, and needed to take some liberty with description there?
      - jvanderbot 4y ago
        Sure sure. I'm being pedantic. But replacing two sentences would fix it.
    - twic 4y ago
      > It necessarily cannot solve as many problems as a star. Could you give an example of a positive-weight shortest path problem with A* can solve, but Dijkstra's algorithm cannot? I do not believe there is such a thing. Or did you mean something else? > And Dijkstra's won't work in "any case" at all, esp graphs with negative edge weights. A* won't solve those either.
    - kragen 4y ago
      i would rather say that a* is an optimization of dijkstra's algorithm they both solve the single-pair shortest-path problem in digraphs with nonnegative arc weights a* which explores nodes in a different, better order thank dijkstra's algorithm, but can only be applied in cases where you can compute an admissible heuristic that makes it less general than dijkstra's algorithm, which works to find shortest paths in any digraph with nonnegative arc weights, not just the ones where an admissible heuristic can be computed any problem you can solve with a* can be solved with dijkstra's algorithm (usually more slowly) but the converse is not true now, in a sense, a* with an inadmissible heuristic such as h(v)≡0 is 'more general' in the sense that it can emulate dijkstra's algorithm and also do other things; you could say that a* is a class of algorithms of which dijkstra's algorithm is one
- deleted 4y ago
  [deleted]
JackFr 4y ago
> I don't see anything wrong in this example It's not in the style of a psalm.
- kevinwang 4y ago
  Ah, interesting. I didn't notice that. I have noticed that chatgpt is really impressive at doing rhyming poems/songs, and many of its generated poems sound similar to each other. I also don't remember raw gpt-3 being so good at poems. So I wonder if there was substantial fine-tuning for chatgpt specifically to reward it to generate poems, in a particular style. And here, it's "over indexing" on that and still generating poems in that familiar style

jvanderbot 4y ago

Dijkstra's cannot be used as generally as described. A-star can potentially be more general, but that's highly dependent on heuristic. Dinkstras is a-star with a "min weight on shortest path first" heuristic. Because a star doesn't expand shortest paths first necessarily, it cannot necessarily find the shortest path to any node except the prescribed endpoint. Dijkstra's will find all shortest paths with cost less than the path to the endpoint, and that's helpful sometimes.

kevinwang 4y ago
I actually think the robot's poetic take matches my thinking more closely than this description Edit: I guess in this description dijkstras is more specific, in that dijkstras is the specific instance of A* with a zero heuristic. But I think what HAL over here was saying is that you can use dijkstras in a superset of scenarios in which you can use (non-trivial) A*, so in that sense dijkstras is more general than A*, so it's not wrong.
lqet 4y ago
What is your definition of "general" here? The classic shortest path problem (which the psalm addresses) is described as finding the shortest path between two nodes, and given non-negative edge weights, Dijkstra's algorithm is perfectly general here. It will find such a shortest path in any graph, no further restrictions. For A*, everything depends on the heuristic, as you said. If h(v) = 0, A* is equivalent to Dijkstra's algorithm, so potentially, it can be as general. But the wrong heuristic (inadmissible, inconsistent) will lead to wrong results, and so calling it a "specialized" tool is correct. The heuristic gives you a specialized version of Dijkstra's algorithm which is faster on specific graphs. > Dinkstras is a-star with a "min weight on shortest path first" heuristic. I am not quite sure what you mean here. Dijkstra's algorithm is A* with no heuristic. I am not sure how a "shortest path first" heuristic would look like - do you mean that Dijkstra's algorithm chooses the node to expand next based on its shortest-path cost to the target t? Even if you would construct such a heuristic h(v) = c(v, t) by explicitly calculating c(v, t) each time, this is not what Dijkstra does, as it would basically be a perfect heuristic - you would then only visit nodes on the shortest path. If you meant that Dijkstra's algorithm is A* with a "neighboring node with shortest path from start node first" heuristic, that's also not strictly true, because expanding the nearest node first is already built-in to A*. A* does not chose the next node v with the smallest h(v), but with the smallest g(v) + h(v), where g(v) is the shortest path cost from the source node to v.
- jvanderbot 4y ago
  > Dijkstra's algorithm is a general one, That can be used in any case, I take issue with this statement. "any case" implies it's more general than A star, which is not true, it's a specialization of A star with (ok you win) h(v) set to nothing. It necessarily cannot solve as many problems as a star. And Dijkstra's won't work in "any case" at all, esp graphs with negative edge weights. The explanation struck me as glossing over too much, to the point of being misleading. Perhaps I'm being too pedantic, fine, but a more enlightened comparison would read more like our discussion than what was given.
  - endorphinbomber 4y ago
    You realize it had the constraints of a poem, and needed to take some liberty with description there?
    - jvanderbot 4y ago
      Sure sure. I'm being pedantic. But replacing two sentences would fix it.
  - twic 4y ago
    > It necessarily cannot solve as many problems as a star. Could you give an example of a positive-weight shortest path problem with A* can solve, but Dijkstra's algorithm cannot? I do not believe there is such a thing. Or did you mean something else? > And Dijkstra's won't work in "any case" at all, esp graphs with negative edge weights. A* won't solve those either.
  - kragen 4y ago
    i would rather say that a* is an optimization of dijkstra's algorithm they both solve the single-pair shortest-path problem in digraphs with nonnegative arc weights a* which explores nodes in a different, better order thank dijkstra's algorithm, but can only be applied in cases where you can compute an admissible heuristic that makes it less general than dijkstra's algorithm, which works to find shortest paths in any digraph with nonnegative arc weights, not just the ones where an admissible heuristic can be computed any problem you can solve with a* can be solved with dijkstra's algorithm (usually more slowly) but the converse is not true now, in a sense, a* with an inadmissible heuristic such as h(v)≡0 is 'more general' in the sense that it can emulate dijkstra's algorithm and also do other things; you could say that a* is a class of algorithms of which dijkstra's algorithm is one
deleted 4y ago
[deleted]

JackFr 4y ago

> I don't see anything wrong in this example It's not in the style of a psalm.

kevinwang 4y ago
Ah, interesting. I didn't notice that. I have noticed that chatgpt is really impressive at doing rhyming poems/songs, and many of its generated poems sound similar to each other. I also don't remember raw gpt-3 being so good at poems. So I wonder if there was substantial fine-tuning for chatgpt specifically to reward it to generate poems, in a particular style. And here, it's "over indexing" on that and still generating poems in that familiar style