| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 7189 人关注过本帖, 4 人收藏
标题:关于波瓦松分酒问题的分析
只看楼主 加入收藏
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
结帖率:100%
收藏(4)
已结贴  问题点数:100 回复次数:35 
关于波瓦松分酒问题的分析
问题描述:某人有12品脱的啤酒一瓶,想从中倒出6品脱,但他没有6品脱的容器,他只有8品脱和5品脱的两个容器,怎样到才可以将12品脱的酒分为两个6品脱的?

问题原贴见https://bbs.bccn.net/thread-438270-1-1.html

类似的用三个容器分液体的问题之前就见过很多。为什么这个叫“波瓦松分酒”呢?查了一下,原来它是由法国著名数学家波瓦松提出的。看来我孤陋寡闻了,法国数学家我知道笛卡尔、傅立叶、柯西、拉普拉斯、拉格朗日等等。波瓦松?头一回听到,而且除了这个分酒问题我再没找到关于他的任何信息。

话说回来,我从网上找到的关于这个分酒问题的解析都是一种数论方法。通过解一个二元一次不定方程来找倒酒路径,结构非常简洁优美。但遗憾的是,只有这么一个结论,没有原因分析。它一定是最短路径么?它能推广到多元么?不管怎样,我很佩服第一个想到这种方法的人(波瓦松?)。

关于上面说的数论方法,网上代码无算,就不在这里重复了。我们还是说说这题从图论角度的解决方法。

之前我写过一篇商人过河问题的分析(https://bbs.bccn.net/viewthread.php?tid=436942),这个分酒问题与它有着相似的结构。比如它们都有有限种状态,有一个开始状态,有一个终止状态,有有限种状态转移方法(函数)。下面来具体解析这个分酒问题。

问题包含的属性:

1、有3个容器,每个容器有固定的容量,但没有刻度。

2、有固定体积的液体(它是什么并不重要,往往是装满最大容积的容器)。

3、液体可以从一个容器倒入另一个容器。由于容器上没有刻度,所以为了精确掌握这个液体转移的过程,那么转移的方式只能是倒空一个容器或倒满另一个容器。

由第1、第2条属性(静态)构成结点,第3条属性(动态)构成连线,形成一张图。问题这时就转换成寻找图中连接初始点(12品脱瓶满)到终止结点(12品脱瓶半)的路径的问题。

路径的寻找目前只有两种方式,深度优先(DFS)或广度优先(BFS)。在原贴的探讨中大家对有多少种分酒方式更感兴趣(同时对递归结构也有兴趣)。对于这种在全部解空间的搜索,DFS更适合。它结构简单,所需的空间多数情况下更少。

下面以一段教学级代码展示以DFS遍历寻找所有可行路径的方法。由于可行路径比较多(共121种),建议将结果输出的文本文件查看。

程序代码:
#include <stdio.h>

typedef int BOOL;
#define TRUE    1
#define FALSE    0

typedef char byte;
typedef struct //该结构体定义了状态结点,包含3个容器。使用中它们的值表示当时3个容器中液体的体积。
{
    byte bottle12;
    byte bottle8;
    byte bottle5;
}STATE;

int times = 0;

//以下move系列的6个函数表示6种不同的液体转移方式。参数from是转移前的状态,to是转移后的状态。由于函数的返回值用来返回执行状态了,所以转移后状态采用指针来传递返回。

BOOL move12to8(STATE from, STATE * to) 
{
    if(from.bottle12 == 0 || from.bottle8 == 8)
        return FALSE;
    if(from.bottle12 > 8 - from.bottle8)
    {
        to->bottle12 = from.bottle12 - (8 - from.bottle8);
        to->bottle8 = 8;
    }
    else
    {
        to->bottle12 = 0;
        to->bottle8 = from.bottle8 + from.bottle12;
    }
    to->bottle5 = from.bottle5;
    return TRUE;
}

BOOL move12to5(STATE from, STATE * to)
{
    if(from.bottle12 == 0 || from.bottle5 == 5)
        return FALSE;
    if(from.bottle12 > 5 - from.bottle5)
    {
        to->bottle12 = from.bottle12 - (5 - from.bottle5);
        to->bottle5 = 5;
    }
    else
    {
        to->bottle12 = 0;
        to->bottle5 = from.bottle5 + from.bottle12;
    }
    to->bottle8 = from.bottle8;
    return TRUE;
}

BOOL move8to12(STATE from, STATE * to)
{
    if(from.bottle8 == 0 || from.bottle12 == 12) return FALSE;
    if(from.bottle8 > 12 - from.bottle12)
    {
        to->bottle8 = from.bottle8 - (12 - from.bottle12);
        to->bottle12 = 12;
    }
    else
    {
        to->bottle8 = 0;
        to->bottle12 = from.bottle12 + from.bottle8;
    }
    to->bottle5 = from.bottle5;
    return TRUE;
}

BOOL move8to5(STATE from, STATE * to)
{
    if(from.bottle8 == 0 || from.bottle5 == 5) return FALSE;
    if(from.bottle8 > 5 - from.bottle5)
    {
        to->bottle8 = from.bottle8 - (5 - from.bottle5);
        to->bottle5 = 5;
    }
    else
    {
        to->bottle8 = 0;
        to->bottle5 = from.bottle5 + from.bottle8;
    }
    to->bottle12 = from.bottle12;
    return TRUE;
}

BOOL move5to12(STATE from, STATE * to)
{
    if(from.bottle5 == 0 || from.bottle12 == 12) return FALSE;
    if(from.bottle5 > 12 - from.bottle12)
    {
        to->bottle5 = from.bottle5 - (12 - from.bottle12);
        to->bottle12 = 12;
    }
    else
    {
        to->bottle5 = 0;
        to->bottle12 = from.bottle5 + from.bottle12;
    }
    to->bottle8 = from.bottle8;
    return TRUE;
}

BOOL move5to8(STATE from, STATE * to)
{
    if(from.bottle5 == 0 || from.bottle8 == 8) return FALSE;
    if(from.bottle5 > 8 - from.bottle8)
    {
        to->bottle5 = from.bottle5 - (8 - from.bottle8);
        to->bottle8 = 8;
    }
    else
    {
        to->bottle5 = 0;
        to->bottle8 = from.bottle5 + from.bottle8;
    }
    to->bottle12 = from.bottle12;
    return TRUE;
}

BOOL equal(STATE s1, STATE s2) //判断两个状态是否相等
{
    if(s1.bottle12 != s2.bottle12) return FALSE;
    if(s1.bottle8 != s2.bottle8) return FALSE;
    if(s1.bottle5 != s2.bottle5) return FALSE;
    return TRUE;
}

BOOL contain(STATE s, STATE * path, int pathLength) //判断在path路径集合中是否包含了状态s。
{
    int i;
    for(i = 0; i < pathLength; i++)
    {
        if(equal(s, path[i]))
            return TRUE;
    }
    return FALSE;
}

void output(STATE * path, int pathLength) //输出一条路径(分酒方式)
{
    int i;
    times++;
    printf("%d:\n", times);
    for(i = 0; i < pathLength; i++)
    {
        printf("%2d:[%2d][%2d][%2d]\n", i, path[i].bottle12, path[i].bottle8, path[i].bottle5);
    }
    puts("");
}

void search(STATE start, STATE end, STATE * path, int pathLength) //递归遍历所有的路径
{
    STATE temp;

    path[pathLength] = start;
    pathLength++;
    
    if(equal(start, end))
        output(path, pathLength);
    
    if(move12to8(start, &temp) && !contain(temp, path, pathLength))
        search(temp, end, path, pathLength);
    if(move12to5(start, &temp) && !contain(temp, path, pathLength))
        search(temp, end, path, pathLength);
    if(move8to12(start, &temp) && !contain(temp, path, pathLength))
        search(temp, end, path, pathLength);
    if(move8to5(start, &temp) && !contain(temp, path, pathLength))
        search(temp, end, path, pathLength);
    if(move5to12(start, &temp) && !contain(temp, path, pathLength))
        search(temp, end, path, pathLength);
    if(move5to8(start, &temp) && !contain(temp, path, pathLength))
        search(temp, end, path, pathLength);
}

int main()
{
    STATE path[14 * 13 / 2];
    search((STATE){12, 0, 0}, (STATE){6, 6, 0}, path, 0);
    return 0;
}


很多时候我们的问题不需要找到所有解,我们只关心最优解。甚至当有多个最优解时我们只需要其中一个(具体是哪个无所谓)。这时BFS往往更适合。

下面再展示一段应用BFS来寻找最短路径的代码。数据结构没有变化,改变的是搜索函数。

程序代码:
#include <stdio.h>

typedef int BOOL;
#define TRUE    1
#define FALSE    0

typedef char byte;
typedef struct
{
    byte bottle12;
    byte bottle8;
    byte bottle5;
}STATE;

BOOL move12to8(STATE from, STATE * to)
{
    if(from.bottle12 == 0 || from.bottle8 == 8)
        return FALSE;
    if(from.bottle12 > 8 - from.bottle8)
    {
        to->bottle12 = from.bottle12 - (8 - from.bottle8);
        to->bottle8 = 8;
    }
    else
    {
        to->bottle12 = 0;
        to->bottle8 = from.bottle8 + from.bottle12;
    }
    to->bottle5 = from.bottle5;
    return TRUE;
}

BOOL move12to5(STATE from, STATE * to)
{
    if(from.bottle12 == 0 || from.bottle5 == 5)
        return FALSE;
    if(from.bottle12 > 5 - from.bottle5)
    {
        to->bottle12 = from.bottle12 - (5 - from.bottle5);
        to->bottle5 = 5;
    }
    else
    {
        to->bottle12 = 0;
        to->bottle5 = from.bottle5 + from.bottle12;
    }
    to->bottle8 = from.bottle8;
    return TRUE;
}

BOOL move8to12(STATE from, STATE * to)
{
    if(from.bottle8 == 0 || from.bottle12 == 12) return FALSE;
    if(from.bottle8 > 12 - from.bottle12)
    {
        to->bottle8 = from.bottle8 - (12 - from.bottle12);
        to->bottle12 = 12;
    }
    else
    {
        to->bottle8 = 0;
        to->bottle12 = from.bottle12 + from.bottle8;
    }
    to->bottle5 = from.bottle5;
    return TRUE;
}

BOOL move8to5(STATE from, STATE * to)
{
    if(from.bottle8 == 0 || from.bottle5 == 5) return FALSE;
    if(from.bottle8 > 5 - from.bottle5)
    {
        to->bottle8 = from.bottle8 - (5 - from.bottle5);
        to->bottle5 = 5;
    }
    else
    {
        to->bottle8 = 0;
        to->bottle5 = from.bottle5 + from.bottle8;
    }
    to->bottle12 = from.bottle12;
    return TRUE;
}

BOOL move5to12(STATE from, STATE * to)
{
    if(from.bottle5 == 0 || from.bottle12 == 12) return FALSE;
    if(from.bottle5 > 12 - from.bottle12)
    {
        to->bottle5 = from.bottle5 - (12 - from.bottle12);
        to->bottle12 = 12;
    }
    else
    {
        to->bottle5 = 0;
        to->bottle12 = from.bottle5 + from.bottle12;
    }
    to->bottle8 = from.bottle8;
    return TRUE;
}

BOOL move5to8(STATE from, STATE * to)
{
    if(from.bottle5 == 0 || from.bottle8 == 8) return FALSE;
    if(from.bottle5 > 8 - from.bottle8)
    {
        to->bottle5 = from.bottle5 - (8 - from.bottle8);
        to->bottle8 = 8;
    }
    else
    {
        to->bottle5 = 0;
        to->bottle8 = from.bottle5 + from.bottle8;
    }
    to->bottle12 = from.bottle12;
    return TRUE;
}

BOOL equal(STATE s1, STATE s2)
{
    if(s1.bottle12 != s2.bottle12) return FALSE;
    if(s1.bottle8 != s2.bottle8) return FALSE;
    if(s1.bottle5 != s2.bottle5) return FALSE;
    return TRUE;
}

BOOL contain(STATE s, STATE * path, int pathLength)
{
    int i;
    for(i = 0; i < pathLength; i++)
    {
        if(equal(s, path[i]))
            return TRUE;
    }
    return FALSE;
}

void output(STATE * path, int pathLength)
{
    int i;
    for(i = pathLength - 1; i >= 0; i--)
    {
        printf("%2d:[%2d][%2d][%2d]\n", pathLength - i - 1, path[i].bottle12, path[i].bottle8, path[i].bottle5);
    }
    puts("");
}

void search(STATE start, STATE end)
{
    STATE path[14 * 13 / 2];
    STATE listState[14 * 13 / 2];
    STATE temp;
    int mapPreIndex[14 * 13 / 2] = {0};
    int listLength, i, j;
    
    listState[0] = start;
    listLength = 1;
    
    for(i = 0; i < listLength; i++)
    {
        if(move12to8(listState[i], &temp) && !contain(temp, listState, listLength))
        {
            listState[listLength] = temp;
            mapPreIndex[listLength] = i;
            listLength++;
            if(equal(temp, end)) break;
        }
        if(move12to5(listState[i], &temp) && !contain(temp, listState, listLength))
        {
            listState[listLength] = temp;
            mapPreIndex[listLength] = i;
            listLength++;
            if(equal(temp, end)) break;
        }
        if(move8to12(listState[i], &temp) && !contain(temp, listState, listLength))
        {
            listState[listLength] = temp;
            mapPreIndex[listLength] = i;
            listLength++;
            if(equal(temp, end)) break;
        }
        if(move8to5(listState[i], &temp) && !contain(temp, listState, listLength))
        {
            listState[listLength] = temp;
            mapPreIndex[listLength] = i;
            listLength++;
            if(equal(temp, end)) break;
        }
        if(move5to12(listState[i], &temp) && !contain(temp, listState, listLength))
        {
            listState[listLength] = temp;
            mapPreIndex[listLength] = i;
            listLength++;
            if(equal(temp, end)) break;
        }
        if(move5to8(listState[i], &temp) && !contain(temp, listState, listLength))
        {
            listState[listLength] = temp;
            mapPreIndex[listLength] = i;
            listLength++;
            if(equal(temp, end)) break;
        }
    }

    if(equal(listState[listLength - 1], end))
    {
        i = listLength - 1;
        for(j = 0; i > 0; j++)
        {
            path[j] = listState[i];
            i = mapPreIndex[i];
        }
        path[j++] = listState[0];
        output(path, j);
    }
}

int main()
{
    search((STATE){12, 0, 0}, (STATE){6, 6, 0});
    return 0;
}


以上代码为教学示例,下面再来段我本来的风格代码吧,依旧是BFS。

程序代码:
#include <stdio.h>

#define analyze(b, s)    ({b[0]=(s)>>8; b[1]=(s)>>4&0xF; b[2]=(s)&0xF;})
#define merge(b)        (b[0]<<8|b[1]<<4|b[2])

int search(int ss, int se, int * path)
{
    static int bc[] = {12, 8, 5};
    int map[1 << 12] = {0}, list[96] = {ss}, b[3];
    int n = 1, i, j, k, t;
    
    for(map[ss] = -1, i = 0; i < n && !map[se]; i++)
    for(j = 0; j < 3; j++)
    for(k = 0; k < 3; k++)
    {
        analyze(b, list[i]);
        if(j == k || b[j] == 0 || b[k] == bc[k]) continue;
        t = b[j] + b[k];
        b[k] = t > bc[k] ? bc[k] : t;
        b[j] = t - b[k];
        if(map[t = merge(b)]) continue;
        list[n++] = t;
        map[t] = list[i];
    }
    for(t = se, i = 0; map[t] > 0; t = map[t]) path[i++] = t;
    path[i++] = ss;
    return i;
}

void output(int * path, int n)
{
    int b[3], i;
    for(i = n - 1; i >= 0; i--)
    {
        analyze(b, path[i]);
        printf("%2d:[%2d][%2d][%2d]\n", n - i - 1, b[0], b[1], b[2]);
    }
}

int main()
{
    int path[96], n;
    n = search(0xC00, 0x660, path);
    output(path, n);
    return 0;
}


分数是散给大家的,来者有份,但最好是就相关问题的探讨。尽量别回复“看看”、“接分”之类的,这是对我和我的劳动的不尊重。
搜索更多相关主题的帖子: 拉普拉斯 数学家 笛卡尔 而且 法国 
2014-11-11 09:45
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
晕,我还以为是我操作错了呢。感谢静神加精,不过之后被我取消了(以为是自己点错了加的,之前正在加色置顶)。再加回来

重剑无锋,大巧不工
2014-11-11 09:56
wp231957
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:神界
等 级:贵宾
威 望:423
帖 子:13688
专家分:53332
注 册:2012-10-18
收藏
得分:12 
标记

DO IT YOURSELF !
2014-11-11 10:05
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:12 
96是怎么来的,看不明白。


[fly]存在即是合理[/fly]
2014-11-11 10:06
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
杨大哥的代码还是那么晦涩呀


[fly]存在即是合理[/fly]
2014-11-11 10:12
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 4 楼 azzbcc
呵呵,我正在想谁第一个问这个96的来历。

这是一个粗略的可能状态数量的估算。如果12份酒可以任意放入3个瓶子内,那么可能的放法有C(14,2)种,14 * 13 / 2 = 91。虽然实际数量应该远比这少,但在得到结果前我不假设能少多少。之后为了对齐就选择了96这个数(纯粹是个人喜好)。

重剑无锋,大巧不工
2014-11-11 10:21
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
再补充一段更通用的代码,通过调整宏参数可以改变问题范围。

程序代码:
#include <stdio.h>

#define BOTTLE_COUNT        3
#define BOTTLE_CAPACITIES    {12, 8, 5}
#define DATA_BITS            4
#define STATES_SIZE            (1 << DATA_BITS * BOTTLE_COUNT)

void analyze(int s, int * b)
{
    int i;
    for(i = 0; i < BOTTLE_COUNT; i++)
        b[i] = s >> ((BOTTLE_COUNT - i - 1) * DATA_BITS) & ((1 << DATA_BITS) - 1);
}

int merge(const int * b)
{
    int s, i;
    for(s = i = 0; i < BOTTLE_COUNT; s = (s << DATA_BITS) + b[i++]);
    return s;
}

void output(int * path, int n)
{
    int b[BOTTLE_COUNT], i, j;
    for(i = n - 1; i >= 0; i--, puts(""))
    {
        printf("%2d", n - i - 1);
        analyze(path[i], b);
        for(j = 0; j < BOTTLE_COUNT; printf("[%2d]", b[j++]));
    }
}

int search(int ss, int se, int * path)
{
    int b[BOTTLE_COUNT];
    int bc[] = BOTTLE_CAPACITIES;
    int map[STATES_SIZE] = {0};
    int list[STATES_SIZE];
    int n, i, j, k, t;
    
    map[ss] = -1;
    for(list[i = 0] = ss, n = 1; i < n && !map[se]; i++)
    for(j = 0; j < BOTTLE_COUNT; j++)
    for(k = 0; k < BOTTLE_COUNT; k++)
    {
        analyze(list[i], b);
        if(j == k || b[j] == 0 || b[k] == bc[k]) continue;
        t = b[j] + b[k];
        b[k] = t > bc[k] ? bc[k] : t;
        b[j] = t - b[k];
        if(map[t = merge(b)]) continue;
        list[n++] = t;
        map[t] = list[i];
    }
    for(t = se, i = 0; map[t] > 0; t = map[t]) path[i++] = t;
    path[i++] = ss;
    return i;
}

int main()
{
    int path[STATES_SIZE], n;
    n = search(merge((int []){12, 0, 0}), merge((int []){6, 6, 0}), path);
    output(path, n);
    return 0;
}

重剑无锋,大巧不工
2014-11-11 10:23
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
以下是引用azzbcc在2014-11-11 10:12:18的发言:

杨大哥的代码还是那么晦涩呀

前两段能看懂吗?

重剑无锋,大巧不工
2014-11-11 10:23
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
回复 8 楼 beyondyf
前两段不是你的风格,哈哈。


[fly]存在即是合理[/fly]
2014-11-11 10:25
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 9 楼 azzbcc
只要你们喜欢,我写哪种代码无所谓。这种分析贴目的是为了让更多的人看懂,而不是炫耀我的编码水平(虽然后来我也炫耀了)。

重剑无锋,大巧不工
2014-11-11 10:30
快速回复:关于波瓦松分酒问题的分析
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.028600 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved