How to find optimal path visit every node with parallel workers complicated by dynamic edge costs?

Posted by Aaron Anodide on Programmers See other posts from Programmers or by Aaron Anodide
Published on 2012-10-25T22:02:18Z Indexed on 2012/10/25 23:15 UTC
Read the original article Hit count: 183

Filed under:

algorithms

|

trees

Say you have an acyclic directed graph with weighted edges and create N workers.

My goal is to calculate the optimal way those workers can traverse the entire graph in parralel.

However, edge costs may change along the way.

Example:

A -1-> B
A -2-> C
B -3-> C (if A has already been visited)
B -5-> C (if A has not already been visited)

Does what I describe lend itself to a standard algorithmic approach, or alternately can someone suggest if I'm looking at this in an inherently flawed way (i have an intuition I might be)?

© Programmers or respective owner

Related posts about algorithms

Finding a problem in some task [closed]

as seen on Programmers - Search for 'Programmers'
Recently I competed in nation wide programming contest finals. Not unexpectedly all problems were algorithmic. I lost (40 points out of 600. Winner got ~300). I know why I lost very well - I don't know how to find actual problem in those obfuscated tasks which are life-blood of every competition.… >>> More
Genetic algorithms

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm trying to implement a genetic algorithm that will calculate the minimum of the Rastrigin functon and I'm having some issues. I need to represent the chromosome as a binary string and as the Rastrigin's function takes a list of numbers as a parameter, how can decode the chromosome to a list of… >>> More
understanding evaluation function

as seen on Programmers - Search for 'Programmers'
I am developing a chess program. And have made use of an alpha beta algorithm and a static evaluation function. I have successfully implemented both but I want to improve the evaluation function by automatically tuning the weights assigned to its features. At this point am totally confused about the… >>> More
How to know whether to create a general system or to hack a solution

as seen on Programmers - Search for 'Programmers'
I'm new to coding , learning it since last year actually. One of my worst habits is the following: Often I'm trying to create a solution that is too big , too complex and doesn't achieve what needs to be achieved, when a hacky kludge can make the fit. One last example was the following (see paste… >>> More
How to implement a genetic algorithm with distance, time, and cost

as seen on Programmers - Search for 'Programmers'
I want to make a solution to find the optimum route of school visit. For example, I want to visit 5 schools (A, B, C, D, E) in my city. Then I must find out what school I should visit first, then the second, then the third etc. with distance, time, and cost criteria. The problem is, I am confused… >>> More

Related posts about trees

Paged binary trees vs. AVL trees and B-trees

as seen on Stack Overflow - Search for 'Stack Overflow'
How are paged binary trees different from AVL trees and B-trees? >>> More
Minimum and maximum height of binary search trees, 2-3-4 trees and B trees.

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, note this is not homework. But can anyone tell me how you find the min/max height of B trees, 2-3-4 trees and binary search trees? Thanks >>> More
Difference between B Trees and 2-3-4 Trees

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, Could someone please explain to me the difference between B Trees and 2-3-4 Trees? And also how would you find the maximum and minimum height of each? Thanks >>> More
B- trees, B+ trees difference

as seen on Stack Overflow - Search for 'Stack Overflow'
In a B- tree you can store both keys and data in the internal/leaf nodes. But in a B+ tree you have to store the data in the leaf nodes only. Is there any advantage of doing the above in a B+ tree? Why not use B- trees instead of B+ trees everywhere? As intuitively they seem much faster. I mean why… >>> More
What is the usage of Splay Trees in the real world?

as seen on Programmers - Search for 'Programmers'
I decided to learn about balanced search trees, so I picked 2-3-4 and splay trees. What are the examples of splay trees usage in the real world? In this Cornell: http://www.cs.cornell.edu/courses/cs3110/2009fa/recitations/rec-splay.html I read that splay trees are 'A good example is a network router'… >>> More