My Secret Life as a Spaghetti Coder
home | about | contact | privacy statement
A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. In many problems, a greedy strategy does not in general produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution in a reasonable time.
What does a greedy algorithm look like?
Images from Wikipedia illustrate the concept well. In the first one, we begin our search of the space for a maximum at point A. If we're greedy, the next highest point takes us along a path that maximizes at point (lower case) m. However, the optimal solution is at point (upper case) M.

Illustration of greedy search along a plane

If you're greedily searching (again, for a maximum) in three-dimensional space, and start in a poor position (like near the left in the image below), you'll never make it off the shorter hill onto the taller one:

Illustration of greedy search using three dimensions

What does a greedy algorithm for yourself look like?
Perhaps we should first define what it is for which we're optimizing: To keep it simple, I'm going to identify it as maximizing income.

You could also be seeking to minimize the distance (in time) between working for clients, or minimizing the time you spend acquiring each customer -- maximization is not an intrinsic property of optimization.

I purposefully exclude things like time and happiness (or optimizing for some combination of all three). While I value those things and would like to think I've tried to optimize for them, upon closer inspection I recently realized I've tended to simply accept whatever side-effect optimizing for money has had on those values.

I think it's a fair assumption that plenty of other people are doing the same. If you're not one of them: congrats! But before you dismiss the idea entirely, you ought to consider that you might be, just to be sure.

So what does it look like? Again from Wikipedia, I like the idea of moving from node to node on a graph:

Illustration of greedy search in a graph

At each point in time (a vertex on the graph) we are presented with a series of options whose positive return is the value at that vertex. The options available to us are connected by the edges. (You might also assign a cost to each edge, and change your greedy-optimization heuristic to be return minus cost).

In the graphic I've used, only two options are available at each point, but in reality there are normally a lot more options from which to choose, and maybe even times when you have only one option.

If we're starting at 7 and being greedy in our search for a maximum, we miss out on the global maximum.

You might mention -- hey, we could backtrack and search the entire space. But you might not have the resources available once you've gone down the path to 6. You might have reached your maximum workload by that point, and by the time you free up some time, the opportunity for the 99 is gone.

How do you know if you're running your business like a greedy search algorithm?
Here are some symptoms:
  • Taking the first job offer or client you get when you need work
  • If you're a freelancer, filling all your time with client work
  • Taking the first business model that seems to be working and trying to maximize it
Can you think of any others?

Prior to last year, I was executing a totally greedy algorithm with regards to my career. But it's not just something I've noticed in myself: almost every job I've had utilized greedy methods for making money.

As part of my greedy search (which was not just about maximizing money, but more towards minimizing unemployment, even if it meant working for people who would end up stiffing me on paychecks), I ended up burning through about four months of savings (I had six). Last year though, I started making some changes to a better approach. When I made my way back up to a six month cushion and took time to reflect on some of the changes that got me there, I realized the parallels to algorithms I'd learned about in college.

Improving your odds
How can you improve your chances of finding a global (or at least higher) maximum?

In the general problem, given enough time and resources, you could do an exhaustive search -- or in our graph model, visit every node.

But I don't have the resources to exhaustively search the entire space to produce an optimal solution, and I'm betting you don't either.

Instead of straight greedy hill-climbing, we could explore some variants. My favorite here is called "shotgun hill climbing," where instead of following a path all the way to it's maximum, we'll randomly restart (but we don't forget where we came from on those restarts, in case we don't end up in a better position).

It's what I like about Amy Hoy's stacking bricks metaphor. A freelancer can start taking time between gigs (or not remain fully engaged) and spend some time developing products. Each successive product is a new brick, and over time you can build a wall.

Savings and product revenue are like ammunition for your shotgun hill climbing business algorithm. They allow you to explore different starting positions, as long as you're not being greedy with minimizing the distance (in time) between clients or booking all your time to work for others.

In practice, all those ideas you have floating around in your head (or ideas.txt file) are the different options you have in paths to take (in addition to other jobs, clients, ideas for "upselling", etcetera). You have to spend a significant piece of time on one to find out if it gets you further up the hill or not -- but not so much so that you can't get back to your last local maximum or randomly try another.

(Side note: I'm not advocating strictly random here -- you can apply some heuristic to affect the "probability" of choosing a certain idea).

Last year I took my first steps to taking a shotgun approach. This year I plan to take it further.

Thoughts? I'd love to hear them below.

Hey! Why don't you make your life easier and subscribe to the full post or short blurb RSS feed? I'm so confident you'll love my smelly pasta plate wisdom that I'm offering a no-strings-attached, lifetime money back guarantee!

Leave a comment

In your text: "My favorite here is called 'shotgun hill climbing,' where instead of following a path all the way to it's maximum, we'll randomly restart (but we don't forget where we came from on those restarts, in case we don't end up in a better position)."

I suppose that would be like my heavily training nearly 20 years ago for client/server database application development only to have no clients interested in the skills I had acquired.

Then 2011 a recruiter is referred to me. I ask the client what they want, answer, "a web database". So I wrote a proposal for a "web database". We (business side of the organization) met with IT to hand the project over to them. They said they were too busy with other projects, they liked my consulting work, said that I should do the work and to implement it in Client/Server. "Hello?!?!? I will check the calendar... yes, that was June 2011!!!"

The size of this little ERP / Business Intelligence package is currently: 93,602 LOCs, 332 Modules, 233 Stored Procedures, and counting... My longest "two week gig" ever. And Client/Server works as well as was promised 20 years ago, when implemented correctly including Software Distribution for automated client updates.

Posted by mdlueck on Jan 22, 2013 at 11:44 AM UTC - 6 hrs

@mdlueck - I'd like to hope I'll get a quicker ROI on my shotgunning approach than you did, but I'm glad it proved valuable to you in the end! =)

Thanks for telling me the story, I enjoyed reading it!

Posted by Sammy Larbi on Jan 23, 2013 at 02:12 PM UTC - 6 hrs

Leave a comment

Leave this field empty
Your Name
Email (not displayed, more info?)


Subcribe to this comment thread
Remember my details

Picture of me

.NET (19)
AI/Machine Learning (14)
Answers To 100 Interview Questions (10)
Bioinformatics (2)
Business (1)
C and Cplusplus (6)
cfrails (22)
ColdFusion (78)
Customer Relations (15)
Databases (3)
DRY (18)
DSLs (11)
Future Tech (5)
Games (5)
Groovy/Grails (8)
Hardware (1)
IDEs (9)
Java (38)
JavaScript (4)
Linux (2)
Lisp (1)
Mac OS (4)
Management (15)
MediaServerX (1)
Miscellany (76)
OOAD (37)
Productivity (11)
Programming (168)
Programming Quotables (9)
Rails (31)
Ruby (67)
Save Your Job (58)
scriptaGulous (4)
Software Development Process (23)
TDD (41)
TDDing xorblog (6)
Tools (5)
Web Development (8)
Windows (1)
With (1)
YAGNI (10)

Agile Manifesto & Principles
Principles Of OOD
Ruby on Rails

RSS 2.0: Full Post | Short Blurb
Subscribe by email:

Delivered by FeedBurner