The traveling salesman problem (TSP) is a well-known NP-complete problem. It has appeared in diverse field of human knowledge. Different heuristics have been developed to generate approximate solutions for TSP. In this project, we used 3 different heuristics for TSP to implement a half toning algorithm. We followed the 3 steps below to implement a half toning algorithm.

Given any input image,

- If the image is a color image, convert it into a black & white image.
- Now we generate the "cities"/vertices of a complete graph on which TSP algorithm will be applied. We distribute cities with a density that locally approximates the darkness of a source image.
- Now we run nearest neighbor, greedy and 2-opt heuristics for TSP on the "cities". This produces a single closed path that resembles the original image.

### Development Platform

This project was developed in C# 2.0 using Microsoft Visual Studio 2008.

### Report

The project report can be found here.

### SVN Repository

The source code repository is hosted at code.google.com. You can checkout the source code from here.