Selección en línea barata con comparaciones ponderadas

Supongamos que queremos encontrar el elemento más pequeño de un conjunto , cuyos elementos están indexados de a . No tenemos acceso a los valores de estos elementos, pero podemos comparar cualquiera de los dos elementos de para ver cuál es más pequeño. Para cualquier índices y , hay un asociado costo para comparar el ésimo y ésimo elementos de . La matriz de costos completa se nos proporciona por adelantado.$S$$1$$n$$S$$i$$j$ $C_{i,j}$$i$$j$$S$$C_{i,j}$

Es bien sabido que los comparaciones son necesarias y suficientes para encontrar el elemento más pequeño de . Sin embargo, dado que cada comparación puede tener un costo diferente, también queremos mantener el costo total de las comparaciones lo más pequeño posible.$n-1$$S$

¿Existe un algoritmo en línea que encuentre una secuencia de comparaciones de costo total pequeño que encuentre el elemento más pequeño de ? $S$ No existe un algoritmo en línea que encuentre el conjunto de comparaciones con un costo total mínimo , incluso cuando , pero quizás haya un algoritmo en línea con una pequeña relación competitiva. $n=3$

En particular, ¿es útil permitir que el algoritmo en línea realice más que comparaciones? ¿Es mejor hacer varias comparaciones baratas "adicionales" en lugar de algunas comparaciones costosas?$n-1$

Estoy especialmente interesado en el caso , donde d es una métrica discreta sobre el conjunto S , y 0 ≤ d ( i , j ) ≤ k , para todos i , j . Un algoritmo en línea óptimo todavía es imposible en esta configuración.$C_{i,j} = 4^{d(i,j)}$$d$$S$$0 \le d(i,j) \le k$$i,j$

Cualquier referencia a problemas similares es apreciada. No estoy buscando a alguien para resolver mi problema (aunque algunas ideas pueden ayudar y son apreciadas). Solo quiero saber si se conoce este problema. (No pude encontrar nada)

El análisis de casos de fuerza bruta revela que la proporción competitiva óptima para el caso especial , sin otras restricciones en la matriz de costos, es la proporción áurea ϕ = ( $n=3$. Por lo tanto, ningún algoritmo en línea puede lograr una relación competitiva mejor queϕ.$\phi = (\sqrt{5}+1)/2$$\phi$

Suponga que , C 1 , 3 = 1 y C 2 , 3 = ϕ .$C_{1,2}=0$$C_{1,3}=1$$C_{2,3}=\phi$

• Sin pérdida de generalidad, el algoritmo comienza comparando con S 2 , a un costo cero.$S_1$$S_2$

• El adversario declara .$S_1 > S_2$

• Si el algoritmo compara con S 3 :$S_1$$S_3$

  • El adversario declara .$S_1 > S_3$
  • El algoritmo debe comparar y S 3 .$S_2$$S_3$
  • El adversario declara , entonces S 2 es el mínimo.$S_2 < S_3$$S_2$
  • El costo total de las comparaciones del algoritmo es .$1+\phi$
  • El adversario revela el orden total .$S_2 < S_3 < S_1$
  • El costo total de las comparaciones óptimas ( y S 2 < S 3 ) es ϕ .$S_1>S_2$$S_2<S_3$$\phi$

• Si el algoritmo compara con S 3 :$S_2$$S_3$

  • El adversario declara , entonces S 2 es el mínimo.$S_3 > S_2$$S_2$
  • El costo total de las comparaciones del algoritmo es .$\phi$
  • El adversario revela el orden total .$S_2 < S_1 < S_3$
  • El costo total de las comparaciones óptimas ( y S 1 < S 3 ) es 1 .$S_1>S_2$$S_1<S_3$$1$

• En cualquier caso, las comparaciones del algoritmo cuestan un factor de más que el conjunto óptimo de comparaciones para el orden total revelado.$\frac{1+\phi}{\phi} = \frac{\phi}{1} = \phi$

En términos más generales, la relación competitiva es , dondea≤b≤cson los tres costos de comparación. (Hay más casos a considerar aquí, porque hay algoritmos óptimos que no realizan la comparación más barata primero, pero el análisis de casos sigue siendo elemental). Los cálculos tediosos implican que la expresiónmin{a+$\min\{\frac{a+c}{a+b} , \frac{a+b+c}{a+c}\}$$a\le b\le c$se maximiza cuandoa=0,b=1yc=ϕ.$\min\{\frac{a+c}{a+b} , \frac{a+b+c}{a+c}\}$$a=0$$b=1$$c=\phi$

En particular, si , el mejor algoritmo posible puede verse obligado a realizar las tres comparaciones.$\frac{a+c}{a+b} > \frac{a+b+c}{a+c}$

Un comienzo es:

1. Ordenar todos los elementos de su matriz de costos C
2. Realice primero la comparación de costo más baja, colocando al perdedor en el juego NOPE
3. Para cada comparación de costos posterior, si alguno de los dos elementos está en NOPE, no realice la comparación
4. Debe continuar hasta que todos los elementos menos uno estén en NOPE, que son las comparaciones n-1.

¿Es este un algoritmo decente? Depende del costo relativo de clasificar C frente a hacer las comparaciones en S:

• Para cualquier elemento que esté evaluando, si hubo una comparación más barata que la actual, ya se realizó, y el elemento actual ganó esa comparación
• Costo == n ^ 2 comparaciones numéricas para ordenar C, más n-1 comparaciones de S

-t.