Seleção on-line barata com comparações ponderadas

Suponha que desejamos encontrar o menor elemento de um conjunto , cujos elementos são indexados de a . Não temos acesso aos valores desses elementos, mas podemos comparar quaisquer dois elementos de para ver qual é menor. Para quaisquer índices e , existe um associado custo para comparar o th e th elementos de . A matriz de custos completa é fornecida antecipadamente. $S$ $1$ $n$ $S$ $i$ $j$ $C_{i,j}$ $i$ $j$ $S$ $C_{i,j}$

É bem sabido que a comparações são necessárias e suficientes para encontrar o mais pequeno elemento de . No entanto, como cada comparação pode ter um custo diferente, também queremos manter o custo total das comparações o menor possível. $n-1$ $S$

Existe um algoritmo online que encontra uma sequência de comparações de pequeno custo total que encontra o menor elemento de ? $S$ Não existe um algoritmo online que encontre o conjunto de comparações com custo total mínimo , mesmo quando , mas talvez exista um algoritmo online com pequena razão competitiva. $n=3$

Em particular, permitir que o algoritmo online realize mais que comparações ajuda? É melhor fazer várias comparações baratas "extras" em vez de algumas comparações caras? $n-1$

Estou especialmente interessado no caso , em que é uma métrica discreta sobre o conjunto e , por tudo que . Um algoritmo on-line ideal ainda é impossível nessa configuração. $C_{i,j} = 4^{d(i,j)}$ $d$ $S$ $0 \le d(i,j) \le k$ $i,j$

Todas as referências a problemas semelhantes são apreciadas. Não estou procurando alguém para resolver meu problema (embora algumas idéias possam ajudar e serem apreciadas). Eu só quero saber se esse problema é conhecido. (Não consegui encontrar nada.)

cc.complexity-theory ds.algorithms reference-request online-algorithms George
fonte

Espere, agora estou confuso. Se você conhece os valores e os custos de comparação aos pares com antecedência, minimizar o custo total da comparação é equivalente a calcular uma arborescência de custo mínimo em um gráfico direcionado acíclico completo. Mas se você não conhece os valores, mas apenas descobre sua ordem realizando comparações, não há estratégia on-line que sempre encontre o menor elemento usando comparações de custo total mínimo; um adversário inteligente pode forçá-lo a desperdiçar dinheiro. Em qual versão você está interessado?

Jeffε

Ok, talvez eu não tenha esclarecido minha pergunta o suficiente. Os valores são desconhecidos e são "revelados" por comparações (na verdade, digamos, comparações retornam apenas se um objeto for maior, igual ou menor que outro). Então, eu estou interessado na segunda versão. Btw nunca ouviu falar da arborescência de custo mínimo. Pelo menos eu aprendi algo novo.

George

Você deve editar sua pergunta para tornar esse ponto explícito. Para responder às suas breves perguntas: Não sei se o problema já é conhecido, mas executar o conjunto ideal de comparações on-line não é NP-completo, porque é impossível (a menos que ). O melhor que você pode esperar é uma pequena taxa competitiva.

n = 2

$n=2$

Jeffε

Editado para maior clareza (espero) e para enfatizar que esta é uma questão de algoritmos on - line . Verifique se eu não estraguei muito a declaração do problema!

Jeffε

Isso é muito melhor! Muito obrigado. Também adicionei que a distância entre dois objetos é limitada acima por algum número inteiro k.

George

Respostas:

A análise de casos de força bruta revela que a razão competitiva ideal para o caso especial , sem outras restrições na matriz de custos, é a proporção áurea . Portanto, nenhum algoritmo on-line pode alcançar uma taxa competitiva melhor que . $n=3$ $\phi = (\sqrt{5}+1)/2$ $\phi$

Suponha que , e . $C_{1,2}=0$ $C_{1,3}=1$ $C_{2,3}=\phi$

Sem perda de generalidade, o algoritmo começa comparando a , ao custo zero. $S_1$ $S_2$
O adversário declara . $S_1 > S_2$
Se o algoritmo comparar a : $S_1$ $S_3$
- O adversário declara . $S_1 > S_3$
- O algoritmo deve comparar e . $S_2$ $S_3$
- O adversário declara , então é o mínimo. $S_2 < S_3$ $S_2$
- O custo total das comparações do algoritmo é . $1+\phi$
- O adversário revela a ordem total . $S_2 < S_3 < S_1$
- O custo total das comparações ideais ( e ) é . $S_1>S_2$ $S_2<S_3$ $\phi$
Se o algoritmo comparar a : $S_2$ $S_3$
- O adversário declara , então é o mínimo. $S_3 > S_2$ $S_2$
- O custo total das comparações do algoritmo é . $\phi$
- O adversário revela a ordem total . $S_2 < S_1 < S_3$
- O custo total das comparações ideais ( e ) é . $S_1>S_2$ $S_1<S_3$ $1$
Nos dois casos, as comparações do algoritmo custam um fator de mais do que o conjunto ideal de comparações para a ordem total revelada. $\frac{1+\phi}{\phi} = \frac{\phi}{1} = \phi$

Em termos mais gerais, a taxa competitiva é , em que é os três custos de comparação. (Há mais casos a serem considerados aqui, porque existem algoritmos ideais que não realizam a comparação mais barata primeiro, mas a análise de casos ainda é elementar.) Cálculos tediosos implicam que a expressão é maximizado quando , e . $\min\{\frac{a+c}{a+b} , \frac{a+b+c}{a+c}\}$ $a\le b\le c$ $\min\{\frac{a+c}{a+b} , \frac{a+b+c}{a+c}\}$ $a=0$ $b=1$ $c=\phi$

Em particular, se , o melhor algoritmo possível pode ser forçado a executar as três comparações. $\frac{a+c}{a+b} > \frac{a+b+c}{a+c}$

Jeffε
fonte

Esse é um primeiro passo muito bom! Obrigado por seu interesse em meu problema (parece que você está ainda mais interessado do que eu :))

George

Boa observação. Apenas para observar, essa análise assume um algoritmo determinístico, a menos que eu esteja enganado.

Tsuyoshi Ito

Sim está certo. Um algoritmo aleatório pode se sair melhor (na expectativa, contra um adversário alheio).

Jeffε

-3

Um começo é:

Classifique todos os elementos da sua matriz de custos C
Faça a comparação de menor custo primeiro, colocando o perdedor no conjunto NOPE
Para cada comparação de custo subsequente, se um dos dois elementos estiver no NOPE, não faça a comparação
Você precisa continuar até que todos, exceto um elemento, estejam no NOPE, que são comparações n-1.

Esse é um algoritmo decente? Depende do custo relativo da classificação C vs. comparações em S:

Para qualquer item que você está avaliando, se houver uma comparação mais barata que a atual, ela já foi executada e o item atual venceu essa comparação
Custo == n ^ 2 comparações numéricas para classificar C, mais n-1 comparações de S

-t.

Tristan Reid
fonte

Sim, este é um algoritmo óbvio e ganancioso. Não, o custo é a soma dos custos das comparações individuais realizadas pelo algoritmo, conforme fornecido pela matriz .

C_{i, j}

$C_{i,j}$

Jeffε

Obrigado! Eu já pensei sobre essa abordagem óbvia e gananciosa (que é o que vou usar se nada melhor surgir). O problema é se isso garante a relação competitiva.

George

@JeffE - sim, o custo é o n-1 comparações com seus custos associados, mas também o custo de classificar a matriz de custo

Tristan Reid

@ George B. - Se o custo da classificação C for relativamente barato, não acho que exista um algoritmo melhor para isso. Esse algoritmo sempre executará exatamente comparações n-1, nunca 1 a mais ou 1 a menos. As comparações realizadas sempre serão as n-1 mais baratas. Eu acho que a ganância é boa ...

Tristan Reid

Não, nem sempre serão os mais baratos. Por exemplo, deixe A> B> C e = 1, = 2 = 1. Se você comparar primeiro e e depois comparar e o custo total será 4 ^ 1 + 4 ^ 2 = 20, enquanto que se você comparar a e depois a o custo será 4 ^ 1 + 4 ^ 1 = 8, portanto, um algoritmo ganancioso não trabalho aqui. E sim, classificar C não é um problema.

d_{(} A, B)

$d_(A,B)$

d_{(} A, C)

$d_(A,C)$

d_{(} B, C)

$d_(B,C)$

A

$A$

B

$B$

A

$A$

C

$C$

B

$B$

C

$C$

A

$A$

B

$B$

George