Archive Pages Design$type=blogging

Simple Travelling Salesman Problem (TSP) OpenGL Graphics Program

Presenting the Travelling Salesman Problem (TSP) OpenGL Graphics Program in C++ language.

Many students looking for OpenGL Graphics Program for Travelling Salesman Problem (TSP), so we came up with it.

What is Travelling Salesman Problem (TSP)?

The Traveling Salesman Problem is problem where a traveler (or salesman) have to visit given no of cities, with known distance. Salesman have to visit each city once with and return to origin city with shortest possible distance.

The TSP is np-hard problem, where we have to optimized all the possible combinations.


How to solve this problem?

In Computational world we solve this problem with two techniques - 1. Brute Force Approach and 2. Dynamic Programming.

1. Brute Force Approach - If we have n, no of cities then by brute force approach we will get (n-1)! permutations. We calculate cost (distance) of every permutation and record minimum cost for it. Finally return the permutation with minimum cost.  The time complexity for this method is n!.

2. Dynamic Programming - In this method we create the cost matrix and find the minimum cost.

Read the Dynamic Programming Approach for TSP.

Our Travelling Salesman Problem OpenGL Program

In our program we have restricted ourself to a maximum of 10000 cities. So, at begining user have to input the no of cities subjected to restriction, as mentioned. Each cities are represented as points. Lines joining the cities represent the distance. In initial setup the program creates sequence from the input, then distance is calculated. The swap and iterations are performs on the cities to find out the minimum distance.

You can see the image below - 

User Interaction

The initial distance is calculate at the beginning after user enter the no of cities in command line.
Next, there is two options for user -  key 's' and key  'a'.

When key 's' is pressed, two cities are selected randomly and swapped only when distance is minimum. This is performed as many times as 's' is pressed and distance calculated after swamp is shown in command line.

Pressing 'a', the swapping performed as many times for different cities(all). After performing each iterations the distance is shown in command line and finally it shows the minimum possible distance. Though this may not be the shortest path or minimum distance covered but optimal solution.  



3D Bi-Cycle 3D Game 3D Laptop 3D Objects 3D Projects 3D Zoo Algorithm Android Aquarium Bellman-Ford Algorithm B├ęzier curves Block Breaker Blockshooting Bucket Sort C# Chess Clock Code Blocks Colors Complex Project Complex Projects Crab Pong Cross Zero Doll DSAV Escapa Fighter Jet First Come First Serve Flag Flag Hoisting flag of usa Fluids Font Demo Games Gear Motion GlutDino Glutplane Graphics Editor iOS iPhone Java Java OpenGL Graphics Programming Light Torus Linked List Ludo Board Game Mancala board games Martyr’s Monument Memory blocks game Memory Game Menu Mickey Mouse Minesweeper Miniature Steam Engine moth Motion Blur MoveLight moving car Moving Ship Multiplex Networking Based Project Nuclear Power Plant Olympic opengl c++ examples OpenGL ES OpenGL Programming OpenGL Tutorial Origami OS Based Projects Paint Paper Folding Particles Drop Path Finding ping pong Pong Game Project Report Projects Report Puzzles qix like Queuqe Random Flowing lines Ray Rigid Body Rings Robot sample c++ opengl code Screen Saver Screen Saver Ship Shadow Cube Shadowfun Shaheed Minar Ship Iceberg Simple Drawing Simple Haloed Lined Wireframe Simple Move Light Simple Project Simulation SNAKE XENZIA GAME Solar system Sorting Space Invaders Sphere Spot Light Swing Stack Stars Taj Mahal The Edge Game Tic Tac Toe Tower of Hanoi Traffic Signal Transformation Triangular Animation Trippy Tutorial water ripple effects Whirlpool
OpenGL Projects: Simple Travelling Salesman Problem (TSP) OpenGL Graphics Program
Simple Travelling Salesman Problem (TSP) OpenGL Graphics Program
Presenting the Travelling Salesman Problem (TSP) OpenGL Graphics Program in C++ language.
OpenGL Projects
Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago