-
resistors gone wild
Date: 10/07/06 (Algorithms) Keywords: no keywords
Was having coffee at a Starbucks last weekend with a friend, when we met an electrical engineer. We got talking and in the course of our conversation, he mentioned a problem that had been bugging him for more than a year now.
Imagine you've a 2-d (MxN) grid of resistors, all of which have the same value. You're only provided with a finite number (say k) of probing points that are located at the boundary. You can attach wires to them and measure some network stats like current, voltage etc., I've illustrated this with a diagram, with some of the probing points indicated by arrows.
It's a finite grid and you know the topology of the network. Now the funda is that somewhere, some resistor/resistors have shorted. You can't muck around the network in any manner. Is there a way to diagnose which resistors have gone "bad" solely from the readings from the probing points?
Please share your thoughts on what you think of this solution.
It's definitely possible to know what resistor(s) have gone bad. Consider a NxN grid. The number of possible probing points at the periphery is 4N. Now during each probing phase we have to chose any 2 points and measure the current, etc., The number of choices at our disposal is 4N choose 2 which is O(n^2). This is cuz n Choose k, when k is a constant, is polynomial in k.
The number of unique scenarios covered by a set of O(n^2) possible probe readings is 2 exp O(n^2). Also the number of possible ways that the resistors in the grid could go bad is equal to the number of all possible subsets of resistors which is also equal to 2 exp (n^2) - cuz there are n^2 resistors in the grid. Thus taking repeated probe readings from the probing points on the periphery will eventually lead to a diagnosis of the problem.
Now the question is what is the number of probing readings one needs to take in order to diagnose a problem. It is of order O(n^2). This is cuz we can traverse a binary tree of possible scenarios - which we mentioned has 2 exp O(n^2) nodes, to arrive at a solution and O(n^2) is the depth of the tree.
Thus the problem of finding out the faulty resistor(s) in a resistor grid using a set of probing points at the periphery, takes quadratic time.
Source: http://community.livejournal.com/algorithms/84619.html
| « C++ Simulator of a Post... | || | kj » |