?

Log in

No account? Create an account
Graphical Models of Probability
Bayesian Networks, Decision Networks, and Probabilistic Relational Models
traveling salesman with a twist 
2nd-Jun-2005 12:20 am
kid
So here is a problem.

Imagine you have a list of cities that a salesman wants to visit, each on a particual date or range of dates.
You know, Moscow: June 1-3; Tokio: June 17; New York: June 19-25, etc. Well, technically instead of ranges I have probability distributions over the dates when the "conference" of interest for the traveling salesman occurs...

Also here is a list of transit station which the salesman can travel through: Paris, Singapour, Washington, whatever.

All these Cities can be I guess arranged in a simple graph bu what is important not every city is connected to another one, there is a network of "railroads" connecting those (I know, there is no railroad between Tokio and New York, but let it be :)). Of course those railroads have lengths (cost functions, and those are probabilistic) associated with those.

What the salesman needs is an optimal path that would make it possible to make o all those conferences or meetings by the dates specified (and i does not matter, what transition he is taking, but it should make sence in terms of lengths of the paths between those cities, that is, he should be choosing the paths hat would make "perfect timing" for him.

I am pretty sure this is a well known "classic" problem, but what is the "classic" name for the problem?
I would really appreciate if you could help me categorize the problem so that I would know where to start my search for an appropriate algorithm.

Thanks guys!

UPDATE: It appears that Hidden Markov Models (which could be actually implemented as a special case of Bayes Nets) provide a nice framework to deal with my problem.
Comments 
13th-Aug-2005 03:20 am (UTC)
This is the traveling salesman problem, the classic NP-complete problem, which means that it's equivalent in complexity (and indeed reducible to!) to factoring large numbers or the knapsack problem.
This page was loaded Sep 22nd 2017, 9:40 am GMT.