Tuesday, November 22, 2011

An Idea for a Probabilistic Approximation of the Solution to the Travelling Salesman Problem

In one of my classes here at Brigham Young, our group has been asked to come up with a unique idea for getting a good approximation to an optimal tour in the traveling salesman problem. Here's the idea I came up with. 

I wanted to bring statistics to the table, knowing about such algorithms as Monte Carlo Integration and others which took an unsolvable or hard problem and managed its size simply by taking samples of the bigger problem. The question was: How do you take a "sample" of an optimal traveling salesman tour?

The idea came to select three cities at random, and then use Djikstra's Algorithm (or the Bellman-Ford Algorithm, in the case of negative edges) to find the shortest path from the first to the second, the second to the third, and the third back to the first again, making sure these paths do not cross. If there is no such path, we start over and pick three other random cities until we find a cycle in the way just described which connects them. Such a cycle we would call a subcycle, and it would represent a sub-optimal approximation to the optimal tour (it takes the shortest route across a subset of the cities in the graph).

Then, we rate the edges that were used in this subcycle. Initially, all the ratings associated with all the edges are 0. Each time we find a subcycle, we add k/N to each edge that is used in that subcycle, where k is the number of cities in the subcycle, and N is the total number of cities in the graph.

We then repeat this rating process hundreds or thousands of times, accumulating ratings for the edges that fall in these random subcycles as described above. In our group project, we have 30 seconds to find a solution for an arbitrarily-sized graph, so we just decided to run the rating process described above for 28 seconds, so that many samples could be taken.

All that is left to do now is to take this information and create a solution. This is easily done by finding the first tour through all the cities, trying first the edges with the highest rating. The hope is that this final solution will be a good approximation to the optimal solution.

We have not yet coded this up, but we are in the process of doing so. I'll post here to let the world know how well it worked out. I'm very excited to see how well this works!

I welcome any comments any of you may have on how well this may or may not work. Please feel free to respond to this post!

Tuesday, November 15, 2011

.vimrc Goodies: Literal Lambda

I recently took to programming in racket after starting to take a class from Jay McCarthy (twitter: @jeapostrophe). Racket is a scheme-based language constructed specifically with industrial use in mind, which means it is based on some pretty solid theory while also posessing, like perl and php, a package management system (PLaneT), a JIT compiler, and other goodies that make it a great language to use in the real world.

This language, along with perl (given that 'use lambda' is invoked), allows the programmer to insert an acutal unicode lambda instead of the keyword 'lambda'. DrRacket, racket's native IDE, allows you to insert this character by pressing 'CTRL+\' . After looking at this page and others, I found I could do this in vim, too.

I put the following lines in my .vimrc file (this same entry worked in my _vimrc file, for the windows version, as well):

if has("multi_byte")
if &termencoding == ""
let &termencoding = &encoding
set encoding=utf-8
setglobal fileencoding=utf-8
"setglobal bomb
set fileencodings=ucs-bom,utf-8,latin1

map! ^\ ^Qu03bb

I inserted the special characters '^\' (CTRL-\) and ^Q (CTRL-Q) by using the normal vim way: in insert mode, type CTRL-V, then whatever control character you need to. For example, I inserted '^\' by typing CTRL-V, CTRL-\. For CTRL-Q, it was trickier. CTRL-Q is usually a specially bound command, so in order to insert it I had to use its octal number ordinal: CTRL-V, 017, were the keys I typed to insert that character.

Now whenever I'm editing a file, I type CTRL-\ and out pops a bonefied lambda!