Algorithmus: Binäre Suche bei unsicheren Werten

Ich benötige einen Algorithmus, um eine binäre Suche durchzuführen, wenn der Test bei jedem Schritt das falsche Ergebnis liefern kann.

Hintergrund: Ich muss die Schüler auf den am besten geeigneten von 12 Schwierigkeitsstufen bringen. Der derzeitige Ansatz ist Brute Force und stellt 60 Multiple-Choice-Fragen mit 4 Antworten mit zunehmendem Schwierigkeitsgrad, stoppt nach drei falschen und stellt den Schüler auf ein Niveau: floor((score - 1) / 5) + 1mit einem Minimum von 1.

Wir sind besorgt, dass Kunden ausgeschaltet werden, wenn sie einem Test mit bis zu 60 Fragen gegenüberstehen, bevor sie das Programm tatsächlich verwenden können. Daher möchten wir die Anzahl der im Test gestellten Fragen minimieren. Wir sind auch besorgt, dass Kunden den Einstufungstest überspringen (weil er lang erscheint) und das Programm dann abbrechen, weil es zu einfach erscheint.

Die mittlere Platzierung befindet sich tatsächlich auf Stufe 2, sodass 50 +% der Schüler <11 Punkte erzielen (dh <14 Fragen beantworten). Anekdotisch kann dies daran liegen, dass sie sich langweilen und die Fragen nicht mehr ernst nehmen (sie sind kleine Kinder).

Vorgeschlagene Lösung: Implementieren Sie den Test als binäre Suche über zwölf Elemente, beginnend mit einer Frage im Schwierigkeitsgrad 6/7 und je nachdem, ob die Frage richtig oder falsch ist. Theoretisch könnte dies in 3-4 Fragen den entsprechenden Schwierigkeitsgrad für sie finden.

Das Problem: Wie Sie vielleicht aus dem vorhandenen Test erraten können, der erst nach drei falschen Antworten endet und 60 Fragen verwendet, um zwischen 12 Stufen zu wählen, möchten wir berücksichtigen, dass Schüler korrekte Antworten (die sie in 25% der Fälle tun sollten) oder versehentlich falsch machen falsche Antworten geben (dicke Finger, falsch interpretierte Frage usw.). Dies ist bei einer binären Suche noch wichtiger, da Sie durch die richtige Antwort auf die erste Frage in die obere Hälfte des Schwierigkeitsgrades gelangen können, selbst wenn Sie jede andere Frage falsch stellen.

Gibt es also einen anerkannten Algorithmus für eine binäre Suche, bei dem Sie nicht garantieren können, dass ein einzelner Test korrekt ist?

Naiv könnte ich bei jedem Schritt das Beste aus 3 oder 5 Fragen versuchen, und da die frühen Fragen einen größeren Einfluss auf das Endergebnis haben als die späteren Fragen, sollten Sie diese zusätzlichen Fragen möglicherweise nur zu den frühen Schritten und nicht zu den späteren hinzufügen. Gibt es mehr als das?

Behandeln Sie das Problem als eine Reihe von Bayes'schen Wahrscheinlichkeiten. Angenommen, es besteht eine Wahrscheinlichkeit von 1/13, dass sich das Kind knapp unter jedem Level befindet, und der Vollständigkeit halber eine Chance von 1/13, dass es von der Spitze abweicht. Dann: 1) Finden Sie den Medianwert Ihres Arrays, dh den Wert, bei dem die Wahrscheinlichkeit, darüber zu liegen, 50% am nächsten kommt. 2) Stellen Sie dem Kind eine Frage von diesem Wert. 3) Verwenden Sie die Bayes-Regel, um die Wahrscheinlichkeit jeder Zelle unter der Annahme einer Fehlerrate von 25% zu aktualisieren. Beende und gib das wahrscheinlichste Level zurück, wenn eine Zelle eine ausreichend hohe Wahrscheinlichkeit erreicht, oder wenn dir auf einem Level die Fragen ausgehen.

Eine strengere Behandlung dieses Algorithmus ist hier ; Ich empfehle es vor der Implementierung zu lesen.