Here is an imgur folder with the projects description (my apologies for the awfully wrinkled paper): http://imgur.com/a/a2vQM

There are a set of pegs, numbered from 0 to n - 1. Each peg can have a connection to another peg with a rubber band.

Basically, the program is given an adjacency list with all of the pegs and the ones they connect to. The idea of the project is to come up with an algorithm that returns a permutation with the all of the rubber bands stretching the least distance.

It's my understanding that this program will take a long time to run. Our teacher implied that the algorithm should run multiple times to get the best answer; each result of the algorithm should improve the overall "cost". (The cost is the distance spanned by all of the rubber bands, measured in pegs. For example, a set of 5 pegs in numerical order that has one rubber band between peg 1 and 3 has a cost of 2). I've been struggling to come up with an algorithm that returns a "good" result. What I need is an algorithm that, when run an infinite amount of times, will improve the cost each time. If anyone recognizes the problem or has any suggestions, please let me know. Thanks!

  • 1
    $\begingroup$ I don't understand the problem. What do you mean by "all of the rubber bands stretching the least distance"? Do you want to minimize the sum of the stretches (known as minimum linear arrangement) or the maximum stretch (known as minimum bandwidth)? $\endgroup$ – Yuval Filmus Jun 6 '17 at 22:12
  • $\begingroup$ im sorry, the way it was worded is vague. Basically, given an undirected graph, the goal is to find a linear permutation of the nodes in which the edges will span the least total distance. I believe the result should be a minimum linear arrangement. Our teacher indicated that the best result might be found using evolutionary computation, but I'm struggling to find a way to improve the permutation without taking a large amount of time. $\endgroup$ – dan d Jun 6 '17 at 22:49
  • $\begingroup$ I encourage you to edit the question so it is clear. (What is meant by "spanning the least total distance"? Are you trying to minimize the sum of the edges? How does the permutation affect the collection of edges and their total distance?) We want it to read well for someone who encounters the question, and people shouldn't need to read the comments to understand what you are asking. Thank you -- and welcome to CS.SE! $\endgroup$ – D.W. Jun 7 '17 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.