Użytkownik "cbnet" <c...@n...pl> napisał w wiadomości
news:gd7cdu$2713$1@news2.ipartners.pl...
> Algorytmy [jak dotąd] są generalnie dwa: oparty na teście
> bitowym, oraz ten z tego tematu, czyli oparty na dzieleniu
> w każdym kroku zbiorów dopuszczalnych rozwiązań.
>
> W obrębie każdego z tych algorytmów można wygenerować
> skończoną ilość rozwiązań szczegółowych (które daje się
> prawdopodobnie oszacować).
>
> Tak bym to oceniał, chyba, że ktoś się silnie nie zgadza...

Mi sięwydaje, że można te algorytmy uogólnić, ale jeszcze nie wiem jak.
Ale taki eksperyment. Robimy metodą ... FT, celowo pokazuję zbiór S
(spalone):

C={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} K={} S={}

1. ? 1,3,5,7,9,11,13,15 Yes

C={1,3,5,7,9,11,13,15} K={0,2,4,6,8,10,12,14} S={}
Z C wybieramy 3,7,11,15, z K wybieramy 2,6,10,14

2. ? 2,3,6,7,10,11,14,15 Yes

C={3,7,11,15} K={1,2,5,6,9,10,13,14} S={0, 4, 8, 12}
Z C wybieramy 7,15, z K wybieramy 5,6,13,14, dodatkowo 'dla zmyły' dorzucamy
z S: 4,12 ;)
W metodzie FT dorzucanie z S jest dopuszczalne - nie wpływa na dalszy ciąg
;)

3. ? 4,5,6,7,12,13,14,15 Yes
C = {7,15} K={3,11, 5,6,13,14} S={0, 4,8,12, 1,2,9,10}
Z C wybieramy 15, z K 11,13,14, z S dorzucamy 'dla jaj' 8,9,10,12 ;)

4. ? 8,9,10,11,12,13,14,15 Yes
Widać już ? Mamy DOKŁADNIE TE SAME 4 ZAPYTANIA co w metodzie bitowej ;)

C={15} K={7, 11,13,14}, S - cała reszta sziedzi tu.
Bez analizy bitowej mamy ten sam stan wiedzy, co wcześniej: 15 jest 'pewna'
a 7,11,13,14 są 'obciażone jednym kłamstwem'.

Zgodnie z przedstawionym olgorytmem FT możemy teraz zadać pytanie

5. ?15, 11

Takie pytanie postawiłem wcześniej korzystając z własnej tabelki.
Nie da się zaś z tej metody w tej chwili wyprowadzić Twojego pytania
postaci:

5. ? 7, 11, 13
Aczkolwiek wydaje mi się, że można algorytm FT nieco uogólnić,
tak, by w sytuacji, gdy w C jest tylko jeden element to jeśli go nie
wyciągamy
to są dopuszczalne(a może wymagane ?) wybory trzech elementów ze zbioru K.

Generalnie konkluzja: jestem prawie pewien, że po drobnych korektach
algorytm
FT staje się uogólnieniem metody bitowej ;). Czyli metoda bitowa jest
szczególnym
przypadkiem algorytmu FT (po drobnych korektach). Pierwsze dwa zapytania
o pierwsze dwa bity możemy dać zawsze, niezależnie od odpowiedzi - nie
naruszając
FT. Czy trzecie - nie jestem pewien. Możliwe, że jest taka sytuacja, że w 3
zapytaniu
będziemy musieli zadać pytanie o 4-ty bit a nie o trzeci, a dopiero w 4
będziemy mogli
już dorzucać z S na tyle swobodnie, że skonstruujemy pytanie identyczne, jak
pytanie
o trzeci bit. Zmieni się więc kolejność zadawanych pytań. To samo może
ostatnich 3 pytań
- być może trzeba by zmieniać kolejność zapytań, żeby je dopasować do FT.