Dynamism in Heuristics

December 29th, 2005

Finally read through Pattern in the Stone, by W. Daniel Hillis. Great read for anyone curious in the fundamentals behind computing. When I say fundamentals, I am not referring to how to setup your new printer, or fix that annoying blue screen of death error, but understanding the mystery behind a box living with you, helping you do things that would be otherwise impossible.

One aspect of this book that was truly informative, was Hillis’ look into algorithms vs. heuristics. In the short time I’ve actually begun feeling comfortable with programming, I’ve always explored problems through a “design an algorithm” approach. I’m just beginning to realize, my approach was only allowing me to find half of the solutions to the problem through my lack of a definition of algorithm. It turns out, an algorithm is a method for solving a problem 100% of the time… no errors, no bad judgement. Its a hard and fast way to solve something, and it usually emplores some set of logic for a pragmatic result (if this is bigger than that, do something, etc). In comparison, heuristics are different and require a different way of thinking about the problem. Rather than searching for one undeniable truth or solution to a problem, heuristics are methods of discovery similar to scouts in war. They are sent out, in a quazi-random fashion to explore the landscape, and return with any information they were able to find. This allows random samples of data to be used in comparison, rather than exhaustive research.

Exploring heuristics in networks has potential benefits, especially in the creation of nodes. Over and over, I find myself realizing that the problems I wish to tackle in building networks revolves around the dreaded N*N equation. As a network scales, it becomes ridiculously hard to control, and even harder to compute. Hillis mentions the need for heuristics while describing real world problems that have a hard time finding algorithms. The famous example in this case being the “Traveling Salesman Problem”. Help the salesman find the shortest route from city to city, and you have the N*N conundrum. For every city you add, you add that many more possible combinations of complexity over which is the fastest. Below are some links to this problem, which is one of the “holy grails” in computer science. I would love to explore potential augmentation to nodes in a network, if they are given certain heuristical analysis to perform in and above their normal nodal tasks (sending and receiving). Would this “random samplings” give certain nodes more natural reactions with the network at large? Could the network as a whole be more robust, with potential for natural decentralization? Is this method already in place in modern P2P applications. These are all questions I would like to further study…

TSP - Mathworld Explanation
Traveling Salesman Problem Competition

Entry Filed under: Concepts and Thoughts, Thesis