Please take me out of here!

This problem is a simplified version of the Sophie problem we found on Facebook.

In Lazyville a company called UnreliableLifters is responsible for the maintainance of all the elevators of the city.

UnreliableLifters is now going through major financial problems, and to reduce costs they decided to replace the precise fault notification system they had earlier with a simpler one, which can only tell you there is a problem in one elevator of the network, without giving a hint about WHERE the problem is. The idea then is to use faults statistics and first visit the most faulty location, then the second one, and so on.

Yesterday you signed the contract with UnreliableLifters as repairman, and today is your first day at work. You know company CEO is out for an inspection round, and an emergency occurs: you are notified there is an elevator which is stuck somewhere, potentially with the CEO inside!!

You suspect the strategy suggested by the company (visit locations according to decreasing fault probabilities) is not always the best one possible to minimize expected latency and, to impress company's CEO (as well as to train for the Algorithms exam), you decide to study the problem a little bit better to come up with an optimal solution.

In what follows we try to provide you some definitions and structures to succeed in this attempt.

Graphs

A graph is an ordered pair G = (V, E) comprising a set V of nodes V={1,...n}, together with a set E of edges, which are 2-element subsets of V. If {u,v} belongs to E it means there is a connection between the node u and the node v of G.
A graph is called complete if all nodes in V are pairwise connected in E.
A path P[u,w] from u to w in the graph G is a subset of E that connects u to w by visiting intermediate nodes only once. A path that goes through all nodes exactly once is called hamiltonian.

Why do we need graphs?

Because they model the problem quite efficiently: nodes are representing elevators, and since you can move freely from one to another, elevators map is well represented as a complete graph.
If you decide to reach elevator3 from elevator1 but going thorugh elevator2 first, the path connecting elevator3 to elevator1 is represented with edges {elevator1,elevator2} and {elevator2,elevator3}.

Weighted Graphs

A weighted graph G=(V, E, C) is a graph G'=(V, E) extended with a cost function C such that C({u,v}) is a natural number representing the cost of traversing the edge {u,v}, for all {u,v} in E.
The notion of path is extended by considering its weighted version: the cost C(P) of a path P is the sum of all costs of edges in P

Why do we need weights?

Weighted Graphs extend our previous formalism and allow you to include the time it takes to move between two elevators in the model.

Weighted Graphs with Probabilities

A weighted probabilistic graph G=(V, D, E, C) is a weighted graph G'=(V, E, C) in which a probability distribution D is defined over the set of nodes V. This means that for all nodes v in the set V, 0<D(v)<1, and the sum of all D(v)s is exactly 1.

Why including probabilities?

This is the last aspect of the problem you have to include in the model, the fault probability of elevators.

Formal definition of the problem

Now the problem can be formally stated in this way: the expected latency of an hamiltonian path P is defined in this way: suppose that P visits the nodes of G in the order {v1,v2,...,vn}, then the expected latency EL(P) of P is the sum of the weighted latencies of all paths in P from v1 to all other nodes, namely:
EL(P)=C(P[v1,v2])*D(v2)+C(P[v1,v3])*D(v3)+...+C(P[v1,vn])*D(vn)

So our problem is defined as follows: given an weighted probabilistic graph G, find a hamiltonian path in G departing from the node 1 that has the minimal expected latency.

In this context always departing from node 1 means the company's headquarter is inside a building which has an elevator of the newtwork.

Solving the problem in three ways

What we gave so far is the general problem definition. Your task is now finding an algorithmic soluton for it, by exploiting three different algorithmic techniques according to the following mandatory guidelines.

Credits

Most of the explanations are based on materials found on Wikipedia.com

For a more formal introduction to graphs please refer to: