¿Cuál es el algoritmo más eficiente para determinar el ordenamiento relativo de un conjunto desconocido de valores?

Question

Esto viene de una pregunta sobre Arqade .

El fondo es que hay un nivel de centro comercial. Vlad, el jefe del crimen organizado quiere que se destruyan bienes del centro comercial por valor de 50.000 dólares. Tu tarea es disparar y volar cosas hasta que eso suceda.

Hay 12 tiendas en el centro comercial y tienes 3 granadas. Después de de volar las tres primeras tiendas, si no has arruinado cosas por valor de 50.000 dólares en tres explosiones, cambias a tu rifle y rompes las ventanas de las tiendas ventanas de las tiendas hasta llegar a ese límite. Entonces te vas.

Una buena y sana diversión.

El valor absoluto de los almacenes es desconocido, pero me interesa determinar el relativa Obviamente, quiero utilizar mis tres granadas donde sean más útiles. Tal como lo veo, tengo un conjunto de 12 variables desconocidas, que representan el valor de cada uno de los almacenes individuales:

$ {O,P,Q,R,S,T,U,V,W,X,Y,Z} $

y una constante $C$ que representa el valor de las ventanas.

Sé cuáles son las tres tiendas que he destruido y puedo contar cuántas ventanas tengo que disparar para que me den por cumplida la misión.

Conociendo sólo esos dos datos, debería ser posible, mediante la experimentación, ordenar el conjunto desconocido. Digamos que en la prueba nº 1 destruyo los almacenes X,Y,Z y me lleva 4 ventanas alcanzar los 50.000 dólares. En la prueba #2, destruyo las tiendas W,Y,Z y me lleva 3 ventanas.

Si $X + Y + Z + 4C = W + Y + Z + 3C$ entonces podemos decir que $W > X$ .

¿Cuál es la forma más eficiente de ejecutar este algoritmo para concluir las 12 tiendas? Cada prueba lleva unos 6 minutos y no quiero duplicar esfuerzos.

Answer 1

He aquí una buena solución matemática:

Realiza 12 pruebas, empezando por $O+P+Q$ entonces $P+Q+R$ entonces $Q+R+S$ etc., y para cada una de ellas registre el número de ventanas como un número entero negativo. Por ejemplo, $$\begin{align}O+P+Q&=-w_1\\ P+Q+R&=-w_2\\ Q+R+S&=-w_3\\ \vdots\\ X+Y+Z&=-w_{10}\\ Y+Z+O&=-w_{11}\\ Z+O+P&=-w_{12}\end{align}$$

Esto nos da un problema de matriz casi tridiagonal: $$\left[\begin{array}{cccccccccccc}1&1&1&0&0&0&0&0&0&0&0&0\\ 0&1&1&1&0&0&0&0&0&0&0&0\\ 0&0&1&1&1&0&0&0&0&0&0&0\\ &&&\ddots&\ddots&\ddots&\\ 0&0&0&0&0&0&0&0&0&1&1&1\\ 1&0&0&0&0&0&0&0&0&0&1&1\\ 1&1&0&0&0&0&0&0&0&0&0&1\\ \end{array}\right]\left[\begin{array}{c}O\\P\\Q\\R\\S\\T\\U\\V\\W\\X\\Y\\Z\end{array}\right]=\left[\begin{array}{c}-w_1\\-w_2\\-w_3\\\vdots\\-w_{10}\\-w_{11}\\-w_{12}\end{array}\right],$$ que puede utilizar su paquete favorito para resolver, o calcular la inversa real por adelantado si va a hacer esto muchas veces.

Esto le dará valores negativos para cada tienda, y los mayores (es decir, los menos negativos) son los valores más altos.

Creo que no es posible conocer todos los valores de los almacenes en menos de 12 pruebas. Tal vez sea posible determinar los 3 valores más grandes en menos de 12 pruebas, pero no tengo ese algoritmo a mano.