迷茫童鞋的阅读指南
该项目的详细描述和算法的具体说明
请参见前一篇
本人也给出了
俗话说得好:凡事说起来容易，做起来难。 博主没有谨慎思考打开IDE就是一顿乱敲，然后就是不停地修复各种BUG。下面谈谈该算法的实现以及遇到的问题和解决办法：
Step1:
国际惯例导入提供的函数：from percolation_provided import *
再敲定函数名：percolation_wave(input_grid)。名字取好了就可以开始干活了，参数先暂定一个，即input_grid
咱们用提供的函数grid(size,fill=0)产生一个flow_grid网格，因为咱们不能修改输入的网格数据，用这个来记录水波流过的位置。
flow_grid = grid(len(input_grid), - 1 ) # 用来表示流，默认填充为-1
Problem One:
接着需要根据输入的input_grid网格生成一个初始状态（也就是第一行）的next_wave，我采用了列表解析的方法。正确写法如下：
next_wave = [(0,m) for m,flow in enumerate(input_grid[0]) if flow == 0]
但是，粗心大意之下，我写成了这个样子，结果就杯具了...
next_wave = [(m,0) for m,flow in enumerate(input_grid[0]) if flow == 0] #这是错误的
然后需要写主循环了，目的是让generate_nextwave函数不辞辛苦地把水波一遍遍地往可以扩散的位置上流。然后我在写while循环条件时又犯了一个错误：
while j < len(input_grid) and next_wave != []:
首先水波不是顺势而下的，会往所有可以流的位置上跑，而我在循环体里还设置了每执行一次generate_nextwave函数，就j+=1。第二，直接写next_wave就可以表示其不为空。正确做法如下：
因为要用到generate_nextwave函数，所以我们要确定它需要用到的参数是：
input_grid：如果[i][j]位置阻塞，则input_grid[i][j]值为1。
flow_grid：如果[i][j]位置没有被水波访问到，则flow_grid[i][j]值为-1；如果第k个水波能够到达该位置，则它包含了值k。
last_wave：(行，列)对的列表，表示在上一个水波中的网格位置。
函数名敲定为generate_nextwave(input_grid,flow_grid,last_wave)。
跳转到generate_nextwave函数，考虑该函数最后返回的类型是一个包含下一组水波的坐标列表。所以定义一个数组。
然后来对传进来的last_wave的数组迭代地进行处理：
1.先考虑，对已存在原数组中的元素进行标记，wave用来表示第X波水波
for (i,j) in last_wave: wave = flow_grid[i][j] + 1 print (i,j),flow_grid[i][j],wave # 测试用
2.判断单元[i][j]的相邻单元是否开放，它的四个相邻单元是[i-1][j]，[i+1][j]，[i][j-1]，[i][j+1]。
这里要注意的是首先需要对单元[i][j]它的四个相邻单元是否存在进行判断，我就犯了这个错误....
因为每次迭代都需要与网格的长度做比较，为此我们需要定义一个变量：
其次，判断语句不要用if...elif....否则就变成每次只要某个条件为真，就跳出循环了，而这样，水波算法就变成直楞子水管算法
...正确代码如下：
# Down if i + 1 < Len: if input_grid[i + 1 ][j] == 0 and flow_grid[i + 1 ][j] ==- 1 : flow_grid[i + 1 ][j] = wave next_wave.append((i + 1 ,j)) # Up if i - 1 >= 0: if input_grid[i - 1 ][j] == 0 and flow_grid[i - 1 ][j] ==- 1 : flow_grid[i - 1 ][j] = wave next_wave.append((i - 1 ,j)) # Left if j - 1 >= 0 : if input_grid[i][j - 1 ] == 0 and flow_grid[i][j - 1 ] ==- 1 : flow_grid[i][j - 1 ] = wave next_wave.append((i,j - 1 )) # Right if j + 1 < Len: if input_grid[i][j + 1 ] == 0 and flow_grid[i][j + 1 ] ==- 1 : flow_grid[i][j + 1 ] = wave next_wave.append((i,j + 1 ))
回到percolation_wave(input_grid)，我们需要对网格最后是否为渗透进行判断。判断渗透的依据是flow_grid的最后一行有某个元素的值不为-1。
for element in flow_grid[ - 1 ]: if element !=- 1 : percolates = True
1.为percolation_wave函数添加可视化参数trace=True，非常便于调试。在while循环内添加相应代码。可视化函数是已经提供的visualize函数。rate(2)表示显示速率为每次2行
if trace: visualize(flow_grid, input_grid) rate( 2 )
2.尽快结束算法。由于水波算法会遍历完网格中所有可经过的路径，即使已经到达了网格最后一行。因此，我们希望一旦判断为可渗透就能够尽快算法。为此需要添加一个参数short=True ，也就是在循环体内，每循环一次就进行一次渗透判断，代码如下：
if short: if [e for e in flow_grid[ - 1 ] if e >- 1 ]: return flow_grid, True
关于调试方法
1.使用print语句
print (i,j),flow_grid[i][j],wave # 测试用
查看输出和预计的是否一致：
(0, 0) -1 0
(0, 1) 0 1
(0, 3) -1 0
(0, 4) 0 1
(0, 5) 1 2
........
2.使用Vpython，这个绝对是个好方法，你可以直观地发现问题所在。
3.使用doctest
最后，本人完整的代码如下：
percolation_wave # -*- coding: utf-8 -*- """ Created on Sun Aug 07 17:29:32 2011@author: Nupta """ from percolation_provided import * from visual import rate def percolation_wave(input_grid, trace = True, short = False): """ Percolation algorithm by wave. Uses input_grid to determine where flow is allowed, trace to determine whether or not to visualize it graphically, and short to determine whether or not to exit early. Essentially, if your algorithm exits early, the code inside the 'if short' condition is what your code might look like. """ flow_grid = grid(len(input_grid), - 1 ) # 用来表示流，默认填充为-1 next_wave = [(0,m) for m,flow in enumerate(input_grid[0]) if flow == 0] # 表示在第一行水波中的网格位置 percolates = False while next_wave: if trace: visualize(flow_grid, input_grid) rate( 2 ) if short: if [e for e in flow_grid[ - 1 ] if e >- 1 ]: return flow_grid, True next_wave = generate_nextwave(input_grid,flow_grid,next_wave) for element in flow_grid[ - 1 ]: if element !=- 1 : percolates = True return flow_grid,percolates def generate_nextwave(input_grid,flow_grid,last_wave): next_wave = [] Len = len(input_grid) for (i,j) in last_wave: wave = flow_grid[i][j] + 1 print (i,j),flow_grid[i][j],wave # 测试用 # Down if i + 1 < Len: if input_grid[i + 1 ][j] == 0 and flow_grid[i + 1 ][j] ==- 1 : flow_grid[i + 1 ][j] = wave next_wave.append((i + 1 ,j)) # Up if i - 1 >= 0: if input_grid[i - 1 ][j] == 0 and flow_grid[i - 1 ][j] ==- 1 : flow_grid[i - 1 ][j] = wave next_wave.append((i - 1 ,j)) # Left if j - 1 >= 0 : if input_grid[i][j - 1 ] == 0 and flow_grid[i][j - 1 ] ==- 1 : flow_grid[i][j - 1 ] = wave next_wave.append((i,j - 1 )) # Right if j + 1 < Len: if input_grid[i][j + 1 ] == 0 and flow_grid[i][j + 1 ] ==- 1 : flow_grid[i][j + 1 ] = wave next_wave.append((i,j + 1 )) return next_wave
当然，你可能更希望看到Pudure提供的参考答案：
Pudure Code # ! /usr/bin/env python from visual import rate from percolation_provided import * def percolation_wave(input_grid, trace = True, short = False): """ Percolation algorithm by wave. Uses input_grid to determine where flow is allowed, trace to determine whether or not to visualize it graphically, and short to determine whether or not to exit early. Essentially, if your algorithm exits early, the code inside the 'if short' condition is what your code might look like. """ flow_grid = grid(len(input_grid), - 1 ) next_wave = [] # Populate the inital wave from the top row for k in range(len(input_grid[0])): if input_grid[0][k] == 0: flow_grid[0][k] = 1 next_wave.append((0,k)) while next_wave: if trace: visualize(flow_grid, input_grid) rate( 2 ) if short: row = len(flow_grid) - 1 for k in range(len(flow_grid[0])): if flow_grid[row][k] != - 1 : return flow_grid, True next_wave = gen_next_wave(input_grid, flow_grid, next_wave) # Check if we made it to the bottom row = len(flow_grid) - 1 percolates = False for k in range(len(flow_grid[0])): if flow_grid[row][k] != - 1 : percolates = True return flow_grid, percolates def gen_next_wave(input_grid, flow_grid, current): next = [] for row, col in current: wave = flow_grid[row][col] + 1 # Look down if row + 1 < len(input_grid): if input_grid[row + 1 ][col] == 0 and flow_grid[row + 1 ][col] == - 1 : flow_grid[row + 1 ][col] = wave next.append((row + 1 , col)) # Look right if col + 1 < len(input_grid[0]): if input_grid[row][col + 1 ] == 0 and flow_grid[row][col + 1 ] == - 1 : flow_grid[row][col + 1 ] = wave next.append((row, col + 1 )) # Look left if col - 1 >= 0: if input_grid[row][col - 1 ] == 0 and flow_grid[row][col - 1 ] == - 1 : flow_grid[row][col - 1 ] = wave next.append((row, col - 1 )) # Look up if row - 1 >= 0: if input_grid[row - 1 ][col] == 0 and flow_grid[row - 1 ][col] == - 1 : flow_grid[row - 1 ][col] = wave next.append((row - 1 , col)) return next
预告提示：
下一篇将介绍网格size的定值测试，实验采用水波探测算法在不同开放概率p下计算发生渗透的概率q是多少