醉汉问题怎么描述？

一个酩酊大醉的农夫站在一片田地的正中央，他每秒钟都会向一个随机的方向迈出一步。那么 1000 秒之后，他与原点的期望距离是多少？如果他走了很多步，那么会离原点越来越远，还是更可能一遍又一遍地走回原点，并停留在附近？

是收敛，还是发散。

为什么要用简单的输入情形手工推演？

给自己一个直觉的认识。然后再用程序证明。

看一下右图中的笑脸，可以看出，有 0.25 的概率距离为 0 个单位，有 0.25 的概率距离为 2 个单位，有 0.5 的概率距离为根号 2 个单位。所以，平均来看，他走出两步之后，会比一步之后更加远离原点。 那么第三步之后呢？如果第二步走到上面或者下面的笑脸，那么第三步会有一半可能使离原点更近，也有一半可能离原点更远。如果第二步走到左侧的笑脸（即原点），那么第三步会使农夫离开原点。如果第二步走到右侧的笑脸，那么第三步会有 0.25 的可能离原点更近，0.75 的可能离原点更远。 看上去似乎醉汉走的步数越多，与原点之间的期望距离就越远。

醉汉模型中的几个类分别起什么作用？

在这个问题中，很明显的三个类是：位置、醉汉、和场地。场地把醉汉和位置联系起来。

class Location (object):
    def __init__(self, x, y):
        """x 和 y 为数值型，可以做加减乘除"""
        #成对的变量，用 tuple 格式做赋值。
        self.x, self.y = x, y

    def move (self, deltaX, deltaY):
        """deltaX 和 deltaY 为数值型，可以是浮点数，即没有限制醉汉的移动方式。
        返回的是另一个 Location"""
        return Location (self.x + deltaX, self.y + deltaY)

    def getX (self):
        return self.x

    def getY (self):
        return self.y

    def distFrom (self, other):
        """other 是另一个 Location"""
        ox, oy = other.x, other.y
        xDist, yDist = self.x - ox, self.y - oy
        return (xDist**2 + yDist**2)**0.5

    def __str__(self):
        return '<' + str (self.x) + ', ' + str (self.y) + '>'

import random, pylab

class Drunk (object):
    def __init__(self, name = None):
        """ 假设 name 是字符串
        返回一个只有名字的 drunk 者 """
        self.name = name

    def __str__(self):
        """匿名者？没有初始化过的 drunk 者？怎么用？"""
        #是不是 self.name != None ?
        if self != None:
            return self.name
        return 'Anonymous'

class Field (object):
    """ 场地的本质是关系：谁在哪里，怎么活动。
    数据属性：
    drunks 字典，将 Drunk 者映射到他的 Location。
    方法属性：
    addDrunk, 添加 Drunk 者.
    moveDrunk, 让 drunk 者用他的方式走到新的 Location，更新字典。
    getLoc, 从字典中提取 drunk 者的当前位置。"""
    
    def __init__(self):
     """ 初始化 Field 不需要参数。
        返回一个字典 drunks，绑定 Drunk 者和他的 Location 位置。
        注意不只一位 drunk 者，location 也可以重合。"""
        self.drunks = {}

    def addDrunk (self, drunk, loc):
        if drunk in self.drunks:
            raise ValueError ('Duplicate drunk')
        else:
            self.drunks [drunk] = loc

    def moveDrunk (self, drunk):
        """只有 drunk 一个参数。其中移动的步长和方向，是某类 drunk 的数据属性"""
        #调用 Drunk 子类中的 takeStep 方法，让他以自己的方式给出移动向量。
        #调用 Location 类中的 move 方法，从原位置经移动向量变为新位置。
        if drunk not in self.drunks:
            raise ValueError ('Drunk not in field')
        #某 Drunk 子类中，定义着对应的 takeStep 方法，返回的是 tuple 格式的向量坐标。
        xDist, yDist = drunk.takeStep ()
        #从 drunks 字典中提取 drunk 者的当前位置。
        currentLocation = self.drunks [drunk]
        #使用 Location 的 move 方法获得一个新位置，更新 drunks 字典中 drunk 者的位置。
        self.drunks [drunk] = currentLocation.move (xDist, yDist)

    def getLoc (self, drunk):
        if drunk not in self.drunks:
            raise ValueError ('Drunk not in field')
        return self.drunks [drunk]

下面三个 Drunk 的子类，限制了醉汉的游走方式。

class UsualDrunk (Drunk):
    """drunk 者的特征是步态，就是定义如何 takeStep。
    正常的 drunk 向各个方向迈一步的概率一致，步长相同。
    返回的是一个向量的坐标元组。"""
    def takeStep (self):
        stepChoices = [(0,1), (0,-1), (1, 0), (-1, 0)]
        return random.choice (stepChoices)


class ColdDrunk (Drunk):
    """这位醉鬼向四个方向的概率都是一样的，但是如果是迈向南方，步子就大一倍。"""
    def takeStep (self):
        stepChoices = [(0.0,1.0), (0.0,-2.0), (1.0, 0.0),\
                       (-1.0, 0.0)]
        return random.choice (stepChoices)


class EWDrunk (Drunk):
    """这是个只向东西两侧走的醉鬼。"""
    def takeStep (self):
        stepChoices = [(1.0, 0.0), (-1.0, 0.0)]
        return random.choice (stepChoices)

Location 类和 Field 类的定义中，看出什么重大决策？

Location 类开始，这个类虽然简单，但明确体现了两个重要的决策。首先，它告诉我们这个模拟中最多只有两个维度。例如，模拟模型中不会包含高度的变化，这和上面的图形是一致的。其次，因为提供给 deltaX 和 deltaY 的值可以是浮点数，不要求是整数，所以这个类没有限制醉汉可能的移动方向。这就对前面的非正式模型进行了扩展。在那个模型中，每一步都是一个长度单位，而且必须平行于 X 轴或 Y 轴。

图 14-2 中的 Field 类也很简单，但也体现了一些值得注意的决策。这个类的作用是将醉汉与位置进行映射。它对位置没有限制，所以可以认为 Field 的范围是无限的。它允许将多个醉汉以位置随机的方式添加到一个 Field 对象中。对醉汉移动的方式没有任何限制，没有禁止多个醉汉出现在同一位置，也没有禁止一个醉汉穿过被其他醉汉占据的空间。

重要决策是：不限制什么。

这些限制是在子类中定义的。

调试醉汉游走程序时，进行了冒烟测试 smoke test？

运行 drunkTest ((0, 1), 100, UsualDrunk) 后，得到的结果令人难以置信：

UsualDrunk random walk of 0 steps
 Mean = 8.634
 Max = 21.6 Min = 1.4
UsualDrunk random walk of 1 steps
 Mean = 8.57
 Max = 22.0 Min = 0.0

走 0 步的平均距离怎么可能比 8 还大？我们的模拟模型中肯定至少有一个 bug。进行了一番调查之后，问题清楚了。在 simWalks 中，函数调用 walk (f, Homer, numTrials) 应该是 walk (f, Homer, numSteps)。

这件事给了我们一个非常重要的教训：看到模拟结果时，永远要持有一种怀疑态度。我们应该扪心自问，这个结果是否真的合理，还要使用对结果非常有把握的参数进行 “冒烟测试”。

在 19 世纪，管道工测试封闭管道系统的一种标准做法是为这个系统充满烟雾。后来，电子工程师使用这个术语描述对某种电子设备的首次测试 —— 接通电源并看看是否冒烟。再后来，软件开发者开始使用这个术语描述对程序进行一次快速测试，看看能否产生有用的结果。

醉汉游走的规律？

普通醉汉，经过 n 次单步游走的平均距离，与游走步数 n 的平方根几乎一致。

可见这个规律，原理不知道。

是不是跟横平竖直的勾股定理有关？

干嘛要在醉汉游走模型中引入图表？

打印输出是能看到一点趋势，但是不如图表来得全面直观。

打印版

def simAll (drunkKinds, walkLengths, numTrials):
    """ 把各种醉鬼 drunkKinds 的情况都模拟出来，请他们各自通过 drunkTest 打印输出平均距离和最大最小距离.
    要求：
    drunkKinds 是元组或列表，元素 Drunk 的几个子类。
    walklengths 是元组或列表，走多少步的各种情况。
    numTrials 是正整数，表示尝试多少次，以便算取平均值和最大最小值。
    返回：
    None。动作和输出都在 drunkTest 里实现。
    """
    for dClass in drunkKinds:
        drunkTest (walkLengths, numTrials, dClass)

# 模拟三种醉鬼在两种步长情况下的移动距离，打印结果。
simAll ((UsualDrunk, ColdDrunk, EWDrunk), (100, 1000), 10)

UsualDrunk random walk of 100 steps
 Mean = 10.38
 Max = 16.1 Min = 1.4
UsualDrunk random walk of 1000 steps
 Mean = 31.59
 Max = 58.7 Min = 8.9
ColdDrunk random walk of 100 steps
 Mean = 25.19
 Max = 42.2 Min = 12.8
ColdDrunk random walk of 1000 steps
 Mean = 256.2
 Max = 305.1 Min = 212.3
EWDrunk random walk of 100 steps
 Mean = 7.2
 Max = 18.0 Min = 0.0
EWDrunk random walk of 1000 steps
 Mean = 23.2
 Max = 42.0 Min = 4.0

能看出 codeDrunk 走得更远，而差多少量级，就不好说了。

绘图版：

class styleIterator (object):
    """为打印样式不重样，专门建了一个类。"""
    def __init__(self, styles):
        """styles 是打印样式的字符串的元组。"""
        self.index = 0
        self.styles = styles

    def nextStyle (self):
        """ 返回当前 index 指向的 styles 元组中的字符串，
        同时将 index 向后移动一格，如果到底就从头再来。"""
        result = self.styles [self.index]
        #如果到底，就从头再来。
        if self.index == len (self.styles) - 1:
            self.index = 0
        else:
            self.index += 1
        return result


def simDrunk (numTrials, dClass, walkLengths):
    """ 为了绘图，计算不同步数对应的出走平均距离。
    要求：
    numTrails 是正整数；
    dClass 是 Drunk 的某一个子类；
    walkLengths 是各种步数情况的元组。
    返回：
    一个列表，表示与各种步长一一对应的出走平均距离。"""
    meanDistances = []
    for numSteps in walkLengths:
        print ('Starting simulation of', numSteps, 'steps')
        trials = simWalks (numSteps, numTrials, dClass)
        mean = sum (trials)/len (trials)
        meanDistances.append (mean)
    return meanDistances


def simAll1 (drunkKinds, walkLengths, numTrials):
    """ 模拟各种醉鬼的情况，绘图输出在各种步数情况下的平均出走距离。
    相比于 simAll，不是分别打印，而是分别绘图。
    要求：
    drunkKinds 是元组或列表，元素 Drunk 的几个子类。
    walklengths 是元组或列表，走多少步的各种情况。
    numTrials 是正整数，表示尝试多少次，以便算取平均值和最大最小值。
    返回：
    一张图表，各种醉鬼各种步数的平均移动距离.png"""
    styleChoice = styleIterator (('m-', 'r:', 'k-.'))
    #循环样式，分别绘图。
    pylab.figure ('simAll1')
    for dClass in drunkKinds:
        curStyle = styleChoice.nextStyle ()
        print ('Starting simulation of', dClass.__name__)
        #调用为了绘图的 simDrunk，返回的是数组。
        means = simDrunk (numTrials, dClass, walkLengths)
        pylab.plot (walkLengths, means, curStyle,
                   label = dClass.__name__)
    #下面这几句是绘制正常的醉汉步数与距离的规律用的。
    #curStyle = styleChoice.nextStyle ()
    #refs = [math.sqrt (x) for x in walkLengths]
    #pylab.plot (walkLengths, refs, curStyle, label = 'Square root of steps')
    #给这张图整体做装饰。
    pylab.title ('Mean Distance from Origin (' + str (numTrials) + ' trials)')
    pylab.xlabel ('Number of Steps')
    pylab.ylabel ('Distance from Origin')
    pylab.legend (loc = 'best')
    #坐标轴调整为对数标度
    pylab.semilogx ()
    pylab.semilogy ()
    pylab.savefig ("各种醉鬼各种步数的平均移动距离")

各种醉鬼各种步数的平均移动距离，可以看出： - 怕冷的醉鬼跑得快，几乎快一个量级。 - 四方游走与东西游走的出走距离差不多，增长速度基本是步数根号 2。

普通醉汉和追寻阳光的醉汉（EWDrunk）看上去以大致相同的节奏离开原点，但是追寻温暖的醉汉（ColdDrunk）离开原点的速度看上去高出不止一个数量级。这很有趣，因为平均来说，他的移动速度只比其他醉汉快 25%（平均来说，他走 5 步时其他人只走 4 步）。

由此可见，图表有打印不可替代的力量。

从线图中看到了规律，怎么更加深刻地理解 3 种醉汉的行为？

绘制对于某个特定的步数，各个醉汉的最终位置分布。

def getFinalLocs (numSteps, numTrials, dClass):
    """ 模拟某类醉鬼从原点出发多次游走的停止位置。
    要求：
    numSteps，正整数，步数。
    numTrials，正整数，尝试次数。
    dClass，Drunk 的某个子类，醉鬼的特征。
    返回：
    locs，列表，numTrials 次游走的最终位置。"""
    locs = []
    d = dClass ()
    for t in range (numTrials):
        f = Field ()
        f.addDrunk (d, Location (0, 0))
        for s in range (numSteps):
            f.moveDrunk (d)
        locs.append (f.getLoc (d))
    return locs


def plotLocs (drunkKinds, numSteps, numTrials):
    """ 绘制各种醉鬼走相同步数后的各种最终位置图。
    要求：
    drunkKinds 是元组或列表，元素 Drunk 的几个子类。
    numSteps 是正整数，表示步数。
    numTrials 是正整数，表示尝试多少次，以便看到最终位置的分布趋势。
    返回：
    一张图表，各种醉鬼走相同步数后的多次最终位置.png。
    """
    styleChoice = styleIterator (('k+', 'r^', 'mo'))
    #循环各中醉鬼的情况。
    pylab.figure ("plotLocs")
    for dClass in drunkKinds:
        #模拟出这种醉鬼多次尝试的最终位置。
        locs = getFinalLocs (numSteps, numTrials, dClass)
        #将 Locations 的信息拆出来
        xVals, yVals = [], []
        for loc in locs:
            xVals.append (loc.getX ())
            yVals.append (loc.getY ())
        #算取平均位置
        meanX = sum (xVals)/len (xVals)
        meanY = sum (yVals)/len (yVals)
        #绘图并标注
        curStyle = styleChoice.nextStyle ()
        pylab.plot (xVals, yVals, curStyle,
                      label = dClass.__name__ + ' mean loc. = <'
                      + str (meanX) + ', ' + str (meanY) + '>')
    #整体修饰图表
    pylab.title ('Location at End of Walks ('
                + str (numSteps) + ' steps)')
    pylab.xlabel ('Steps East/West of Origin')
    pylab.ylabel ('Steps North/South of Origin')
    pylab.legend (loc = 'lower left')
    pylab.savefig ("各种醉鬼走相同步数后的多次最终位置")


# 描绘最终位置图表，三种醉鬼，走 100 步，尝试 200 次。
plotLocs ((UsualDrunk, ColdDrunk, EWDrunk), 100, 200)

得到

从图 各种醉鬼走相同步数后的多次最终位置 可见： - UsualDrunk 漫无目的四处游走； - EWDrunk 只在 X 轴上移动，200 个点有很多重合了。 - ColdDrunk 更偏向南方。

从平均意义上说，为什么 ColdDrunk 相对于其他两种类型的醉汉，总是试图从原点走得更远？

要搞清这个问题，恐怕不能从多次游走的终点入手，而应该看一下单次游走经过的路径。

# 单次游走经过的路径

def traceWalk (drunkKinds, numSteps):
    """ 绘制各种醉鬼一次漫步的轨迹。
    要求：
    drunkKinds 是元组或列表，元素 Drunk 的几个子类。
    numSteps 是正整数，表示步数。
    返回：
    一张图表。
    """
    styleChoice = styleIterator (('k+', 'r^', 'mo'))
    f = Field ()
    #替换为有 1000 个虫洞的场地，场地内有正负 100 * 正负 200，共 80000 个点。虫洞占比 1/80。
    # f = oddField (1000, 100, 200)
    pylab.figure ("traceWalk")
    for dClass in drunkKinds:
        d = dClass ()
        f.addDrunk (d, Location (0, 0))
        #把每一步的位置存入 locs 列表。
        locs = []
        for s in range (numSteps):
            f.moveDrunk (d)
            locs.append (f.getLoc (d))
        #拆分出 xy 信息。
        xVals, yVals = [], []
        for loc in locs:
            xVals.append (loc.getX ())
            yVals.append (loc.getY ())
        #各种醉鬼分别绘图
        curStyle = styleChoice.nextStyle ()
        pylab.plot (xVals, yVals, curStyle,
                  label = dClass.__name__)
    #整体修饰标注
    pylab.title ('Spots Visited on Walk ('
                + str (numSteps) + ' steps)')
    pylab.xlabel ('Steps East/West of Origin')
    pylab.ylabel ('Steps North/South of Origin')
    pylab.legend (loc = 'best')
    pylab.savefig ("各种醉鬼一次漫步的轨迹")


# 绘制三种醉鬼各走 100 步的轨迹图表。
traceWalk ((UsualDrunk, ColdDrunk, EWDrunk), 100)

由图 “各种醉鬼一次漫步的轨迹” 可见： - UsualDrunk 和 ColdDrunk 经常重复自己走过的路。 - ColdDrunk 很少重复自己走过的路。 - 有倾向性，长远积累起来，走得更远。

从醉汉游走的模型开发过程中，注意体会哪三点？

首先，我们将模拟代码分成了 4 个独立的部分。其中 3 个为类（Location、Field 和 Drunk），对应于问题非正式描述中出现的 3 个抽象数据类型。第 4 部分是一组函数，可以使用这些类进行一些简单的模拟。

一开始，就想把程序分成几个类，和在抽象类基础上的函数，做简单模拟，调试抽象类。

然后，我们为 Drunk 类精心设计了一个层次结构，这样可以观察各种不同类型的有偏随机游走。关于 Location 和 Field 的代码依然保持不变，但修改了模拟代码来遍历 Drunk 的不同子类。在此期间，我们利用了 “类本身也是一个对象” 这一特点，将其作为实参进行传递。

然后丰富类，更有针对性地描述问题。

最后，我们对模拟过程进行了一系列增量修改，但其中没有任何修改涉及表示抽象类型的类。这些修改多数是为了生成图形，这些图形可以使我们对不同类型的游走有更深刻的理解。这是一种典型的开发模拟模型的方法，先使基础的模拟运行起来，然后不断添加新功能。

最后为了更深刻地理解问题，不改变抽象类，添加新功能。

在有虫洞的田地里，醉汉可能走成什么模样？

class oddField (Field):
    """这是一个特别场地，它有虫洞。"""
    def __init__(self, numHoles, xRange, yRange):
        """ 初始化虫洞特别场地。
        要求：
        numHoles 是正整数值，表示场地内虫洞的数量。
        xRange 和 yRange 都是正数值，正负 xy 和起来表示场地的范围。
        建立：
        drunks 字典，继承 Field 类，将 drunk 者映射到他们各自的位置。
        wormholes 字典，将位置 (x, y) 的虫洞映射到新位置上 Location (newX, newY)"""
        Field.__init__(self)
        self.wormholes = {}
        for w in range (numHoles):
            #在范围内随机找一个点。
            x = random.randint (-xRange, xRange)
            y = random.randint (-yRange, yRange)
            #在范围内随机找另一个点。
            newX = random.randint (-xRange, xRange)
            newY = random.randint (-yRange, yRange)
            #把另一个点的数据集成入一个 Location 抽象类。
            newLoc = Location (newX, newY)
            #注意字典的键是 (x, y) 元组，键值是 Location 类。
            self.wormholes [(x, y)] = newLoc

    def moveDrunk (self, drunk):
        """请 drunk 者移动一步，如果他踩到了虫洞，那就他的位置更新为虫洞彼岸的位置。"""
        Field.moveDrunk (self, drunk)
        x = self.drunks [drunk].getX ()
        y = self.drunks [drunk].getY ()
        if (x, y) in self.wormholes:
            self.drunks [drunk] = self.wormholes [(x, y)]
           
# 在有虫洞的田地里，绘制三种醉鬼各走 500 步的轨迹图表。
traceWalk ((UsualDrunk, ColdDrunk, EWDrunk), 500)

由图可见： - ColdDrunk 踩到虫洞的几率更大。 - 虫洞空间虽然受限，但是醉汉游走的空间不受限制。

干嘛要在醉汉游走的田地里引入虫洞玩以下，教学要点是什么？

我们的代码是高度结构化的，所以很容易适应建模情形的重大改变。就像可以在不修改 Field 的情况下添加不同类型的醉汉一样，我们也可以在不对 Drunk 及其任何子类进行修改的情况下，添加一种新的 Field 类型。（如果有足够的先见之明，在 trackWalk 中使用一个形参表示田地，甚至都不用修改 traceWalk 中的第 2 行代码。）

• 因为各个结构彼此独立，可以在后续修改中避免冲突。

在简单随机游走问题甚至有偏随机游走问题中，通过分析方法推导各种不同类型醉汉的预期行为还是比较可行的，但如果引入虫洞再做这些分析就很困难了。相比之下，修改模型以模拟新的情形则非常容易。与分析性模型相比，适应性强是模拟模型引以为傲的一大优点。

• 手工分析推演虽然可行，但是模拟模型能力范围更广。

以上，2018-05-02 16:50:01 记完。