What are the real-world practical problems where only the best (exact) solution algorithm or program will do (but not the good-enough solution)?

EDITED (I realized that the question certainly needs a context)

The problem 1.1-5 in the book of Thomas Cormen et al Introduction to algorithms is: "Come up with a real-world problem in which only the best solution will do. Then come up with one in which a solution that is “approximately” the best is good enough." I'm interested in its first statement. And (from my understanding) it is asked to name a real-world problem where only the exact solution will work as opposed to a real-world problem where good-enough solution will be ok.

So what is the difference between the exact and good enough solution. Consider some physics problem for example the simulation of the fulid flow in the permeable medium. To make this simulation happen some simplyfing assumptions have to be made when deriving a mathematical model. Otherwise the model becomes at least complex and unsolvable. Virtually any particle in the universe has its influence on the fluid flow. But not all particles are equal. Those that form the permeable medium are much more influental than the ones located light years away.

Then when the mathematical model needs to be solved an exact solution can rarely be found unless the mathematical model is simple enough (wich probably means the model isn't close to reality). We take an approximate numerical method and after hours of coding and days of verification come up with the program or algorithm which is a solution. And if the model and an algorithm give results close to a real problem by some degree that is good enough soultion.

Its worth noting the difference between exact solution algorithm and exact computation result. When considering real-world problems and real-world computation machines I believe all physical problems solutions where any calculations are taken can not be exact because universal physical constants are represented approximately in the computer. Any numbers are represented with the limited precision, at least limited by amount of memory available to computing machine.

I can imagine plenty of problems where good-enough, good to some degree solution will work, like train scheduling, automated trading, satellite orbit calculation, health care expert systems. In that cases exact solutions can't be derived due to constraints on computation time, limitations in computer memory or due to the nature of problems.

I googled this question and like what this guy suggests: there're kinds of mathematical problems that need exact solutions (little note here: because the question is taken from the book "Introduction to algorithms" the term "solution" means an algorithm or a program, which in this case gives exact answer on each input). But that's probably more of theoretical interest. So I would like to narrow down the question to:

What are the real-world practical problems where only the best (exact) solution algorithm or program will do (but not the good-enough solution)?

There are problems like breaking of cryptographic ciphers where only exact solution matters in practice and again in practice the process of deciphering without knowing a secret should take reasonable amount of time. Returning to the original question this is the problem where good-enough (fast-enough) solution will do. There's no practical need in instant crack though it's desired. So the quality of "best" can be understood in any sense: exact, fastest, requiring least memory, having minimal possible network traffic etc.

And still I want this question to be theoretical if possible. In a sense that there may be example of computer X that has limited resource R of amount Y where the best solution to problem P is the one that takes not more than available Y for inputs of size N. But that's the problem of finding the particular solution for P on computer X which is... well, good enough.

My final thought that we live in a world where it is required from programming solutions to practical purposes to be good enough. In rare cases really very very good but still not the best ones. Isn't it? :) If it's not can you provide an example? Or can you name any such unsolved problem of practical interest?

-
If you'd like assistance with a problem post the problem itself. Otherwise, the question is far too open-ended. – eulerfx Oct 4 '12 at 23:39
Define "best." Fastest? Cheapest? Smallest executable? Most reliable? Easiest to maintain? Works on highest number of computing devices? – Robert Harvey Oct 5 '12 at 0:05
One example of the second one would be finding the "shortest route" between cities used by the airline industry. The other option would be located in the medical field, where a solution to a problem, could be the difference betwen life and death. – Ramhound Nov 13 '12 at 3:34
Are you looking for examples? I'd say a weather forecast model. Why? Best can be read as "best known". As soon as someone comes up with a better model, the older ones are instantly deprecated. – Pieter B Feb 8 at 15:02
Shouldn't this be moved to cs.stackexchange.com? – user16764 Feb 8 at 23:46
show 1 more comment

Note that this is at the very start of the book, when we're still talking in very general terms about 'problems', which aren't necessarily computational or mathematical. Also, your bolded question I think misstates the problem from the book.

The book (assuming the text in the linked blogpost is accurate) asks for

a real-world problem in which only the best solution will do

only the best (exact) solution algorithm or program will do (but not the good-enough solution)

This doesn't make sense. By definition, a "good-enough solution" is good enough, even when it's suboptimal (ie not the best possible). The book is asking for a case where anything suboptimal (ie anything but the best) is not good enough.

And here's my example:

You are a parent. You have a set period of time to consider, a limited supply of food and water, and yourself and `n` children to keep fed and watered. Maximise `m`, where `m` is the number of people who survive to the end of the set period of time.

An algorithm that results in `m = n` is very close to optimal (only `1` off!), but really wouldn't do.

-
 I take that that any algorithm that gives you m = n + 1 and completes within the time period is considered to be equally "optimal" then? – user16764 Feb 8 at 23:43 @user16764 yes, by stating that the only considered output is `m`, I avoid tricky questions about the quality of survival... – AakashM Feb 8 at 23:52 It is possible to survive with m > n + 1 if the children are from different families, grow up during a period if it is big enough and start having their own families. – Mike Feb 11 at 18:37 You are right, I'm not asking the same question the book asks. However I need you to help me realize how I misstate good-enough and best concepts in my question. Because from the lines you highlighted the only difference I see is that I'm asking about the problem that has to be solved programmatically. But that's the reason the question is on this site and not somewhere else. – Mike Feb 11 at 19:26

Best is kind of dependent on the context, but if it means most reliable I think a device that controls the delivery of doses of radiation for cancer treatment would be right up there. So would the control system for a heavy lift VTOL aircraft. Systems that control space vehicles, both manned (to protect life) and unmanned (to protect huge financial investments) would be in this category. Failures in these areas (Therac-25, V22 Osprey during development, Ariane-5) and a success (IBM Federal Systems Space Shuttle software) are worth knowing among all practicing software engineers.

Other five nines quality systems might include 911 call centers, stock trading transaction managers, phone switches including cellular infrastructure, and military command and control systems.

There are other bests like the famous story of Steve Jobs telling Steve Kenyon that if he could make one of the Apple products boot a second faster every day for millions of users for years and years it was thousands of lifetimes that would not be spent waiting.

-