|
Many real world planning problems are np-complete. For example, some companies would very much like to know the most efficient way to deliver X packages to Y destinations with a fleet of Z trucks. Those same companies would also, no doubt, like to impose some constraints like limiting the percentage of late deliveries. The Department of Transportation would probably like to get in the act, too -- regulations limit how many hours a driver can be behind the wheel within a given period of time.
The only way to really, truly, find the best solution to that problem is to check all valid solutions against each other. It should be obvious that to exhaustively check every single solution is not computationally possible. By the time you'll have arrived at the best solution, all the packages will be so late that their recipients will have died of old age.
So, instead of an exhaustive search, we'll take a different approach: Generate any solution at random, and then, while time permits, try to improve upon it. With every improvement, we hope to get closer to the ideal solution, even though we may never find it (and even if we do find it, we wouldn't know that we've found it).
And that, in a nutshell, is hill climbing. It also happens to be a very good approach to software development.
Due to time constraints it's unlikely that we, as software developers, will ever write the best possible software solutions. In all but the simplest of software projects, there will always be something to improve upon.
I wouldn't recommend starting a software project (or part thereof) with just any random piece of code -- I'd like to think we can start projects somewhere in the vicinity of good code. But I would recommend keeping in mind that first versions are just starting points.
When I'm writing code, I like to make a mental checklist of potential, future improvements. That algorithm isn't ideally suited to our data... This documentation could be a little more clear... I really should refactor here... I should write a unit test to cover this edge condition... And, so forth.
Each improvement should be iterative and independent of other improvements. With hill climbing there's always the possibility walking down into a valley. Which may be fine if we're escaping a local maxima, but maybe we're just flat out headed in the wrong direction.
Some "improvements" are best thrown away.
But, perhaps I've stretched this hill climbing analogy a little too far. Perhaps, a new analogy is in order: I've often found that software development is like writing a blog article. Sometimes an article goes on too long. Sure there's more that could be said, but if you've already made you're point, why bother? Writing code is the same way, sure you could continue to improve it, but if it works, why bother?
Maybe it's good enough already.
|
Anonymous says,