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 3 weeks ago • 1353 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!
Peanut Butter Cup Love T-Shirt
Peanut Butter Cup Love
TCIF Thank Cthulhu Its Friday T-Shirt
TCIF Thank Cthulhu Its Friday
You Lie T-Shirt
You Lie

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 3 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
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  (54574 votes)
2. arvana  (44871 votes)
3. dystopianfuturetoday  (43382 votes)
4. kronosposeidon  (40190 votes)
5. NetRunner  (39499 votes)
6. blankfist  (37256 votes)
7. ant  (34689 votes)
8. mintbbb  (31840 votes)
9. Farhad2000  (31684 votes)
10. eric3579  (30506 votes)
11. rasch187  (30026 votes)
12. Issykitty  (27142 votes)
13. mlx  (21681 votes)
14. deputydog  (21048 votes)
15. Fedquip  (20917 votes)
Top 15 Sifters of the Past Week
1. demon_ix  (509 votes)
2. MikesHL13  (443 votes)
3. Sagemind  (379 votes)
4. Ornthoron  (377 votes)
5. Issykitty  (351 votes)
6. ant  (311 votes)
7. arvana  (307 votes)
8. EndAll  (296 votes)
9. brycewi19  (291 votes)
10. Fusionaut  (277 votes)
11. Zifnab  (244 votes)
12. rasch187  (209 votes)
13. gwiz665  (196 votes)
14. NetRunner  (190 votes)
15. EDD  (171 votes)