|
|
12球問題表述如下：有12個球，有一個球的重量與其它球的重量不一致。用一臺沒有刻度的天平稱3次把這個球找出。當然12球問題可以推廣至N個球。
首先考慮這道題目的模式，它屬于輸入反饋的問題。每一次輸入（即稱一次）便會有一個反饋信息，分析反饋信息再次輸入，直到把問題解決。通過一次次輸入反饋、這類問題解法思路較簡單，由于是有窮狀態，狀態數目不大，可以用窮舉法解答。比較所有的輸入，找出最佳輸入（某個標準意義下）。問題是如何衡量輸入的好壞。直觀上，輸入越好，反饋的信息就越大。問題變成了對信息的量化。山農給出了信息量的定義是解決問題的關鍵。信息量是不確定性的大小。如果某個事件的概率為P，則它含有的信息量為log(1/p)。具體理論請參考關于信息論方面的書籍。（這個問題和猜數字很像，大家參考此文《猜數字的一種解法》）。
具體到這個12球問題。12個球從0-11編號。0號球為較輕的球可能性為1/24。這個事件的信息量log(24)。同理0號球為重球這個事件的信息量為log(24)。這樣的事件有24個，每個事件出現的概率1/24，所以整個系統的信息量24*(1/24*log(24))，即log(24)。
下面我們考慮一次具體的輸入：
第一次輸入，天平左端放0號球，右端放1號球。反饋信息可能為平衡，左傾，右傾。 平衡：這時0，1號球是標準球。根據上面的計算過程，同樣可以計算出此時系統含有的信息量20*(1/20*log(20))，即log(20)。這次輸入獲得的信息log(24)-log(20)。
左傾：可能的情況，1號球為輕球，2號球為重球。此時系統的信息量log(2)。獲得的信息log(24)-log(2)。
右傾：同左傾，此時系統的信息量log(2)。獲得的信息log(24)-log(2)。
這次輸入，出現平衡的概率20/24，出現左傾的概率2/24，出現右傾的概率2/24。這可以計算這次輸入能夠獲得的平均信息量為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)。
下面就要枚舉所有可能的輸入，找出平均信息量最大的輸入。枚舉需要些技巧，需要把球分類，例如第一次輸入時每個球可以看成相同，左右天平放的球數為1，2，3，4，5，6，一共六情況。如果把每個球區別看待枚舉的次數將會很多。下面介紹分類方法。
根據球的狀態，分成4類，一類：標準球即排出不標準的可能性，二類：只可能為輕球，三類：只可能為重球，四類：可能為輕球也可能為重球。
 // 把球分類
// 輸出參數：type 表示對應球的類型，0為標準球，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;
}
}
// 返回四個數組，分別表示四類球
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);
}
}
// 使用分類法得到最佳輸入
// 輸出參數：left，right左右天平球的標號
void CGuessBall::GetBestInputSort(VectorInt& left, VectorInt& right )
{
double max_entropy = 0.0;
// 把球分類
VectorInt types(m_iNumOfBalls, 0);
SortBalls(types);
VectorInt t[4];
SortBalls(t[0], t[1], t[2], t[3]);
// 枚舉所有可能的輸入組合
// 首先找出i個球，左右天平各方i/2個球。
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))
{
// 再從i個球中找出i/2個球
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++;
}
}
// 把球的類型轉化成具體的球號
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]++;
}
// 檢查是否是理論最優，提前返回
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;
}
要使得到的信息量最大，就要使天平左傾，右傾，平衡的出現的概率盡可能相等。四類球，只有三類影響平衡，如果它們的個數能被3整除，左右天平各放三分之一份球。當然也有不能被3整除的情況。三類球，每一類均可能有余數0，1，2。組合起來一共有27種情況。考慮這27種情況配合標準球如何分配。得到以下的算法，先將三類球三等分，然后再考慮27種余數情況，得到第二種算法。
// 直接法得到最佳輸入
void CGuessBall::GetBestInputDirect(VectorInt& left, VectorInt& right)
{
// 第一次輸入，沒有標準球。
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
{ // 有標準球
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;
}
這里要注意，如果有標準球則能達到最佳的輸入。所以第一次沒有標準球要區別對待。此外其實沒有27種情況，因為第二，三類不可能和第四類同時出現。
這是一個測試程序 ，解答12球的問題，它輸出左右天平放的球的編號，等待用戶判斷左傾，右傾還是平衡，直到輸出結果。
#ifdef _TEST_
int main()
{
int size = 12;
CGuessBall guess(size);
while (1)
{
VectorInt left, right;
int fd;
guess.GetBestInput(left, right);
// 輸出左右天平的編號
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("猜出結果：%d球為%s球", ans/2, ans%2?"重":"輕");
break;
}
else if (rz < 1)
{
printf("輸入錯誤");
break;
}
else
continue;
}
}
#endif
從程序運行情況看，很多球也很少幾次就可以找出不規則球。下面討論N個球要多少次才能確定不規則球。最佳輸入能夠使天平的三種情況出現的次數均勻。如果是最佳輸入，系統的信息量只剩下原來的三分之一。由于對N個球，如果N不能被3整除，第一次就找不到最佳輸入。對N個球可以在[log3(2*N)]+1次內找出不規則球。
第二個程序是測試上面兩種算法的性能
#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球數：%d\t平均時間：%d\n", i, j, time);
}
}
return 0;
}
#endif
這是測試結果： 方法：0 球數：12 平均時間：0 方法：0 球數：13 平均時間：0 方法：0 球數：14 平均時間：0 方法：0 球數：15 平均時間：0 方法：0 球數：16 平均時間：0 方法：0 球數：17 平均時間：1 方法：0 球數：18 平均時間：1 方法：0 球數：19 平均時間：1 方法：0 球數：20 平均時間：5 方法：0 球數：21 平均時間：5 方法：0 球數：22 平均時間：5 方法：0 球數：23 平均時間：6 方法：0 球數：24 平均時間：6 方法：0 球數：25 平均時間：6 方法：0 球數：26 平均時間：27 方法：0 球數：27 平均時間：26 方法：0 球數：28 平均時間：25 方法：0 球數：29 平均時間：167 方法：0 球數：30 平均時間：162 方法：0 球數：31 平均時間：157 方法：0 球數：32 平均時間：171 方法：0 球數：33 平均時間：165 方法：0 球數：34 平均時間：163 方法：1 球數：12 平均時間：0 方法：1 球數：13 平均時間：0 方法：1 球數：14 平均時間：0 方法：1 球數：15 平均時間：0 方法：1 球數：16 平均時間：0 方法：1 球數：17 平均時間：0 方法：1 球數：18 平均時間：0 方法：1 球數：19 平均時間：0 方法：1 球數：20 平均時間：0 方法：1 球數：21 平均時間：0 方法：1 球數：22 平均時間：0 方法：1 球數：23 平均時間：0 方法：1 球數：24 平均時間：0 方法：1 球數：25 平均時間：0 方法：1 球數：26 平均時間：0 方法：1 球數：27 平均時間：0 方法：1 球數：28 平均時間：0 方法：1 球數：29 平均時間：0 方法：1 球數：30 平均時間：0 方法：1 球數：31 平均時間：0 方法：1 球數：32 平均時間：0 方法：1 球數：33 平均時間：0 方法：1 球數：34 平均時間：0 這里是 全部代碼
|