Quick Options

NSFW Content:
Listing Mode:
Coloring Style:
Animations:

◀ Quick Options    Login    Register
X Greetings! You are not currently logged in, but please don't let that stop you from voting up any videos you like. :)

3D,computer science,fundamental problem,graph theory Genetic Algorithm solves Traveling Salesman problem

Genetic Algorithm solves Traveling Salesman problem

posted by oxdottir 1 year 8 months 4 weeks ago • 1364 views
tags: 
embed
email

The Travelling Salesman problem is stated as: "Given a number of cities and the costs of travelling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once?"

Ryan Bateman used the open source classes listed at heatonresearch.com to create a Processing program that would solve the 3D Travelling saleman problem using Genetic algorithms. Re-used paths (corresponding to Chromosomes) increase in visibility as they're re-used, fading otherwise,
meaning the paths 'emerge' as certain chromosomes become more dominant.

The problem is considered 'solved' when a hundred generations have passed without a more optimal solution having been found. This is really a philosophical position because this definiton of "solved" is not conventional, and if it really is "solved," this solution can be used to do all sorts of exciting things like break cryptographic algorithms, and such.

For more on genetic algorithms used to produce art (including a fair amount of math), see http://www.videosift.com/video/Google-talks-Scott-Draves-on-technical-details-for-art.

GREAT DESIGNS FROM VIDEOSIFT'S T-SHIRT STORE
Support VideoSift - Buy a Shirt! Use coupon code SIFTFALL09 at checkout to save an additional 20% now!
Atheism For Lent T-Shirt
Atheism For Lent
Classy As Fuck T-Shirt
Classy As Fuck
Grab A Mop T-Shirt
Grab A Mop

Comments subscribe to this feed
Upvote purely because this is very close to how routers perform route fowarding decisions. Ie. This is how the internet would work if you could see routers calculating least cost paths to each destination in their route table.


written by charliem  | 1 year 8 months 4 weeks ago | CH
 1  | flag spam (0)
Connect the dots. la lala lala
Connect the dots. la lala lala


written by Doc_M  | 1 year 8 months 3 weeks ago | CH
 0  | flag spam (0)
NO, NO, NO! GOD DID IT!


written by Smugglarn  | 1 year 8 months 3 weeks ago | CH
 -1  | flag spam (0)
That's pretty slick for an NP-hard problem.


written by HaricotVert  | 1 year 8 months 3 weeks ago | CH
 1  | flag spam (0)
Submit Comment

Connect with Facebook
          - OR -
log in or register to submit new comment


playlists with this video
So cool! by gwiz665  • So interesting by gwiz665

who voted for this video
oxdottir  - Fjnbk  - siftbot x21 - gwiz665  - Lann

who has this post bookmarked
gwiz665  - jonny  - Fjnbk

Genetic Algorithm Solves Traveling Salesman Problem Related Videos

Ivy League Computer Science parody of Minority Report

Obama Knows His Computer Science

Evolution of a Virtual creature: 1070 generations

Watch this Video Next

Friends O' the Sift
Top 15 Sifters of All Time
1. Zifnab  (54762 votes)
2. arvana  (45077 votes)
3. dystopianfuturetoday  (43699 votes)
4. kronosposeidon  (40492 votes)
5. NetRunner  (39651 votes)
6. blankfist  (37341 votes)
7. ant  (35090 votes)
8. mintbbb  (31847 votes)
9. Farhad2000  (31731 votes)
10. eric3579  (30527 votes)
11. rasch187  (30104 votes)
12. Issykitty  (27242 votes)
13. mlx  (21750 votes)
14. deputydog  (21076 votes)
15. Fedquip  (20924 votes)
Top 15 Sifters of the Past Week
1. EndAll  (509 votes)
2. Sagemind  (305 votes)
3. MikesHL13  (292 votes)
4. ant  (281 votes)
5. dystopianfuturetoday  (264 votes)
6. gwiz665  (254 votes)
7. kronosposeidon  (240 votes)
8. demon_ix  (240 votes)
9. necrontyr  (235 votes)
10. Issykitty  (212 votes)
11. Zifnab  (211 votes)
12. Duckman33  (203 votes)
13. NetRunner  (167 votes)
14. arvana  (149 votes)
15. enon  (145 votes)