广搜TDD

实验描述

用go语言完成深搜Bfs的“走迷宫”算法。从迷宫的[1][1]点，走到迷宫右下角（迷宫大小可变，因此数组要用切片数组）.

然后自己拟造简单数据，完成test和benchmark（测时间）

先写框架，用最少代码把测试框架跑起来

在bfs_test.go中

package iteration import "testing" func TestBfs(t *testing.T){ var m [][]int; ans:=Bfs(m); excepted:=-1; if (ans!=excepted){ t.Errorf("we want %d,but %d",excepted,ans); } }

在bfs.go中

package iteration func Bfs(m [][]int) int{ return 5; }

此时执行

go test XXX

结果：

--- FAIL: TestBfs (0.00s) bfs_test.go:12: we want -1,but 5 FAIL FAIL bo 0.500s FAIL C:\Users\ASUS>

编译正确，符合预期

框架已经打出来了，接下来是Bfs的代码，还有在test函数中地图的构建

代码的补全

知识预备：切片数组 （大佬请跳过）

go语言里数组大小也在函数传参的考虑范围里。 例如：

func Arratfunction(a [][]int){ } a:=[3][3]int; ArrayFunction(a);

就无法通过编译。

所以这里必须使用切片数组（相当与c语言里数组指针，动态分配数组） 切片数组的长度可动态分配，无论长度如何切片都可以传参。

这样迷宫大小就不是考虑问题了（可以用len()函数获得尺寸）

二维切片数组的分配例子：

var m [][]int=make([][]int,101); for i:=0;i<101;i++ { m[i]=make([]int,51); }

一个101*51的二维切片数组。

我不喜欢0，所以都分配多一点，呜呜呜呜

首先补全Bfs函数

深搜在此不做解释

在bfs.go中：

package bfs import "fmt" type point struct { x int; y int; } func Bfs(m [][]int) int { var q [10050]point; h:=0;t:=1; q[1].x=1;q[1].y=1; var height int =len(m); var width int=len(m[0]); var vis [][]bool; vis=make([][]bool,height); for i:=0;i<height;i++ { vis[i]=make([]bool,width); } var step [][]int; step=make([][]int,height); for i:=0;i<height;i++{ step[i]=make([]int,width); } for i:=0;i<height;i++{ for j:=0;j<width;j++{ vis[i][j]=false; step[i][j]=-1; } } vis[1][1]=true; step[1][1]=0; height=height-1; width=width-1; var dir [5][3]int; dir[1][1]=1;dir[1][2]=0; dir[2][1]=0;dir[2][2]=1; dir[3][1]=-1;dir[3][2]=0; dir[4][1]=0;dir[4][1]=-1; for ;h!=t; { h++; now:=q[h]; x:=now.x; y:=now.y; for i:=1;i<4;i++ { nx:=x+dir[i][1]; ny:=y+dir[i][2]; if nx<=0 || nx>height || ny<=0||ny>width { continue; } if vis[nx][ny]==false && m[nx][ny]==1 { vis[nx][ny]=true; step[nx][ny]=step[x][y]+1; t++; q[t].x=nx; q[t].y=ny; } } } fmt.Printf(""); /* ans debug for i:=1;i<=height;i++{ for j:=1;j<=width;j++{ fmt.Printf("%d ",step[i][j]); } fmt.Printf("\n"); } */ return step[height][width]; }

然后补全bfs_test.go

主要就是拟造数据

package bfs import "testing" func TestBfs(t *testing.T) { var m [][]int=make([][]int,101); for i:=0;i<101;i++ { m[i]=make([]int,51); } //先建立无障碍迷宫 for i:=0;i<101;i++{ for j:=0;j<51;j++{ m[i][j]=1; } } // 在迷宫中加入两堵墙，让计算机绕路 for i:=1;i<=99;i++ { m[i][3]=0; } for i:=2;i<=100;i++{ m[i][5]=0; } excepted:=346;//脑算答案 ans:=Bfs(m); if ans!=excepted { t.Errorf("we want %d , but we get %d",excepted,ans); } }

这里画了一个大致是这样的迷宫：

绕个弯子就走到了答案是346（具体数据见代码）

go test测试结果：

ok hw2 0.451s

说明答案正确

如果更改excepted为-1呢？（故意出错） 结果：

bfs_test.go:30: we want -1 , but we get 346

说明测试是可靠的。

基准测试 （貌似就是测时间）

在bfs_test.go中加入函数 BenchmarkBfs(b *testing.B)

func BenchmarkBfs( b* testing.B){ var m [][]int=make([][]int,101); for i:=0;i<101;i++ { m[i]=make([]int,51); } //先建立无障碍迷宫 for i:=0;i<101;i++{ for j:=0;j<51;j++{ m[i][j]=1; } } // 在迷宫中加入两堵墙，让计算机绕路 for i:=1;i<=99;i++ { m[i][3]=0; } for i:=2;i<=100;i++{ m[i][5]=0; } for i:=0;i<b.N;i++{ Bfs(m); } }

然后运行

go test XXX -bench="."

运行结果：

goos: windows goarch: amd64 pkg: hw2 BenchmarkBfs-16 20274 60140 ns/op PASS ok hw2 2.294s

表明运行了20274次，每次60140纳秒

（新电脑，就是快）