Considere o seguinte problema.
Existem valores desconhecidos v 1 , ⋯ , v n ∈ R . A tarefa é encontrar o índice do maior usando apenas consultas do seguinte formulário. Uma consulta é especificada por um conjunto S ⊆ { 1 , ⋯ , n } e a resposta correspondente é max i ∈ S v i . O objetivo é usar o menor número possível de consultas.
Esse problema é fácil: podemos usar a pesquisa binária para encontrar o argmax com consultas . isto é, construa uma árvore binária completa com n folhas correspondentes aos índices. Comece pela raiz e desça até uma folha da seguinte maneira. Em cada nó, consulte o valor máximo nas subárvores direita e esquerda e, em seguida, vá para a criança ao lado com a resposta maior. Ao alcançar uma folha, produza seu índice.
A seguinte versão barulhenta desse problema surgiu em minha pesquisa.
Não há valores desconhecidos v 1 , ⋯ , v n . Estes podem ser acedidos com consultas em que um conjunto S ⊆ { 1 , ⋯ , n } é especificado e uma amostra a partir de N ( max i ∈ S v i , 1 ) é devolvido. O objectivo é o de identificar i * ∈ { 1 , ⋯ , n } de tal modo que E [ v i * ] usando o menor número de consultas possível. (A expectativa é superior à escolha de i ∗ , que depende das moedas do algoritmo e das respostas ruidosas da consulta.)
fonte
Respostas:
Desculpe, isso está meio cozido, mas espero que possa ser útil!
fonte