Traveling Salesman Framework

No preview image

1 collaborator

Default-person David Weintrop (Author)

Tags

(This model has yet to be categorized with any tags)
Visible to everyone | Changeable by everyone
Model was written in NetLogo 5.0.2 • Viewed 615 times • Downloaded 36 times • Run 0 times
Download the 'Traveling Salesman Framework' modelDownload this modelEmbed this model

Do 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

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 over 11 years ago

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 over 11 years ago

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 over 11 years ago

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 over 11 years ago

Click to Run Model

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.

Uploaded by When Description Download
David Weintrop over 11 years ago latest version of the model Download this version
David Weintrop over 11 years ago Initial upload Download this version

Attached files

No files

This model does not have any ancestors.

This model does not have any descendants.