Esiste un algoritmo per trovare un oggetto che corrisponde a determinate proprietà, come un gioco di 20 domande?

Question

una domanda su 20 domande giochi è stato chiesto here:

Tuttavia, se sto comprensione correttamente, le risposte sembrano dare per scontato che ogni domanda andrà giù un albero gerarchico ramificazione. Un albero binario dovrebbe funzionare se il gioco è andato in questo modo:

1. E 'un animale? Sì.
2. È un mammifero? Sì.
3. È un felino? Sì.

Perché il felino è un esempio di un mammifero e il mammifero è un esempio di un animale. Ma cosa succede se le domande vanno così?

1. È un mammifero? Sì.
2. È un predatore? Sì.
3. Ha un naso lungo? No.

Non è possibile diramare un albero con questo tipo di domande, perché ci sono molti predatori che non sono mammiferi. Quindi non puoi fare in modo che il tuo programma si limiti a mammiferi e i predatori siano un sottogruppo di mammiferi.

Quindi c'è un modo per utilizzare un albero di ricerca binario che non sto capendo o esiste un algoritmo diverso per questo problema?

Giusto per chiarire, sto usando solo 20 domande come esempio, quindi la mia domanda riguarda questo tipo di problema di ricerca in generale, non altri problemi coinvolti in particolare in un gioco di 20 domande.

Answer 1

È paragonato a una ricerca binaria in cui ogni domanda è sì/no, quindi ogni risposta separa il set rimanente in due parti. Tuttavia, il set di dati sarebbe probabilmente non essere memorizzato in un albero binario effettivo, perché come ti rendi conto, che funzionerebbe solo se le domande sono state sempre poste nello stesso ordine della dimensione di divisione dell'albero.

Inoltre, è possibile avere facilmente più di 20 dimensioni ("proprietà") su cui suddividere le cose, e alcune di queste venti potrebbero essere condivise da più di un oggetto (quindi il nodo foglia di un livello 20 l'albero binario non necessariamente contiene solo un elemento).

Quindi, la "ricerca binaria" è solo una metafora di ciò che sta effettivamente accadendo, in quanto in ogni fase si tenta di scegliere la proprietà che meglio divide il set rimanente in due metà uguali. Per quanto riguarda le strutture dati attuali, dovresti usare qualcos'altro.

Answer 2

Se è necessario attenersi a un albero binario per il problema, non c'è nulla che dice che non è possibile duplicare un ramo o un nodo. Posiziona il nodo di risposta felino alla fine di più di una serie di decisioni. Oppure chiedi due volte alla domanda del predatore - una volta se l'utente ha detto "sì" ai mammiferi, e una volta se l'utente ha risposto "no".

Sicuramente ci sono problemi di ottimizzazione ed efficienza se si prende questa decisione, ma ci sono anche modi per affrontare specifici problemi. (Ad esempio, se si è preoccupati dello spazio di archiviazione per l'albero delle decisioni, quindi rendere i rami o i nodi o entrambi i puntatori a oggetti/dichiarazioni immutabili).

Answer 3

Se stai cercando una corrispondenza esatta - solo hash su tutte le proprietà e fare una ricerca.

Se si desidera eseguire il riconoscimento del motivo per trovare elementi simili, è possibile utilizzare un metodo con una mappatura abbastanza "lineare", ad esempio k-next neighbor. Ad esempio, puoi usare un albero kd per rappresentare lo spazio di ricerca.

Answer 4

Credo che quello che stai cercando sia più comunemente indicato come Decision Tree, in particolare per la classificazione. Puoi quindi utilizzare algoritmi come C4.5 per imparare come ordinare le tue domande per classificarle in modo efficiente.