←back to thread

Seam Carving (2018)

(andrewdcampbell.github.io)
70 points maxwell | 1 comments | | HN request time: 0s | source
Show context
Murky3515[dead post] ◴[] No.41084799[source]
[flagged]
_a_a_a_ ◴[] No.41084885[source]
[flagged]
replies(4): >>41085044 #>>41085141 #>>41087052 #>>41089622 #
tejtm ◴[] 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 ◴[] 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_ ◴[] 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 ◴[] 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 #
_a_a_a_ ◴[] No.41085379[source]
DDG disagrees.

https://html.duckduckgo.com/html?q=%22%20heuristic%20dynamic...

I'm clearly not going to understand your motivation so I think I'll stop here.

(edit: There is absolutely nothing stopping heuristics and DP being combined; in fact they have to be in eg. database optimisation. A pure DP solution to query optimisation will be optimal, but will take unbounded (lthough finite) time, which is unacceptable. DP and heuristics are combined to both guide the DP search and bound it after a strict time (usually a couple of seconds CPU) by when it is hopefully 'good enough').

replies(1): >>41088629 #
1. Murky3515 ◴[] No.41088629[source]
You're wrong, and I don't know why you're being stubborn about this. HDP is a different class of algorithms that uses DP, but it is not DP. A basic read of wikipedia of dynamic programming reveals the key pieces of DP:

There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems. ... Optimal substructure means that the solution to a given optimization problem can be obtained by the combination of optimal solutions to its sub-problems.

See the words optimal and optimization?

https://en.wikipedia.org/wiki/Dynamic_programming