Binary search is not efficient with traversal costs. What is?

Binary search let me down when I tried to apply it to the real world. The scenario is as follows.

I need to test the range of a device that communicates over radio. Communication needs to occur quickly, but slow transmission is tolerable, up to a point (say, about 3 minutes). I need to test whether transmissions will be successful every 200 feet until failure, up to 1600 feet. Every 200 feet a test will be run which requires 3 minutes to execute.

I naively assumed that a binary search would be the most efficient method of finding the failure point, but consider a travel speed of 200 ft/min and test time of 3 minutes. If failure to transmit occurs at 500 feet, binary search is not the most efficient means of finding the failure point, as shown below.

enter image description here

Simply walking along and testing every single point would have found the solution sooner, taking only 12 minutes, whereas binary search & testing would take 16 minutes.

My question: How do you calculate the most efficient path to the solution when traveling time matters? What is this called (e.g., binary-travel search, etc.)?

Edit Report

Depending on what you actually want to optimise, there may be a way to work out an optimum search pattern. I presume you don't want to optimise the worst case time, because the slowest case for many search strategies will be when the break is at the very end, and binary search is actually pretty good here - you walk to the end without changing direction, and you don't make very many stops.

You might consider different binary trees, and perhaps work out the average time taken to work your way down to a leaf. Binary search is one sort of tree, and so is walking along and testing as you go - a very unbalanced tree in which each node has at least one leaf attached to it.

When following along such a tree you always start at one end or another of the line you are walking along, walk some distance before making a measurement, and then, depending on the result and the tree, either stop or repeat the process with a shorter line, where you are at one end or another of it.

This gives you something you can attack using dynamic programming. Suppose you have solved the problem for lengths of up to N segments, so that you know the cost for the optimum solutions of these lengths. Now you can work out the optimum solution for N+1 segments. Consider breaking the N+1 segments into two pieces in the N+1 possible ways. For each such way, work out the cost of moving to its decision point and taking a measurement and then add on the cost of the best possible solutions for the two sections of segments on either side of the decision point, possibly weighted to account for the probability of ending up in those sections. By considering those N+1 possible ways, you can work out the best way of splitting up N+1 segments, and its cost, and continue until you work out a best solution for the number of sections you actually have.

answered 2012-12-03T20:16:10.607

Binary search is not efficient with traversal costs. What is?

1 Answer

Your Answer