Tuesday, May 11, 2010

Decision Trees

Technique Tuesday

Back in the early days of personal computers, when graphical displays began to outnumber character-mode displays (and state of the art computers had less processing power than modern smart phones yet took up most of your desk), a remarkable game came out that made those underpowered machines look like far more expensive graphical workstations.

The game was called Doom and it achieved its magic through a special incantation called binary space partitioning (BSP) trees. Without belaboring the algorithm, BSP trees enabled the game engine to quickly determine what the player was looking at so that it could ignore most of the information about the environment and focus the computer's meager processing power on rendering just those things the player could see.

Decision trees are an organizational tool that has much of the same magic as BSP trees. While there are more rigorous applications of decision trees, the basic idea is that you lay out a tree of possible outcomes for each decision. As you work through the tree, the best course of action often becomes clear because you can eliminate branches that lead to undesirable outcomes. For example, when it was time to go courting it didn't take me long to realize that the vast majority of women were not suitable candidates for a spouse (for a variety of reasons) and that I would be less frustrated if I devoted my attention and efforts only to those women that were suitable.

Again, like other little systems, the goal here is to reduce potentially complex situations to simpler and more manageable forms.

Image: luigi diamanti / FreeDigitalPhotos.net