1

I am looking for description (name of algorithm, code, pseudocode, etc.) that can help me frame this problem and find the appropriate recursion and the most efficient solution.

Problem:
Given a graph with weighted nodes and a starting node, I want to generate a weight-ordered list of nodes that are lying on a path that starts at the starting node and then proceeds by jumping to the next adjacent unvisited highest-value node, then to the next etc. until it can no longer continue (e.g. no adjacent nodes, no unvisited adjacent nodes, or all nodes were visited already once).

Am I correctly assuming that this is a variation on the traveling salesman problem? Any suggestions or pointers would be greatly appreciated. Algorithms just aren't my area of expertise...


Update from comments: This is not a homework question. ... There's actually years of empirical research behind simply being able to frame seemingly random mammalian behavior as an algorithmic problem. ... Without tackling these group dynamics algorithmically I will not be able to expand testing beyond my initial sample and unfortunately, regression analysis just won't do the trick.

  • Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask – gnat Jan 13 '14 at 10:42
  • 1
    This question appears to be off-topic because reads like it is posting a homework question for other people to solve. – GlenPeterson Jan 18 '14 at 3:17
  • Let me assure you it's not a homework question. Though I am quite pleased to learn that I managed to distill it down to something that could be seen as such. There's actually years of empirical research behind simply being able to frame seemingly random mammalian behavior as an algorithmic problem. However, my objective is not to find an algorithm. Without tackling these group dynamics algorithmically I will not be able to expand testing beyond my initial sample and unfortunately, regression analysis just won't do the trick... – phaedrus Jan 18 '14 at 11:13
2

If I understand correctly then no, this isn't a variation on the TSP. It's a pretty straight forward greedy algorithm.

Here is some psuedocode:

List visited = {}

Main(Node startNode)
  FindPath(startNode)
  sort(visited)

FindPath(Node node)
  visited.addNode(node)
  neighbours = node.getAdjactentNodes()
  neighbours.subtract(visited)
  if(neighbours.isEmpty())
    // all adjacted nodes are visited
    return
  else
    sort(neighbours)
    FindPath(neighbours.First())
  end if

So -- what's happening here?

We are creating a list to hold all the nodes we've visited on our journey.

In FindPath: We then visit the node, we add it to the list of visited nodes and ask it for a list of neighbours. If there are no adjacent nodes then we are finished (no more nodes to visit). If there are adjactent nodes we sort them by weight and pass the biggest to FindPath.

When the FindPath function bottoms out (eventually we end up on a node that we can't jump anywhere from) we are left with all the nodes we've visited in the visited list and so then we just need to sort it by weight.

Hope that helps.

  • Thanks! This is very helpful indeed. I hadn't thought of just "bringing the list along for the ride" so to speak... – phaedrus Jan 18 '14 at 17:25

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.