本文將給出解答猜數(shù)字游戲（guess number）的一種算法，最多6步就可猜出結(jié)果。這個(gè)的解法需要用到部分信息論的知識(shí)。
猜數(shù)字問(wèn)題表述如下：答案是0至9十個(gè)數(shù)的四位排列（沒(méi)有重復(fù)元素）。每猜一次，游戲比較答案和輸入這兩組排列，反饋aAbB。aA表示有a個(gè)數(shù)字?jǐn)?shù)值正確位置正確，bB表示b個(gè)數(shù)字?jǐn)?shù)值正確位置錯(cuò)誤。
考慮問(wèn)題的互動(dòng)方式，這道題目屬于輸入反饋的問(wèn)題。每次輸入，從反饋中獲取部分信息，當(dāng)獲得系統(tǒng)的全部信息時(shí)，就能猜出答案。所以解這個(gè)問(wèn)題的關(guān)鍵是尋找合適的輸入使反饋的信息量最大。
這道題的解法思路比較簡(jiǎn)單，由于是有窮狀態(tài)，而且數(shù)量不大，可用窮舉法解答。比較所有可能的輸入，找出最佳輸入（某個(gè)標(biāo)準(zhǔn)下）。問(wèn)題變成了如何衡量輸入的好壞。輸入越好則反饋的信息越大，山農(nóng)給出的信息量的定義是衡量輸入好壞的標(biāo)準(zhǔn)。信息量是不確定性的大小，如果某個(gè)事件的概率為P，則它含有的信息量為log(1/P)。具體的理論可以參考一本關(guān)于信息論的書。
具體到猜數(shù)字這個(gè)題目，答案有多種可能。得到反饋前，每一個(gè)輸入的反饋有不同的可能。得到反饋后，反饋是確定的，不確定性變?yōu)?/span>0。這樣問(wèn)題的信息量變小了。前后的信息量之差就是這個(gè)輸入能夠得到的信息量。
統(tǒng)計(jì)反饋前這個(gè)輸入可能得到的反饋，求出各種反饋的概率，可由下面公式計(jì)算出反饋前的信息量：
H=P1*log(1/P1)+P2*log(1/P2)+...。P1，P2等分別為不同反饋的概率。
反饋后，這個(gè)輸入的反饋是確定的，信息量為0。比較所有輸入能夠得到信息量，就能找出最佳的輸入。
統(tǒng)計(jì)反饋前這個(gè)輸入可能得到的反饋：
// 把輸入和所有可能的答案比較，得到所以不同反饋可能出現(xiàn)的次數(shù)
// 輸入?yún)?shù)：input輸入
// 輸出參數(shù)：feedbacks反饋可能出現(xiàn)的次數(shù)
void GetPsbFeedbacksNum(VectorInt& feedbacks, const VectorInt& input)
{
// 和所有可能的答案比較
for (int j=0; j<ALL_ANS_NUM; j++)
{
// 答案是否已經(jīng)被排除
if (g_AnsState[j] != 0)
continue;
feedbacks[GetFeedback(input, g_AllAns[j])]++;
}
}計(jì)算這個(gè)輸入能夠獲得的信息量
// 計(jì)算信息量
// 輸入?yún)?shù)：不同反饋出現(xiàn)的次數(shù)
// 返回值：信息量
double CalcEntropy(const VectorInt &feedbacks)
{
int sum = 0;
double entropy = 0.;
for (int j=0; j<feedbacks.size(); j++)
sum += feedbacks[j];
for (int j=0; j<feedbacks.size(); j++)
{
if (feedbacks[j] == 0)
continue;
float tmp = (float)feedbacks[j]/sum;
entropy += -1*tmp*log(tmp);
}
return entropy;
}
這樣就得到每個(gè)輸入的信息量。下面討論如何枚舉所有可能的輸入。
輸入的種類有10*9*8*7種，把每一種輸入和所有可能答案比較。這方法比較直觀，但運(yùn)算次數(shù)太多。
// 得到最佳的輸入，不分類直接比較的方法
// 最佳輸入存放在g_AnsGuess中
void GetBestInputNoSort()
{
double max_entropy = 0.; // 存放最大的信息量
VectorInt feedbacks((ANS_SIZE+1)*(ANS_SIZE+1), 0); // 反饋的結(jié)果分類
// 比較所有輸入的信息量
for (int i=0; i<ALL_ANS_NUM; i++)
{
// 這個(gè)輸入的信息量是否是0
if (g_InputState[i] == 1)
continue;
// 是否只在可能的答案中搜索最佳輸入
// if (g_AnsState[i] != 0)
// continue;
// 得到所有可能的反饋
feedbacks.assign((ANS_SIZE+1)*(ANS_SIZE+1), 0);
GetPsbFeedbacksNum(feedbacks, g_AllAns[i]);
// 計(jì)算信息量
double entropy = CalcEntropy(feedbacks);
// 排除信息量為0的輸入
if (entropy < 0.00001)
{
g_InputState[i] = 1;
continue;
}
// 求最大的信息量
if (max_entropy < entropy)
{
max_entropy = entropy;
g_AnsGuess = g_AllAns[i];
}
}
}
由于第一次輸入，各種輸入能夠得到的信息量是一樣的，因此第一次可以不比較，任給一組輸出。改進(jìn)后的代碼如下：
// 得到最佳的輸入，不分類直接比較的方法，但優(yōu)化過(guò)第一次輸入。
// 最佳輸入存放在g_AnsGuess中
void GetBestInputIpvFst()
{
// 如果是第一次，所有輸入的信息量是一樣的，任選一個(gè)
if (g_isFirstTime)
{
g_isFirstTime = 0;
g_AnsGuess = g_AllAns[0];
}
else
GetBestInputNoSort();
}
第一次輸入時(shí)10個(gè)元素之間是沒(méi)有分別的。沿著這個(gè)思路考慮，第二次輸入時(shí)，6個(gè)沒(méi)有參與輸入的元素，也沒(méi)有分別。舉例來(lái)說(shuō)，第一次輸入{0，1，2，3}，則4，5，6，7，8，9六個(gè)元素屬同一類元素，在第二次輸入時(shí)可以相互替換。如{0，1，2，4}和{0，1，2，5}兩組輸入能夠得到的信息量應(yīng)該相同。把元素分類枚舉則可以優(yōu)化算法。
分類方法如下，參入輸出的元素單獨(dú)成一類，沒(méi)有參與的元素是一類。第一次輸入時(shí)，只有一類元素，這類元素個(gè)數(shù)為10。第二次輸入時(shí)，有五類元素，有四類元素個(gè)數(shù)為1，一類元素個(gè)數(shù)為6。依次類推。關(guān)于如何枚舉見(jiàn)
《從集合中枚舉子集》。
// 得到最佳的輸入,元素分類的方法
// 最佳輸入存放在g_AnsGuess中
void GetBestInputSort()
{
double max_entropy = 0.; // 存放最大的信息量
VectorInt feedbacks((ANS_SIZE+1)*(ANS_SIZE+1), 0);// 反饋的結(jié)果分類
// 初始化枚舉
CSetIterAgent<int> iter(g_AnsEle);
iter.Init(ANS_SIZE, CSetIter::MULT_ORDERED_IN);
// 比較所有輸入的信息量
VectorInt setsub(ANS_SIZE, 0);
while (iter.GetNextSubset(setsub, g_AnsEle))
{
// 把-1元素具體化，-1表示該元素沒(méi)有輸入過(guò)
AssembleInput(setsub);
// // 這個(gè)輸入的信息量是否是0
// if (g_InputState[GetSetPosition(setsub)] == 1)
// continue;
// 是否只在可能的答案中搜索最佳輸入
// if (g_AnsState[GetSetPosition(setsub)] != 0)
// continue;
// 得到所有可能反饋的數(shù)目
feedbacks.assign((ANS_SIZE+1)*(ANS_SIZE+1), 0);
GetPsbFeedbacksNum(feedbacks, setsub);
// 計(jì)算信息量
double entropy = CalcEntropy(feedbacks);
// // 排除信息量為0的輸入
// if (entropy < 0.00001)
// {
// g_InputState[GetSetPosition(setsub)] = 1;
// continue;
// }
// 求最大的信息量
if (max_entropy < entropy)
{
max_entropy = entropy;
g_AnsGuess = setsub;
}
}
// 元素分類
SortEle();
}
分類的方法可以大大提升運(yùn)算速度，下面的測(cè)試會(huì)證明這一點(diǎn)。但當(dāng)參與輸入元素慢慢增加時(shí)，分類就不那么重要，而且調(diào)用CSetIterAgent也是一筆不小的開銷。將第一種算法和分類法結(jié)合：
// 不分類法和分類法的混合法
// 輸入?yún)?shù)：num表示當(dāng)輸入元素個(gè)數(shù)等于或超過(guò)num時(shí)用直接法
void GetBestInputBlend(int num)
{
// 計(jì)算沒(méi)有輸入過(guò)的元素個(gè)數(shù)
int sum = 0;
for (int i=0; i<g_AnsEle.size(); i++)
{
if (g_AnsEle[i] == -1)
sum++;
}
sum = g_AnsEle.size() - sum;
if (sum >= num)
GetBestInputNoSort();
else
GetBestInputSort();
}
下面給出這些算法的測(cè)試結(jié)果。測(cè)試方法是將10*9*8*7種答案依次用這些算法求解，統(tǒng)計(jì)猜出每個(gè)答案需要多少次數(shù)。一共花費(fèi)了多少時(shí)間。
1次 1
2次 12
3次 261
4次 2082
5次 2500
6次 184
平均次數(shù)：4.51190
N次是指N次輸入反饋后，就可以確定答案，并不指第N次輸入的反饋是4A0B。
花費(fèi)的時(shí)間：
GetBestInputNoSort： 8h也沒(méi)有算完
GetBestInputIpvFst： 9385s
GetBestInputSort： 1596s
GetBestInputBlend7： 2151s
GetBestInputBlend10： 1515s
這些方法在本質(zhì)上是一樣的，即在所有的輸入中尋找反饋信息量最大的輸入。下面考慮其他方法，比較這些方法的差別。
如果縮小尋找范圍，不考慮不是答案的輸入。代碼如下：
取消GetBestInputNoSort函數(shù)中
// 是否只在可能的答案中搜索最佳輸入
if (g_AnsState[i] != 0)
continue;
和GetBestInputSort函數(shù)中
// 是否只在可能的答案中搜索最佳輸入
if (g_AnsState[GetSetPosition(setsub)] != 0)
continue;
這兩行注釋。
測(cè)試結(jié)果如下：
1次 1
2次 16
3次 228
4次 1555
5次 2688
6次 542
7次 10
平均次數(shù)：4.70218
運(yùn)行時(shí)間：
GetBestInputIpvFst：1375s
GetBestInputSort： 97s
縮小范圍后，速度有很多提升，但平均次數(shù)增加了。
再考慮另外一種方法，不從信息量的角度考慮。用第一個(gè)可能為答案的排列作為輸入。
// 得到第一個(gè)可能的答案
void GetFstPsbInput()
{
for (int i=0; i<ALL_ANS_NUM; i++)
{
if (g_AnsState[i] == 0)
{
g_AnsGuess = g_AllAns[i];
break;
}
}
}
測(cè)試結(jié)果：
1次 1
2次 15
3次 211
4次 1240
5次 2108
6次 1203
7次 252
8次 10
平均次數(shù)：5.00515
花費(fèi)的時(shí)間：7s
這個(gè)方法令人吃驚的是它的速度，如此簡(jiǎn)單卻又不錯(cuò)的效果。平均次數(shù)要比上面兩個(gè)方法差些。
上面的測(cè)試結(jié)果是在vc2005的release下編譯測(cè)試。
本文用信息量大小作為判斷最佳輸入的標(biāo)準(zhǔn)，相比其他算法平均步數(shù)較少，但花費(fèi)的時(shí)間較多。如何縮短計(jì)算時(shí)間將在以后的文章中繼續(xù)探討。此外從測(cè)試中看出，方法2，3在兩次內(nèi)猜中答案的次數(shù)比方法1多。在這個(gè)意義下方法2，3比方法1要優(yōu)。以后還會(huì)在不同的意義下比較各類算法。大家有什么好的想法可以聯(lián)系我，大家一起討論。我的郵箱
lemene@sina.com.cn 代碼下載