Finding Your Way (Pathing)

Zen Digest

  • There is only one optimal path.
  • It may actually not be optimal to find the optimal path.
  • Having a methodology will keep you from going in circles.

The Whole Picture

There are no lack of quotes about how the journey is more important than the destination.  Life is the journey between the two fixed points of birth and death.  The true challenge lies in how to best get from point A to point B.  Whether it is an existential crisis, or a data-traversal problem, surprisingly the solutions and methodologies are extremely similar.

I was recently trying to solve a database issue where I had an extremely large volume of data that I needed to be able to sort through intelligently and quickly.  Thankfully for me, this is not a unique problem, and some of the best minds have been working on it since the dawn of computing.  A large portion of the issue was solved by creating a binary-tree index.  While those words may seem unrelated to you if you’re not familiar with databases, the concept is actually quite simple.  Data gets stored in a “tree” (it actually looks more like a triangle).  Whenever a new item is added, it compares itself to the top of the tree.  If it’s greater, it goes to the right, if less, it goes left until it finds and empty spot.  For a visual you can see below:

As you can see above, this allows you to store 25 items that are no more than 4 items away from the top.  So, if you wanted to find item 25, you only need to do 4 checks, instead of 25.  This snowballs quickly.  You can store over 1 million items while being only 20 away from the top, and over 1 billion items while only being 30 away from the top.

Without this tree (or index) you’d have to do 1 billion checks to find the item, but with it, only 30.  That’s efficiency.

When it comes to data comparison, this is pretty much the de-facto standard and what enables websites and software to run as quickly as they can.

But what about complex problems

A binary tree is great when you can easily compare two items – is one greater or not – but when you get more complex, you need more complex methodologies.  Take for example driving directions.  You have to factor in things like traffic, distance, speed limit, traffic lights, etc.  At this point you also need to ask yourself – what is considered “best.”  For example, is it better to take the long-flat drive around a mountain (which is longer but safer) or to drive up and down the mountain, which is shorter but more dangerous and demanding on a car.  If it’s raining, you’ll probably want to drive around the mountain!

Some problems and ultimately get too complex to optimize.  In math, the shortest distance between two points is a straight line, but if an insurmountable object stands in our way, we must be quick to find a new route.  It is very possible to spend too much time at your starting point waiting to find the optimal route.  In these cases, it’s best to look for a good direction to start and begin your journey.  Once on your journey, give yourself checkpoints to recalculate the route and ensure you’re on the best path.

The Corn Maze Solution

There is a well known algorithm for solving basic mazes (an corn mazes).  You pick a side – left or right, and follow the wall.  It isn’t the most efficient but it is guaranteed to get you to the end.  It was favored by early computer scientists because its logic was simple and computationally inexpensive.

Share

Leave a Reply

Your email address will not be published. Required fields are marked *