12球問(wèn)題表述如下：有12個(gè)球，有一個(gè)球的重量與其它球的重量不一致。用一臺(tái)沒(méi)有刻度的天平稱(chēng)3次把這個(gè)球找出。當(dāng)然12球問(wèn)題可以推廣至N個(gè)球。
首先考慮這道題目的模式，它屬于輸入反饋的問(wèn)題。每一次輸入（即稱(chēng)一次）便會(huì)有一個(gè)反饋信息，分析反饋信息再次輸入，直到把問(wèn)題解決。通過(guò)一次次輸入反饋、這類(lèi)問(wèn)題解法思路較簡(jiǎn)單，由于是有窮狀態(tài)，狀態(tài)數(shù)目不大，可以用窮舉法解答。比較所有的輸入，找出最佳輸入（某個(gè)標(biāo)準(zhǔn)意義下）。問(wèn)題是如何衡量輸入的好壞。直觀上，輸入越好，反饋的信息就越大。問(wèn)題變成了對(duì)信息的量化。山農(nóng)給出了信息量的定義是解決問(wèn)題的關(guān)鍵。信息量是不確定性的大小。如果某個(gè)事件的概率為P，則它含有的信息量為log(1/p)。具體理論請(qǐng)參考關(guān)于信息論方面的書(shū)籍。（這個(gè)問(wèn)題和猜數(shù)字很像，大家參考此文《猜數(shù)字的一種解法》）。
具體到這個(gè)12球問(wèn)題。12個(gè)球從0-11編號(hào)。0號(hào)球?yàn)檩^輕的球可能性為1/24。這個(gè)事件的信息量log(24)。同理0號(hào)球?yàn)橹厍蜻@個(gè)事件的信息量為log(24)。這樣的事件有24個(gè)，每個(gè)事件出現(xiàn)的概率1/24，所以整個(gè)系統(tǒng)的信息量24*(1/24*log(24))，即log(24)。
下面我們考慮一次具體的輸入：
第一次輸入，天平左端放0號(hào)球，右端放1號(hào)球。反饋信息可能為平衡，左傾，右傾。 平衡：這時(shí)0，1號(hào)球是標(biāo)準(zhǔn)球。根據(jù)上面的計(jì)算過(guò)程，同樣可以計(jì)算出此時(shí)系統(tǒng)含有的信息量20*(1/20*log(20))，即log(20)。這次輸入獲得的信息log(24)-log(20)。
左傾：可能的情況，1號(hào)球?yàn)檩p球，2號(hào)球?yàn)橹厍颉４藭r(shí)系統(tǒng)的信息量log(2)。獲得的信息log(24)-log(2)。
右傾：同左傾，此時(shí)系統(tǒng)的信息量log(2)。獲得的信息log(24)-log(2)。
這次輸入，出現(xiàn)平衡的概率20/24，出現(xiàn)左傾的概率2/24，出現(xiàn)右傾的概率2/24。這可以計(jì)算這次輸入能夠獲得的平均信息量為20/24*(log(24)-log(20))+2/24*(log(24)-log(2))+2/24*(log(24)-log(2))，即20/24*log(24/20)+2/24*log(24/2)+2/24*log(24/2)。
下面就要枚舉所有可能的輸入，找出平均信息量最大的輸入。枚舉需要些技巧，需要把球分類(lèi)，例如第一次輸入時(shí)每個(gè)球可以看成相同，左右天平放的球數(shù)為1，2，3，4，5，6，一共六情況。如果把每個(gè)球區(qū)別看待枚舉的次數(shù)將會(huì)很多。下面介紹分類(lèi)方法。
根據(jù)球的狀態(tài)，分成4類(lèi)，一類(lèi)：標(biāo)準(zhǔn)球即排出不標(biāo)準(zhǔn)的可能性，二類(lèi)：只可能為輕球，三類(lèi)：只可能為重球，四類(lèi)：可能為輕球也可能為重球。
// 把球分類(lèi)
// 輸出參數(shù)：type 表示對(duì)應(yīng)球的類(lèi)型，0為標(biāo)準(zhǔn)球，1可能為輕球，2可能為重球，3都有可能
void CGuessBall::SortBalls(VectorInt& type)
{
for (int i=0; i<m_iNumOfBalls; i++)
{
if (m_vPsbAns[i*2] == 0)
type[i]++;
if (m_vPsbAns[i*2+1] == 0)
type[i] += 2;
}
}
// 返回四個(gè)數(shù)組，分別表示四類(lèi)球
void CGuessBall::SortBalls(VectorInt& type0, VectorInt& type1, VectorInt& type2, VectorInt& type3)
{
for (int i=0; i<m_iNumOfBalls; i++)
{
if (m_vPsbAns[i*2] == 0 && m_vPsbAns[i*2+1] == 0)
type3.push_back(i);
else if (m_vPsbAns[i*2+1] == 0)
type2.push_back(i);
else if (m_vPsbAns[i*2] == 0)
type1.push_back(i);
else
type0.push_back(i);
}
}
// 使用分類(lèi)法得到最佳輸入
// 輸出參數(shù)：left，right左右天平球的標(biāo)號(hào)
void CGuessBall::GetBestInputSort(VectorInt& left, VectorInt& right )
{
double max_entropy = 0.0;
// 把球分類(lèi)
VectorInt types(m_iNumOfBalls, 0);
SortBalls(types);
VectorInt t[4];
SortBalls(t[0], t[1], t[2], t[3]);
// 枚舉所有可能的輸入組合
// 首先找出i個(gè)球，左右天平各方i/2個(gè)球。
CSetIterAgent<int> iter(types);
for (int i=2; i<=m_iNumOfBalls; i+=2)
{
iter.Init(i, CSetIter::MULT_DISORDER_IN);
VectorInt subset(i, 0);
while (iter.GetNextSubset(subset, types))
{
// 再?gòu)膇個(gè)球中找出i/2個(gè)球
CSetIterAgent<int> iter_i(subset);
iter_i.Init(i/2, CSetIter::MULT_DISORDER_IN);
VectorInt subset_l(i/2, 0);
VectorInt subset_r(i/2, 0);
while (iter_i.GetNextSubset(subset_l, subset))
{
// subset - subset_l得到subset_r
int idx_r=0, idx_l=0, idx=0;
while (idx < subset.size())
{
if (idx_l >= subset_l.size() ||
subset_l[idx_l] != subset[idx])
{
subset_r[idx_r++] = subset[idx++];
}
else
{
idx_l++, idx++;
}
}
// 把球的類(lèi)型轉(zhuǎn)化成具體的球號(hào)
int idxs[4] = {0, 0, 0, 0};
left.assign(i/2, -1);
for (int j=0; j<subset_l.size(); j++)
{
left[j] = t[subset_l[j]][idxs[subset_l[j]]++];
}
right.assign(i/2, -1);
for (int j=0; j<subset_r.size(); j++)
{
right[j] = t[subset_r[j]][idxs[subset_r[j]]++];
}
// 得到所有可能的反饋
VectorInt outputs(3, 0);
for (int j=0; j<m_vPsbAns.size(); j++)
{
if (m_vPsbAns[j] == 1)
continue;
outputs[CheckFeedback(right, left, j)+1]++;
}
// 檢查是否是理論最優(yōu)，提前返回
if (IsTheoryBestInput(outputs))
{
m_vLeft = left;
m_vRight = right;
return;
}
// 比較
double entropy = CalcEntropy(outputs);
// 求最大的信息量
if (max_entropy < entropy)
{
max_entropy = entropy;
m_vLeft = left;
m_vRight = right;
}
}
}
}
left = m_vLeft;
right = m_vRight;
}
要使得到的信息量最大，就要使天平左傾，右傾，平衡的出現(xiàn)的概率盡可能相等。四類(lèi)球，只有三類(lèi)影響平衡，如果它們的個(gè)數(shù)能被3整除，左右天平各放三分之一份球。當(dāng)然也有不能被3整除的情況。三類(lèi)球，每一類(lèi)均可能有余數(shù)0，1，2。組合起來(lái)一共有27種情況。考慮這27種情況配合標(biāo)準(zhǔn)球如何分配。得到以下的算法，先將三類(lèi)球三等分，然后再考慮27種余數(shù)情況，得到第二種算法。
// 直接法得到最佳輸入
void CGuessBall::GetBestInputDirect(VectorInt& left, VectorInt& right)
{
// 第一次輸入，沒(méi)有標(biāo)準(zhǔn)球。
if (m_iTimes == 0)
{
int num = (m_iNumOfBalls+1) / 3;
left.assign(num, -1);
right.assign(num, -1);
for (int i=0; i<num; i++)
{
left[i] = i;
right[i] = i + num;
}
}
else
{ // 有標(biāo)準(zhǔn)球
VectorInt t0, t1, t2, t3;
SortBalls(t0, t1, t2, t3);
int tmp1 = t1.size() / 3;
for (int i=0; i<tmp1; i++)
{
left.push_back(t1[i]);
right.push_back(t1[i+tmp1]);
}
int tmp2 = t2.size() / 3;
for (int i=0; i<tmp2; i++)
{
left.push_back(t2[i]);
right.push_back(t2[i+tmp2]);
}
int tmp3 = t3.size() / 3;
for (int i=0; i<tmp3; i++)
{
left.push_back(t3[i]);
right.push_back(t3[i+tmp3]);
}
switch ((t3.size()%3)*9+(t2.size()%3)*3+(t1.size()%3))
{
case 0*3*3 + 0*3 + 0:
case 0*3*3 + 0*3 + 1:
case 0*3*3 + 1*3 + 0:
break;
case 0*3*3 + 0*3 + 2:
case 0*3*3 + 1*3 + 2:
case 0*3*3 + 2*3 + 2:
// case 1*3*3 + 0*3 + 2:
left.push_back(t1[tmp1*2]);
right.push_back(t1[tmp1*2+1]);
break;
case 0*3*3 + 1*3 + 1:
left.push_back(t1[tmp1*2]);
right.push_back(t0[0]);
break;
case 0*3*3 + 2*3 + 0:
case 0*3*3 + 2*3 + 1:
// case 1*3*3 + 2*3 + 0:
left.push_back(t2[tmp2*2]);
right.push_back(t2[tmp2*2+1]);
break;
case 1*3*3 + 0*3 + 0:
// case 1*3*3 + 0*3 + 1:
// case 1*3*3 + 1*3 + 0:
case 2*3*3 + 0*3 + 0:
left.push_back(t3[tmp3*2]);
right.push_back(t0[0]);
break;
// case 1*3*3 + 1*3 + 1:
// case 1*3*3 + 1*3 + 2:
// case 1*3*3 + 2*3 + 1:
// left.push_back(t1[tmp1*2]);
// right.push_back(t3[tmp3*2]);
// break;
// case 1*3*3 + 2*3 + 2:
// left.push_back(t1[tmp1*2]);
// right.push_back(t1[tmp1*2+1]);
// left.push_back(t2[tmp2*2]);
// right.push_back(t2[tmp2*2+1]);
// break;
// case 2*3*3 + 0*3 + 1:
// case 2*3*3 + 0*3 + 2:
// case 2*3*3 + 1*3 + 0:
// case 2*3*3 + 1*3 + 1:
// case 2*3*3 + 2*3 + 0:
// case 2*3*3 + 1*3 + 2:
// case 2*3*3 + 2*3 + 1:
// left.push_back(t3[tmp3*2]);
// right.push_back(t3[tmp3*2+1]);
// break;
// case 2*3*3 + 2*3 + 2:
// left.push_back(t1[tmp1*2]);
// right.push_back(t1[tmp1*2+1]);
// left.push_back(t3[tmp3*2]);
// right.push_back(t3[tmp3*2+1]);
// break;
default:;
}
}
m_vLeft = left;
m_vRight = right;
}
這里要注意，如果有標(biāo)準(zhǔn)球則能達(dá)到最佳的輸入。所以第一次沒(méi)有標(biāo)準(zhǔn)球要區(qū)別對(duì)待。此外其實(shí)沒(méi)有27種情況，因?yàn)榈诙?lèi)不可能和第四類(lèi)同時(shí)出現(xiàn)。
這是一個(gè)測(cè)試程序 ，解答12球的問(wèn)題，它輸出左右天平放的球的編號(hào)，等待用戶(hù)判斷左傾，右傾還是平衡，直到輸出結(jié)果。
#ifdef _TEST_
int main()
{
int size = 12;
CGuessBall guess(size);
while (1)
{
VectorInt left, right;
int fd;
guess.GetBestInput(left, right);
// 輸出左右天平的編號(hào)
for (int i=0; i<left.size(); i++)
printf("%d, ", left[i]);
printf("\n");
for (int i=0; i<right.size(); i++)
printf("%d, ", right[i]);
printf("\n");
// 等待反饋
printf("左傾，平衡，右傾（-1，0，1）：");
scanf("%d", &fd);
if (fd <= -1) fd = -1;
else if (fd >= 1) fd = 1;
else fd = 0;
int rz = guess.RemoveImpsAns(fd);
if (rz == 1)
{
int ans = guess.GetTheFirstImpsAns();
printf("猜出結(jié)果：%d球?yàn)?s球", ans/2, ans%2?"重":"輕");
break;
}
else if (rz < 1)
{
printf("輸入錯(cuò)誤");
break;
}
else
continue;
}
}
#endif
從程序運(yùn)行情況看，很多球也很少幾次就可以找出不規(guī)則球。下面討論N個(gè)球要多少次才能確定不規(guī)則球。最佳輸入能夠使天平的三種情況出現(xiàn)的次數(shù)均勻。如果是最佳輸入，系統(tǒng)的信息量只剩下原來(lái)的三分之一。由于對(duì)N個(gè)球，如果N不能被3整除，第一次就找不到最佳輸入。對(duì)N個(gè)球可以在[log3(2*N)]+1次內(nèi)找出不規(guī)則球。
第二個(gè)程序是測(cè)試上面兩種算法的性能
#ifdef _TEST_TIME_
#include <windows.h>
int main()
{
const int inc = 20;
DWORD time;
CGuessBall guess;
for (int i=0; i<2; i++)
{
for (int j=12; j< 12+inc; j++)
{
time = 0;
for (int t=0; t<j*2; t++)
{
guess.Init(j, i);
DWORD start = GetTickCount();
while (1)
{
VectorInt left, right;
guess.GetBestInput(left, right);
int fd = guess.CheckFeedback(left, right, t);
int rz = guess.RemoveImpsAns(fd);
if (rz == 1)
break;
}
time += GetTickCount()-start;
}
time /= j*2;
printf("方法：%d\t球數(shù)：%d\t平均時(shí)間：%d\n", i, j, time);
}
}
return 0;
}
#endif
這是測(cè)試結(jié)果：
方法：0 球數(shù)：12 平均時(shí)間：0
方法：0 球數(shù)：13 平均時(shí)間：0
方法：0 球數(shù)：14 平均時(shí)間：0
方法：0 球數(shù)：15 平均時(shí)間：0
方法：0 球數(shù)：16 平均時(shí)間：0
方法：0 球數(shù)：17 平均時(shí)間：1
方法：0 球數(shù)：18 平均時(shí)間：1
方法：0 球數(shù)：19 平均時(shí)間：1
方法：0 球數(shù)：20 平均時(shí)間：5
方法：0 球數(shù)：21 平均時(shí)間：5
方法：0 球數(shù)：22 平均時(shí)間：5
方法：0 球數(shù)：23 平均時(shí)間：6
方法：0 球數(shù)：24 平均時(shí)間：6
方法：0 球數(shù)：25 平均時(shí)間：6
方法：0 球數(shù)：26 平均時(shí)間：27
方法：0 球數(shù)：27 平均時(shí)間：26
方法：0 球數(shù)：28 平均時(shí)間：25
方法：0 球數(shù)：29 平均時(shí)間：167
方法：0 球數(shù)：30 平均時(shí)間：162
方法：0 球數(shù)：31 平均時(shí)間：157
方法：0 球數(shù)：32 平均時(shí)間：171
方法：0 球數(shù)：33 平均時(shí)間：165
方法：0 球數(shù)：34 平均時(shí)間：163
方法：1 球數(shù)：12 平均時(shí)間：0
方法：1 球數(shù)：13 平均時(shí)間：0
方法：1 球數(shù)：14 平均時(shí)間：0
方法：1 球數(shù)：15 平均時(shí)間：0
方法：1 球數(shù)：16 平均時(shí)間：0
方法：1 球數(shù)：17 平均時(shí)間：0
方法：1 球數(shù)：18 平均時(shí)間：0
方法：1 球數(shù)：19 平均時(shí)間：0
方法：1 球數(shù)：20 平均時(shí)間：0
方法：1 球數(shù)：21 平均時(shí)間：0
方法：1 球數(shù)：22 平均時(shí)間：0
方法：1 球數(shù)：23 平均時(shí)間：0
方法：1 球數(shù)：24 平均時(shí)間：0
方法：1 球數(shù)：25 平均時(shí)間：0
方法：1 球數(shù)：26 平均時(shí)間：0
方法：1 球數(shù)：27 平均時(shí)間：0
方法：1 球數(shù)：28 平均時(shí)間：0
方法：1 球數(shù)：29 平均時(shí)間：0
方法：1 球數(shù)：30 平均時(shí)間：0
方法：1 球數(shù)：31 平均時(shí)間：0
方法：1 球數(shù)：32 平均時(shí)間：0
方法：1 球數(shù)：33 平均時(shí)間：0
方法：1 球數(shù)：34 平均時(shí)間：0
這里是
全部代碼