←back to thread

Seam Carving (2018)

(andrewdcampbell.github.io)
70 points maxwell | 1 comments | 24 Jul 24 19:03 UTC | HN request time: 0.001s | source
Show context
Murky3515[dead post] ◴[27 Jul 24 06:27 UTC] No.41084799[source]▶
[flagged]
_a_a_a_ ◴[27 Jul 24 06:52 UTC] No.41084885[source]▶
[flagged]
replies(4): >>41085044 #>>41085141 #>>41087052 #>>41089622 #
tejtm ◴[27 Jul 24 08:04 UTC] No.41085141[source]▶
Indeed.

I would wager that over the last several decades BLAST (basic local alignment search tool) has done more to advance our knowledge of biology than any other algorithm.

https://en.wikipedia.org/wiki/BLAST_(biotechnology)

replies(1): >>41085207 #
Murky3515 ◴[27 Jul 24 08:21 UTC] No.41085207[source]▶
BLAST isn't a dynamic programming algorithm. It's not guaranteed to find an optimal solution, unlike a DP algorithm. It has some elements of DP, but that's it.
replies(1): >>41085234 #
_a_a_a_ ◴[27 Jul 24 08:27 UTC] No.41085234[source]▶
"BLAST is a heuristic method which means that it is a dynamic programming algorithm..."

https://bioinformaticsreview.com/20210503/how-blast-works-co...

"The heart of many well-known programs is a dynamic programming algorithm, or a fast approximation of one, including sequence database search programs like BLAST..."

https://www.nature.com/articles/nbt0704-909

replies(1): >>41085328 #
Murky3515 ◴[27 Jul 24 08:57 UTC] No.41085328[source]▶
All DP algorithms guarantee an optimal result. It's a defining characteristic of DP. BLAST doesn't. I'm really surprised that you're attempting to debate this.
replies(2): >>41085379 #>>41085676 #
JohnKemeny ◴[27 Jul 24 10:44 UTC] No.41085676[source]▶
That's not true. You can of course use DP for heuristic and approximation algorithms. There's an FPTAS for Knapsack using DP, for instance.
replies(1): >>41088639 #
Murky3515 ◴[27 Jul 24 19:15 UTC] No.41088639[source]▶
It is true. DP always deals with optimization. Just because my car has a radio, doesn't mean my car is a radio.
replies(2): >>41092719 #>>41114936 #
1. JohnKemeny ◴[28 Jul 24 12:11 UTC] No.41092719{5}[source]▶
Well, perhaps you use different definitions than I do, but it should be obvious that it is possible to design an algorithm using dynamic programming that does not solve the problem optimally. By optimally here, I mean always output the optimal solution.

If you, by optimization mean that there's a function value you are maximizing or minimizing, than that's not true either, since Subset Sum and Hamiltonian path are canonical decision problems for which DP is used.

Heck, you can even take the standard TSP DP algorithm and, instead of looking at all possible "exit vertices" in linear time, look at a randomly chosen constant number of candidates, thereby reducing the running time by a factor n and getting a randomized heuristic function not guaranteed to give the optimal value.