ah, ok. this might be the answer https://stackoverflow.com/questions/38896231/what-is-the-difference-between-optimality-and-efficiency

so optimal means correct? if the requirement is to find the shortest path, then anything that isn't the shortest past would be incorrect.

If the requirement is to find the shortest path, then only a shortest path is correct.

If the goal is "find a 'good enough' path, hopefully short" then an algorithm that, say, returns a path guaranteed to be at most twice as long as the shortest path, might be good enough, for your purposes.

There are many computationally hard optimization problems where people have figured out how to write a fast algorithm that is guaranteed to return a solution that is "at most A times worse than the best", but no one has figured out a fast algorithm with A=1.

i think i understand. I was working through a problem on a discrete optimization class and they required you mark if your algorithm proved optimal. I looked at some existing solutions and people just hard coded this flag . in the lectures they talk around it but never specifically define it. At one point they say DP is optimal for knapsack, but then later say it depends on the input. I'm going to hardcode it as well, as it seem to be a bit of a distraction.

knapsack is one of those hard computational problems where, for the general problem with arbitrarily large pieces sizes, there is no known "fast" (i.e. guaranteed worst case polynomial run time in the size of the input). If the piece sizes are limited to be small, then there are.

You should probably ask the professor/TA to be sure what they mean, but my guess is when they say "mark if your algorithm proved optimal", they mean "tell us if the program you wrote implements an algorithm that is guaranteed to return a best possible solution". There are certainly algorithms for the problem that are guaranteed to return a solution, but not necessarily a best one.

There are algorithms that are not guaranteed to return a best solution, but they might still for some inputs return a solution that is a best one. Whether or not it is easy to determine that a particular solution is a best one or not, depends a lot upon the problem.

Thanks Andy, i did ask on the class forums. I know i'm constant with other solutions so far and maybe specifics are made clear later. 🙂