Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Please, if you feel that question is big and does not deserve your attention (tl;dr) do not downvote it or ask for closing it being based on that.

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 I would like to develop my (mis)understanding of the question and ask 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 the computer 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 the mathematical model needs to be solved and 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 originally 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:

Are there any real-world practical problems where only the best (exact) solution algorithm or program will do (but not the good-enough, suboptimal, you call it solution)?

I want to clarify my understanding of "good enough". The best solution is good enough but not every good enough solution is the best (exact, fastest, etc..) one. So I’m asking for a kind of a problem for which no solutions can be considered good-enough unless the solution is the best.

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.

During formulation of this question I came to conclusion that we live in a world where it is required from programming solutions to practical purposes to be good enough. In rare cases (like shuttle maneuvering) very very good ones. I could not find any problems that require only the best solution. If there is such problem of practical interest solved or unsolved can you provide any example of it? Or does there exist any proof that no such problem can exist?

share|improve this question

closed as unclear what you're asking by Ozz, Bart van Ingen Schenau, MichaelT, GlenH7, Dynamic Aug 18 '13 at 20:32

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

    
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
1  
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
3  
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 '13 at 15:02
2  
Consider the possibility that the correct answer might be: "There are no real world problems where a solution that is good enough is not good enough." –  user16764 Feb 12 '13 at 15:38
add comment

2 Answers

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

but your bolded question asks for

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.

share|improve this answer
    
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 '13 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 '13 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 '13 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 '13 at 19:26
    
To be clear, your example is absolutely not of a kind of a problem that needs only the best solution. There could be ways (solutions) to survive with m1=n+1, m2=n+2, m3=(n+1)*2 or even m4=(n+2)^(n+1) all are greater or equal than n+1, so all are good enough. In its definition this problem is bound to the multitude of satisfactory solutions, not only the best one. You might set another problem as: survive with final amount of n+1 of the very same people during the time of T and that still has numerous variations on how to get food or how to fight diseases in order to survive. –  Mike Oct 4 '13 at 4:13
add comment

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.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.