@空明流轉(zhuǎn)
直接枚舉法，你說的是對5040種排列依次猜測嗎。。。？最壞情況下猜測次數(shù)可能5040次吧。或者你有更好的辦法嗎？
@東坡_居士
我覺得不應(yīng)當(dāng)考慮概率，而應(yīng)當(dāng)考慮在任意時(shí)刻，可行解集合里任何數(shù)都有可能是正確結(jié)果。實(shí)際上就是在一個(gè)狀態(tài)轉(zhuǎn)移圖中，任何可行的路徑都有可能沿著走下去，每選擇一個(gè)數(shù)，就走進(jìn)了一個(gè)分支。
@東坡_居士
上面公式還可以進(jìn)一步修改一下：
t(F) = min{ t( F- conf(f) ) + 1, for all f belongs to F}， 其中conf(f)指與f沖突的集合（每一種返回結(jié)果就對應(yīng)一個(gè)沖突集，所以復(fù)雜度又上升了）。
@東坡_居士
我猜測你也在考慮“動(dòng)態(tài)規(guī)劃”方法。
我考慮過“動(dòng)態(tài)規(guī)劃”算法，遞推公式： t(F) = min{ t(F-f)+1, for all f belongs to F}, 其中 F 是當(dāng)前可行集，t(F)為該可行集 F 條件下猜出結(jié)果的次數(shù)，f 為 F 中的一個(gè)可行排列。
但是我沒有編程實(shí)現(xiàn)，因?yàn)閾?dān)心復(fù)雜度太高運(yùn)行不完。但是可以保證這樣能得到最優(yōu)解。
貪心算法得到的應(yīng)當(dāng)不是最優(yōu)解，但是近似最優(yōu)解，而且也是可以接受的。
@東坡_居士
最好最壞就是說：每一行求最大（最壞），然后對所有行的最大值中取最小（最好）。所以計(jì)算過程還是 O(M^2) 的。
@東坡_居士
回復(fù)東坡_居士：你的算法“如果這個(gè)“提問”得到的“答案”種類越多，每個(gè)答案下面的可能數(shù)字就越少”，實(shí)際上可以通過對Clever1Palyer的進(jìn)行修改實(shí)現(xiàn)：
34 int all_max = 0;
35 int all_max_index;
36 for (int i=0; i<M; i++) {
37 // 對于每一個(gè)可行排列 Ri
38 if (_cand[i]) { // 這一行也可以去掉
41 // cur_max 記錄該當(dāng)前行可行排列的關(guān)系的種數(shù)
42 int cur_max = 0;
43 for (int j=0; j<=MATCH; j++)
44 res_count[j] = 0;
45 for (int j=0; j<M; j++) {
46 if (_cand[j])
47 res_count[ (int)table[i][j] ]++;
48 }
49 for (int j=0; j<=MATCH; j++) // 求種類數(shù)
50 if (res_count[j] > 0)
51 cur_max ++;
52 // 如果 cur_max 小于全局 all_max，則更新 all_max，并記錄下當(dāng)前排列的序號
53 // 這樣能找到種類數(shù)最多的情況
54 if (cur_max > all_max) {
55 all_max = cur_max;
56 all_max_index = i;
57 }
58 }
59 }
所以我的假設(shè)是最壞假設(shè)，你的假設(shè)是等概率假設(shè)。呵呵，你把裁判想得比較善良。
@東坡_居士
當(dāng)前Clever1Player時(shí)間復(fù)雜度為 (M*M*Time) ，其中Time為猜測次數(shù)。考慮次數(shù)總小于10，所以時(shí)間復(fù)雜度為 (M^2)。
我曾經(jīng)做過優(yōu)化，即使用一個(gè)數(shù)組保存可行排列序號，這樣在 Clever1Player 的 36 和 45 行就只需要掃描數(shù)組，而不需要每次都掃描 M 次了。當(dāng)然總的時(shí)間復(fù)雜度依然是 (M^2)。
Clever2Player 與 Clever1Player 的唯一區(qū)別在于 “去掉了Clever1Player 的第 38 行”，使得“下一次猜測的排列不局限于可行排列”。
基于的考慮是：
-------------
假設(shè)正確結(jié)果是 0124
第一次猜 0123 -> 3A0B
Clever1Player 接下來不能猜 4567 ，因?yàn)?4567 不在可行集中（已經(jīng)排除）。
但是Clever2Player 則有可能會(huì)猜 4567 得到 0A1B，直觀上說，猜測范圍就縮小到 01234567 中了，搜索空間減小很多。實(shí)際上我們?nèi)四X使用邏輯推理的時(shí)候通常就是這么考慮的，而且我們肯定是不會(huì)使用這種搜索算法的。
至于邏輯推理法與搜索法之間有什么聯(lián)系，我也不清楚。
-------------
另外，該算法的關(guān)注點(diǎn)在于猜測次數(shù)，即在于效果而不是效率。所以為了使算法看起來清晰，我沒有過多優(yōu)化。
NaivePlayer 算法執(zhí)行時(shí)間最快，大約1分鐘跑完所有，Clever1Player大約5分鐘，Clever2Player大約10分鐘。