深度優(yōu)先搜索(depth-first search，簡(jiǎn)稱dfs)就是遞歸地進(jìn)行一系列操作，直到找到想要的結(jié)果或者搜到頭了（無(wú)路可走）。
我對(duì)深度優(yōu)先搜索的總結(jié)就是：
（1）不見(jiàn)南墻不回頭
（2）找到以后往回走
深度優(yōu)先搜索其實(shí)和我們大多數(shù)人小時(shí)候走迷宮時(shí)選擇的策略非常類似。
深度優(yōu)先搜索有一個(gè)很簡(jiǎn)單的例子：求n!。
int f(int n) {
if(n == 0 || n == 1) return 1;
return f(n-1) * n;
}
我們以現(xiàn)在ACM競(jìng)賽中一道簡(jiǎn)單的競(jìng)賽題 --
素?cái)?shù)環(huán) 為例，來(lái)講解深度優(yōu)先搜索。
點(diǎn)此進(jìn)入題目描述
這道題目的意思是，找到所有的素?cái)?shù)環(huán)輸出。
我們可以寫(xiě)下對(duì)應(yīng)的偽代碼：
function dfs(深度) {
if(深度 == 1) {
第1個(gè)點(diǎn)確定為1;
第1個(gè)點(diǎn)標(biāo)記訪問(wèn)過(guò)了;
dfs(深度+1);
撤銷第1個(gè)點(diǎn)的標(biāo)記;
}
else {
for(i = 1 to n) {
if(i加上第（深度-1）個(gè)點(diǎn)的值是素?cái)?shù) and i沒(méi)有被訪問(wèn)過(guò)) {
第（深度）個(gè)點(diǎn)確定為i;
第i個(gè)點(diǎn)標(biāo)記訪問(wèn)過(guò)了;
dfs(深度+1);
撤銷第i個(gè)點(diǎn)的標(biāo)記;
}
}
}
if(深度 > n) {
if(第（深度-1）個(gè)點(diǎn)的值+1是素?cái)?shù)) {
輸出這串素?cái)?shù)環(huán);
}
return;
}
return;
}
簡(jiǎn)單了解了深度優(yōu)先搜索，并且差不多看懂了這個(gè)偽代碼，我們就可以用代碼實(shí)現(xiàn)一下了。下面是完整的Java代碼：
import java.util.Scanner;
public class Main {
public static boolean isprime(int n) {
if(n ==2 || n == 3 || n == 5 || n == 7 || n == 11 || n == 13 || n == 17 || n == 19 ||
n == 23 || n == 29 || n == 31 || n == 37 || n == 41)
return true;
return false;
}
private static boolean[] vis = new boolean[22];
private static int[] ans = new int[22];
private static Scanner in;
public static void dfs(int dep,int n) {
for(int i=1;i<=n;i++) {
if(vis[i] == false && isprime(ans[dep-1] + i)) {
vis[i] = true;
ans[dep] = i;
if(dep == n && isprime(1+i)) {
System.out.print(ans[1]);
for(int i1=2;i1<=n;i1++) System.out.print(" " + ans[i1]);
System.out.println("");
vis[i] = false;
return;
} else if(dep == n) {
vis[i] = false;
return;
}
dfs(dep+1, n);
vis[i] = false;
}
}
return;
}
public static void main(String[] args) {
in = new Scanner(System.in);
int cnt = 0;
while(in.hasNext()) {
int n = in.nextInt();
for(int i=1;i<=n;i++) vis[i] = false;
cnt ++;
System.out.println("Case " + cnt + ":");
vis[1] = true;
ans[1] = 1;
dfs(2, n);
System.out.println("");
}
}
}
遞歸地一種很好玩的現(xiàn)象：德羅斯特效應(yīng)
posted on 2015-03-07 20:47
marchalex 閱讀(193)
評(píng)論(0) 編輯 收藏 所屬分類:
java小程序