搜索
编程论坛 → 开发语言 → 『 C语言论坛 』 → 关于波瓦松分酒问题的分析
标题：关于波瓦松分酒问题的分析
只看楼主
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等　级：贵宾
威　望：103
帖　子：3282
专家分：12654
注　册：2008-1-21
结帖率：100%
楼主
 已结贴√  问题点数：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
第 2 楼
 得分:0 
晕，我还以为是我操作错了呢。感谢静神加精，不过之后被我取消了（以为是自己点错了加的,之前正在加色置顶）。再加回来

重剑无锋，大巧不工
2014-11-11 09:56
wp231957
Rank: 16Rank: 16Rank: 16Rank: 16
来　自：神界
等　级：版主
威　望：422
帖　子：13681
专家分：53296
注　册：2012-10-18
第 3 楼
 得分:12 
标记

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


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


[fly]存在即是合理[/fly]
2014-11-11 10:12
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等　级：贵宾
威　望：103
帖　子：3282
专家分：12654
注　册：2008-1-21
第 6 楼
 得分: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
第 7 楼
 得分: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
第 8 楼
 得分: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
第 9 楼
 得分:0 
回复 8 楼 beyondyf
前两段不是你的风格，哈哈。


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

重剑无锋，大巧不工
2014-11-11 10:30



参与讨论请移步原网站贴子：https://bbs.bccn.net/thread-438421-1-1.html




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

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