A chuva nunca estuda, por isso ela é completamente ignorante durante o meio do período, mesmo que consistindo apenas de perguntas Sim / Não. Felizmente, o professor de Rain permite que ela retome o mesmo intermediário quantas vezes quiser, mas ele apenas reporta a pontuação, para que Rain não saiba quais problemas ela errou. Como o Rain pode obter todas as respostas corretas ao refazer o exame um número mínimo de vezes?
Para ser mais formal, o exame tem um total de Perguntas Sim / Não, cuja resposta correta é . Quero encontrar uma estratégia que minimize o número esperado de vezes que o Rain precisa refazer o exame.
Eu tenho pensado nisso por um tempo. Quando Rain faz o teste intermediário pela primeira vez, sua pontuação sempre terá uma distribuição de , independentemente da resposta, portanto cada estratégia diminui a mesma quantidade de entropia. Eu não tenho idéia do que isso significa, no entanto. Isso significa que qualquer palpite aleatório é tão bom quanto responder a todos os "Sim" ou todos os "Não"?
Embora essa não seja uma questão de lição de casa, pretendo basear meu próximo projeto de pesquisa em torno dele, então
- Forneça algumas dicas em vez de uma resposta completa;
- Se esta pergunta já foi respondida, por favor me dê um ponteiro.
Respostas:
Isso é semelhante ao jogo Mastermind .
Há muita literatura sobre esse tópico. Para esse caso específico (4 perguntas com cada 6 opções), várias estratégias foram elaboradas para reduzir o número médio de tomadas para um pouco acima de 4,3.
Você pode escolher uma dessas estratégias ou fazer uma nova e aplicá-la ao caso den perguntas com 2 opções, qual é a sua situação. A pergunta é muito ampla para fornecer uma resposta detalhada aqui.
fonte
Esse é um problema de otimização em que você procura encontrar um desconhecidon número binário de-dígitos de suposições, em que o feedback dessas suposições é que você recebe o número de dígitos corretos. Isso é essencialmente apenas Mastermind binário , que também é examinado em um problema computacional chamado "otimização de caixa preta" (ver, por exemplo, Doerr et al 2001 ).
fonte
Como outros já disseram, o problema é muito parecido com o jogo Mastermind. Suponha que as respostas corretas sejam variáveis bináriascEu para i = 1 , … , n e que Rain faz o teste k vezes, às vezes j respondendo xi , j ao Eu quinta questão (i ≤ n , j ≤ k ) A resposta total correta para oj é a quinta vez Tj .
O que se segue são apenas algumas observações e notas, com base na solicitação explícita do OP para fornecer apenas algumas dicas sobre o problema.
Observe que um limite inferior "teórico da informação" fácilk para uma configuração genérica de respostas corretas é k ≥ O ( n / logn ) : cada teste fornece à Rain um número 0 ≤Tj≤ n , o que equivale a ≤ logn conhecimento, enquanto o conhecimento necessário para conhecer todas as respostas é ~n (por causa do n perguntas binárias).
No caso geral, você pode definir variáveiszYEu e zNEu ser estar 0 0 ou 1 1 respectivamente se o Eu -a resposta correta é Sim ou Não. Dessa forma, seu problema é determinar o ponto de respostas corretas em um espaço linear "discreto" da dimensão 2 n : para ver por que considerar que, pela definição acima de variáveis, você tem as restrições
zYEu+zNEu= 1
Além disso, no seuj -ª realização do exame, você está testando uma combinação linear dessas variáveis e sabe que a soma delas é Tj :
∑i = 1nzY/ NEu=Tj
Isso destaca que é trivial resolver esse problema emn consultas, porque ao fazer o teste k vezes que você tem n + k equações que definem um ponto em um 2 n espaço dimensional, para que, se você for inteligente o suficiente para não fazer consultas redundantes (apenas altere suas respostas uma de cada vez), poderá realizar apenas n vezes o teste.
Em casos específicos (como quando a relação sim / não é particularmente desequilibrada), deve ser fácil criar heurísticas particularmente adequadas: suponha que, por exemplo, você saiba que existe apenas uma resposta Sim em todo o questionário. Você pode encontrá-lo em apenasregistron consultas por bissecção padrão nos conjuntos de respostas. Além disso, você pode verificar se está nesse caso emitindo uma primeira consulta "tudo sim" (nesse caso)T1 1= 1 )
Generalizando a ideia no ponto anterior, se o número de respostas Sim forC (suponha C≤ n / 2 ) (e isso pode ser conhecido por uma única consulta), você está basicamente pesquisando um conjunto de tamanhos C dentro de um conjunto de tamanho n (portanto, existem (nC) ≃nC ) e sua consulta consiste em conhecer a cardinalidade da interseção de um conjunto S de sua escolha com o referido conjunto de perguntas Sim, que eu acho que é um problema muito mais estudado e você provavelmente pode encontrar muitas referências sobre ele.
Ligue para o aparelho que você está procurando (respostas Sim)Y . Com uma única consulta, você pode conhecer sua cardinalidade| Y| =m . Agora, um conjunto selecionado aleatoriamenteS usado como consulta permite conhecer a cardinalidade dos dois subconjuntos |Y∩ S| =t e |Y∩Sc| =m-t , e seu problema original foi reduzido para dois subproblemas com aproximadamente a metade do tamanho (também o número de respostas Sim procuradas geralmente será dividido pela metade a cada iteração). Não vou escrever detalhes explícitos, mas é apenas uma questão de cálculos simples de probabilidade.
Explorando a observação acima, você deve criar um algoritmo probabilítico que resolva o subproblemaP( m , n ) ≃ ≤ 1 + 2 ∗ P( m / 2 , n / 2 ) , o que deve proporcionar a você um limite de O ( m logn ) . A criação de um algoritmo determinístico para esse problema pode ser feita usando a técnica das expectativas maximizadas, mas não posso prever se funcionaria ou não.
fonte
Deseja minimizar o número máximo de repetições? ou minimizar o número esperado de retomadas?
Você pode criar estratégias muito diferentes, dependendo da qual deseja analisar.
Uma abordagem ingênua do primeiro passo levaria atén + 1 vezes e consistiria em fazer o teste pela primeira vez e, na segunda vez, alterar apenas a primeira resposta. Se a pontuação subir, mantenha a nova resposta; se diminuir, volte para a primeira resposta para todo o futuro. passos. Na 3ª vez (2ª repetição), altere apenas a 2ª resposta, etc.
Agora você pode começar a comparar outras estratégias a essa. Se na 2ª vez do teste 2 respostas forem alteradas, se a pontuação for alterada, sabemos as respostas corretas para 2 perguntas e salvamos uma etapa, mas se alteramos uma para a correta e a outra para a errada, a pontuação será alterada. não muda e não sabemos qual alteração estava correta até fazermos o exame uma terceira vez, alterando apenas uma delas (mas isso também nos dirá sobre a outra), então 1 ou 2 tentam obter 2 respostas (50% chance de cada), o que reduzirá o número esperado de repetições, mas provavelmente manterá o máximo no mesmo.
Agora você pode examinar outras estratégias e ver como elas se comparam (altere as 3 primeiras respostas, altere as primeirasn2 etc.).
fonte