随笔 - 51, 文章 - 1, 评论 - 41, 引用 - 0
数据加载中……

猜数字的一种解法

         本文将给出解答猜数字游戏(guess number)的一种算法,最多6步就可猜出结果。这个的解法需要用到部分信息论的知识
    猜数字问题表述如下:答案是09十个数的四位排列(没有重复元素)。每猜一次,游戏比较答案和输入这两组排列,反馈aAbBaA表示有a个数字数值正确位置正确,bB表示b个数字数值正确位置错误。
    考虑问题的互动方式,这道题目属于输入反馈的问题。每次输入,从反馈中获取部分信息,当获得系统的全部信息时,就能猜出答案。所以解这个问题的关键是寻找合适的输入使反馈的信息量最大。
    这道题的解法思路比较简单,由于是有穷状态,而且数量不大,可用穷举法解答。比较所有可能的输入,找出最佳输入(某个标准下)。问题变成了如何衡量输入的好坏。输入越好则反馈的信息越大,山农给出的信息量的定义是衡量输入好坏的标准。信息量是不确定性的大小,如果某个事件的概率为P,则它含有的信息量为log(1/P)。具体的理论可以参考一本关于信息论的书。
    具体到猜数字这个题目,答案有多种可能。得到反馈前,每一个输入的反馈有不同的可能。得到反馈后,反馈是确定的,不确定性变为0。这样问题的信息量变小了。前后的信息量之差就是这个输入能够得到的信息量。

统计反馈前这个输入可能得到的反馈,求出各种反馈的概率,可由下面公式计算出反馈前的信息量:
H=P1*log(1/P1)+P2*log(1/P2)+...P1P2等分别为不同反馈的概率。
反馈后,这个输入的反馈是确定的,信息量为0比较所有输入能够得到信息量,就能找出最佳的输入。

统计反馈前这个输入可能得到的反馈

// 把输入和所有可能的答案比较,得到所以不同反馈可能出现的次数
// 输入参数:input输入
// 输出参数:feedbacks反馈可能出现的次数
void GetPsbFeedbacksNum(VectorInt
& feedbacks, const VectorInt& input)
{
        
// 和所有可能的答案比较
    
for (int j=0; j<ALL_ANS_NUM; j++)
    {
        
// 答案是否已经被排除
        
if (g_AnsState[j] != 0)
            continue;
        feedbacks[GetFeedback(input, g_AllAns[j])]
++;
    }
}

计算这个输入能够获得的信息量
// 计算信息量
// 输入参数:不同反馈出现的次数
// 返回值:信息量
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;
}

这样就得到每个输入的信息量。下面讨论如何枚举所有可能的输入。
输入的种类有10*9*8*7种,把每一种输入和所有可能答案比较。这方法比较直观,但运算次数太多。
// 得到最佳的输入,不分类直接比较的方法
// 最佳输入存放在g_AnsGuess中
void GetBestInputNoSort()
{
    
double max_entropy = 0.;    // 存放最大的信息量
    VectorInt feedbacks((ANS_SIZE
+1)*(ANS_SIZE+1), 0);    // 反馈的结果分类

    
// 比较所有输入的信息量
    
for (int i=0; i<ALL_ANS_NUM; i++)
    {
        
// 这个输入的信息量是否是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]); 

        
// 计算信息量
        
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];
        }
    }    
}

由于第一次输入,各种输入能够得到的信息量是一样的,因此第一次可以不比较,任给一组输出。改进后的代码如下:
// 得到最佳的输入,不分类直接比较的方法,但优化过第一次输入。
// 最佳输入存放在g_AnsGuess中
void GetBestInputIpvFst()
{
    
// 如果是第一次,所有输入的信息量是一样的,任选一个
    
if (g_isFirstTime)
    {
        g_isFirstTime 
= 0;
        g_AnsGuess 
= g_AllAns[0];
    }
    
else
        GetBestInputNoSort();
}

第一次输入时10个元素之间是没有分别的。沿着这个思路考虑,第二次输入时,6个没有参与输入的元素,也没有分别。举例来说,第一次输入{0,1,2,3},则4,5,6,7,8,9六个元素属同一类元素,在第二次输入时可以相互替换。如{0,1,2,4}和{0,1,2,5}两组输入能够得到的信息量应该相同。把元素分类枚举则可以优化算法。
分类方法如下,参入输出的元素单独成一类,没有参与的元素是一类。第一次输入时,只有一类元素,这类元素个数为10。第二次输入时,有五类元素,有四类元素个数为1,一类元素个数为6。依次类推。关于如何枚举见《从集合中枚举子集》
// 得到最佳的输入,元素分类的方法
// 最佳输入存放在g_AnsGuess中
void GetBestInputSort()
{
    
double max_entropy = 0.;    // 存放最大的信息量
    VectorInt feedbacks((ANS_SIZE
+1)*(ANS_SIZE+1), 0);// 反馈的结果分类

    
// 初始化枚举
    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表示该元素没有输入过
        AssembleInput(setsub);

//        // 这个输入的信息量是否是0
//        if (g_InputState[GetSetPosition(setsub)] == 1)
//            continue;

        
// 是否只在可能的答案中搜索最佳输入
//        if (g_AnsState[GetSetPosition(setsub)] != 0)
//            continue;

        
// 得到所有可能反馈的数目
        feedbacks.assign((ANS_SIZE
+1)*(ANS_SIZE+1), 0);
        GetPsbFeedbacksNum(feedbacks, setsub);

        
// 计算信息量
        
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();
}

分类的方法可以大大提升运算速度,下面的测试会证明这一点。但当参与输入元素慢慢增加时,分类就不那么重要,而且调用CSetIterAgent也是一笔不小的开销。将第一种算法和分类法结合:
// 不分类法和分类法的混合法
// 输入参数:num表示当输入元素个数等于或超过num时用直接法
void GetBestInputBlend(
int num)
{
    
// 计算没有输入过的元素个数
    
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();
}

下面给出这些算法的测试结果。测试方法是将10*9*8*7种答案依次用这些算法求解,统计猜出每个答案需要多少次数。一共花费了多少时间。
1次         1
2次         12
3次         261
4次         2082
5次         2500
6次         184
平均次数:4.51190
N次是指N次输入反馈后,就可以确定答案,并不指第N次输入的反馈是4A0B。
花费的时间:
GetBestInputNoSort:       8h也没有算完
GetBestInputIpvFst:         9385s
GetBestInputSort:            1596s
GetBestInputBlend7:       2151s
GetBestInputBlend10:     1515s

这些方法在本质上是一样的,即在所有的输入中寻找反馈信息量最大的输入。下面考虑其他方法,比较这些方法的差别。
如果缩小寻找范围,不考虑不是答案的输入。代码如下:
取消GetBestInputNoSort函数中
        // 是否只在可能的答案中搜索最佳输入
        
if (g_AnsState[i] != 0)
            continue;
和GetBestInputSort函数中
        // 是否只在可能的答案中搜索最佳输入
        
if (g_AnsState[GetSetPosition(setsub)] != 0)
            continue;
这两行注释。
测试结果如下:
1次       1
2次       16
3次       228
4次       1555
5次       2688
6次       542
7次       10
平均次数:4.70218
运行时间:
GetBestInputIpvFst:1375s
GetBestInputSort:   97s
缩小范围后,速度有很多提升,但平均次数增加了。

再考虑另外一种方法,不从信息量的角度考虑。用第一个可能为答案的排列作为输入。
// 得到第一个可能的答案
void GetFstPsbInput()
{
    
for (int i=0; i<ALL_ANS_NUM; i++)
    {
        
if (g_AnsState[i] == 0)
        {
            g_AnsGuess 
= g_AllAns[i];
            break;
        }
    }
}
测试结果:
1次       1
2次       15
3次       211
4次       1240
5次       2108
6次       1203
7次       252
8次       10
平均次数:5.00515
花费的时间:7s
这个方法令人吃惊的是它的速度,如此简单却又不错的效果。平均次数要比上面两个方法差些。
上面的测试结果是在vc2005的release下编译测试。

         本文用信息量大小作为判断最佳输入的标准,相比其他算法平均步数较少,但花费的时间较多。如何缩短计算时间将在以后的文章中继续探讨。此外从测试中看出,方法2,3在两次内猜中答案的次数比方法1多。在这个意义下方法2,3比方法1要优。以后还会在不同的意义下比较各类算法。大家有什么好的想法可以联系我,大家一起讨论。我的邮箱lemene@sina.com.cn

代码下载

posted on 2007-11-26 16:42 lemene 阅读(4033) 评论(5)  编辑 收藏 引用

评论

# re: 猜数字的一种解法  回复  更多评论   

见过的最好结果6步
100%
2008-03-13 12:54 | QQ474073341

# re: 猜数字的一种解法  回复  更多评论   

我已经证明了六步不可能猜完所有的数
149588829
2008-03-13 14:46 | yczni

# re: 猜数字的一种解法[未登录]  回复  更多评论   

可以六步完成,这里是指最多六步就知道确切的结果。不是指六步就反馈4A0B。有点细微的差别,如果一定要反馈4A0B才算成功,则需要七步。
2008-03-14 23:52 | lemene

# re: 猜数字的一种解法  回复  更多评论   

依靠反馈的熵的最大值来决定最佳猜测感觉没有依据,我觉得应该是根据每种可能的反馈导致正确答案范围的减小量来作为信息量比较合适。
2011-05-06 21:49 | 奔跑

# re: 猜数字的一种解法[未登录]  回复  更多评论   

@奔跑
本算法基本思想也可以理解“根据每种可能的反馈导致正确答案范围的减小量来作为信息量”,具体的算法只是这一思想的数学建模。
2011-05-07 17:52 | lemene

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理