CODEWITHSUNDEEP
algorithmmathgraphstatisticstraveling-salesman
TheOne
TheOne

Reputation: 11159

How to calculate minimum expected time for searching a graph?

I have a simple graphing problem where I traverse a graph looking for an item. Each node in the graph has a probability n/100 of the item being there, where the sum of all the probabilities equals 1. How can I find the minimum expected time to search for the item in the entire graph?

The item is guaranteed to exist in only one node.

At first glance it seems like a traveling sales person problem and that is simple. Just get the permutations of the the paths and calculate the path for each and return the minimum.

But then it gets tricky when I need to find the minimum expected time. Is there any mathimatical formula that I could plug in on the minimal path to get the result?

ie: sum = 0
    for node in path:
        sum += node.prob * node.weight

Or is there something more complicated that needs to be done?

Upvotes: 0

Views: 1199

Answers (1)

corsiKa
corsiKa

Reputation: 82559

If all you're doing is looking for a particular item, then you're guaranteed to be at most n lookups.

If the item is 100% guaranteed to exist in the graph, and it will exist exactly once, then you'll find it after approximately n/2 searches. So (time to search one node) * (n / 2) is your expected time.

If you want a better answer than that you need more information.

Also, you should clarify what "each node in the graph has a probability n/100 of the item being there" means. This seems to indicate if I have 1 node in my graph, there's a 1/100 chance of it being on the node I check, but that if I have 100 nodes, I have a 100/100 chance. That, my friend, makes as much sense as a chimpanzee in a tutu.

Upvotes: 2

Related Questions