Traveling Salesman Framework
Download this modelDo you have questions or comments about this model? Ask them here! (You'll first need to log in.)
WHAT IS IT?
This shows how to create two different kinds of random networks. In an Erdos-Renyi network, each possible link is given a fixed probability of being created. In a simple random network, a fixed number of links are created between random nodes.
THINGS TO NOTICE
SETUP-SIMPLE-RANDOM is fast as long as the number of links is small relative to the number of nodes. If you are making networks which are nearly fully connected, then we suggest using the following code instead:
ask turtles [ create-links-with other turtles ]
ask n-of (count links - num-links) links [ die ]
SETUP-ERDOS-RENYI can also be written using the same idiom:
ask turtles [ create-links-with other turtles ]
ask links with [random-float 1.0 > probability] [ die ]
Compared to the code in the Code tab, this avoids the potentially confusing use of self > myself, but runs somewhat slower, especially if the linking probability is small.
EXTENDING THE MODEL
Use the layout-spring command, or one of the other layout-* commands, to give the network a visually pleasing layout.
RELATED MODELS
Network Example - how to dynamically create and destroy links Preferential Attachment and Small Worlds (found under Sample Models, not under Code Examples) - how to create some other kinds of networks Network Import Example - how to create a network based on data from a file
CREDITS AND REFERENCES
Comments and Questions
breed [nodes node] links-own [ weight ; the weight of the link ] to setup-simple-random clear-all ;; Make turtles set-default-shape turtles "circle" create-nodes number-of-nodes [ setxy random-xcor random-ycor ] ask nodes [ setxy random-xcor random-ycor ] ;; Now make links one at a time until we have enough while [count links < num-links] [ ;; Note that if the link already exists, nothing happens ask one-of turtles [ create-link-with one-of other turtles [ set weight (random 10) + 1 set label weight ] ] ] end to go end ; Public Domain: ; To the extent possible under law, Uri Wilensky has waived all ; copyright and related or neighboring rights to this model.
There are 2 versions of this model.
Attached files
No files
This model does not have any ancestors.
This model does not have any descendants.
David Weintrop
ideas for next steps
Hey Tim, Here is the start of a traveling salesman model. What type of supports would you like to provide your students to help them implement a traveling salesman algorithm? The simplest is probably what you have - a Go method where they would put their logic. I'm trying to think we else the model could have: maybe some display of how many of the nodes have been visited? Some visual cues for visited/not-visited nodes and/or traveled links? There could be some point-and-click logic letting students connect nodes that way. What are you thinking? let me know and together we can try and build out this model together.
Posted about 12 years ago
Tim Miller
Thanks and next steps
David, Thanks for the framework. My students are researching some different algorithms that can be followed to visit all the nodes while attempting to minimize the total distance traveled. After they find and understand the algorithms, they will create their own flowchart of logic that the algorithm will follow. The students that will be using NetLogo do not have any programming background, so they will need some guidance in implementing their algorithm. My goal for them is two-fold: understanding the idea algorithmic thinking to solve a problem, and developing some initial experience in writing code. I have shown my students this discussion board, and I want them to use it as a resource for developing their NetLogo model.
Posted about 12 years ago
Tina Conis
Model Idea
Hi, My name is Tina and I am interested in making a program for the Ant Colony Algorithm. I would like this program to be in NetLogo and have several turtles finding their way from point to point. I have no previous programming experience so I would like some help in making this program. Do you have any tips or know anyone who I could communicate with through email to help me in making the program?
Posted about 12 years ago
David Weintrop
A way to get started on a model
Hi Tina, I think an Ant Colony algorithm sounds pretty cool and that NetLogo would be a great tool for it. One way I often get started with new models is to look through the NetLogo models library for models that do something similar to what I want my model to do, then try and figure out how that model works. You can open the models library in NetLogo by clicking the Models Library menu item under the File menu. The models in the Code Examples are usually easier to understand the the other models, so I would start there. Maybe the "Move towards target Example" model could be useful, or the "Link-Walking Turtles Example" model. Also, there are a few models that have Ants walking around that could be useful, like the "Ants" and "Ant Lines" models. Hope that helps! Let me know if you have any more questions. Happy Modeling, David Weintrop
Posted about 12 years ago