| The problem of diagnosing a complex system through a series of tests of its components arises in many practical situations. In many of these cases, testing a component is costly (it may cost money, take time, or incur pain on the patient, etc.), and therefore it is important to determine a best diagnosing policy which minimizes the expected cost of testing.; We consider complex systems, consisting of several components, in which the state of the system (e.g. working or failing, healthy or unhealthy, etc.) depends on the states of its components. We assume that this dependency is known, either by an explicit functional description, or via an oracle. The procedure of diagnosing such a system consists of testing the components one-by-one, until the state of the whole system is correctly determined.; We consider one frequently arising type of such problem, in which it is assumed that the cost of testing a component as well as the (a priori) probability that it is working correctly, are known in advance, and, the components are assumed to work or fail independently of each other. Since the inspection of the system is usually repeated many times it is customary to associate the expected cost to an inspection policy, and to consider the problem of finding a policy that minimizes the corresponding expected cost. This corresponds to the practical desire of minimizing the total cost in the long run.; This problem has many potential applications including but not limited to problems in communication networks, artificial intelligence, industrial engineering and medical diagnosis.; In this thesis, we give a thorough literature review, provide optimal polynomial time algorithms for certain types of systems, and propose heuristics for more general cases. We also report computational results. |
