2010年3月11日木曜日

深さ優先探索,動的計画法,メモ化再帰

ITmediaにて,chokudai(高橋直大)さん連載の「最強最速アルゴリズマー養成講座」の最新記事が公開されました.

最強最速アルゴリズマー養成講座:アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ
http://www.itmedia.co.jp/enterprise/articles/1003/06/news002.html

というわけで,格子の問題を,解説を元にサクッと組んでみました.


public class Main{
private int w, h;
private int[][] memo;

private int recursive1(int[][] grid, int x, int y){
if(y==0&&x==w-1){
return 1;
}
else if(y<0||x>=w||grid[y][x]==1){
return 0;
}
else {
return recursive1(grid, x+1, y)+recursive1(grid, x, y-1);
}
}

// 単純な深さ優先探索(DFS) O(2^(h+m))
private int count1(int[][] grid){
w=grid[0].length;
h=grid.length;
return recursive1(grid,0,h-1);
}

// 動的計画法(DP) O(h*w)
private int count2(int[][] grid){
w=grid[0].length;
h=grid.length;
int[] a=new int[w];

for(int i=0;i<w&&grid[h-1][i]==0;i++){
a[i]=1;
}

for(int j=h-2;j>=0;j--){
for(int i=1;i<w;i++){
if(grid[j][i]==1)
a[i]=0;
else
a[i]+=a[i-1];
}
}
return a[w-1];
}

private int recursive3(int[][] grid, int x, int y){
if(y==0&&x==w-1){
return 1;
}
else if(y<0||x>=w||grid[y][x]==1){
return 0;
}
else {
if(memo[y][x]!=0)
return memo[y][x];
else
return memo[y][x]=recursive3(grid, x+1, y)+recursive3(grid, x, y-1);
}
}

// メモ化再帰
private int count3(int[][] grid){
w=grid[0].length;
h=grid.length;
memo=new int[h][w];
return recursive3(grid,0,h-1);
}

public static void main(String[] args){
// 0:通過可能
// 1:通過不可能
int[][] grid=new int[][]
{
{0,0,0,0,0,0},
{0,1,0,0,0,0},
{0,0,0,0,1,0},
{0,0,1,0,0,0},
{0,0,0,0,0,0},
};
System.out.println("1:"+new Main().count1(grid));
System.out.println("2:"+new Main().count2(grid));
System.out.println("3:"+new Main().count3(grid));
}
}


深さ優先探索,動的計画法,メモ化再帰の3つです.意外なほど簡単に組めたので驚き.

「最強最速アルゴリズマー養成講座」の記事一覧は下記から.

「最強最速アルゴリズマー養成講座」最新記事一覧 - ITmedia Keywords
http://www.itmedia.co.jp/keywords/algorithmer.html

0 件のコメント: