3 ms·
Is this like the travelling salesman problem, but looking for the longest, not shortest journey?
by 4ndrewl 5mo ago
Is this like the travelling salesman problem, but looking for the longest, not shortest journey?
- saghm 5mo agoFinding the longest path in a graph is itself a pretty well-described NP-complete problem: https://en.wikipedia.org/wiki/Longest_path_problem https://en.wikipedia.org/wiki/Longest_path_problem Alternately, you can listen to a Billy Joel parody that describes the problem in decidedly less academic terms: https://www.youtube.com/watch?v=a3ww0gwEszo https://www.youtube.com/watch?v=a3ww0gwEszo
- nottorp 5mo agoHmm fun study topic: which major algorithms stay the same when you "invert" their goal, and which don't? Where invert can mean at the least: switch max/min or gt/lt, but also for find the subset, find what's not in the subset. At the least.