c语言中dfs用pos做参数,使用DFS解决8-Puzzle
meriton - on..
6
好的,所以你的程序花費的時間比預期的要長.首先,我們要確定它是否陷入無限循環,或者只是緩慢.為此,讓程序通過在主循環中添加以下內容來打印其進度:
int statesVisited = 0;
while (OPEN.empty() == false && STATE == false) {
statesVisited++;
System.out.println(statesVisited);
然后我們看到該程序每秒訪問了幾千個狀態.由于我們的處理器每秒執行數十億條指令,這意味著處理狀態需要大約一百萬條cpu指令.它不應該那么高,不是嗎？那可能是什么導致了這個？
一般來說,我們現在使用分析器來測量代碼中所占用的代碼的哪一部分,但由于程序太短,我們可以先嘗試猜測.我的第一個猜測是打印我們訪問的每個州都可能非常昂貴.為了驗證這一點,我們只打印每1000個狀態:
while (OPEN.empty() == false && STATE == false) {
statesVisited++;
if (statesVisited % 1000 == 0) {
System.out.println(statesVisited);
}
我們改變了位置,我們注意到前5000個州在第二個國家被訪問,所以印刷確實很重要.我們還注意到一些奇怪的事情:雖然前一個5000狀態在一秒鐘內被訪問,但由于某種原因,程序似乎變得越來越慢.在訪問的20000個州,大約需要一秒鐘才能訪問1000個州,并且情況會持續惡化.這是意料之外的,因為處理狀態不應該變得越來越昂貴.所以我們知道循環中的一些操作變得越來越昂貴.讓我們回顧一下我們的代碼,以確定它可能是哪個操作.
無論集合的大小如何,推送和彈出都需要恒定的時間.但是你也使用Stack.search和LinkedList.contains.記錄這兩個操作都要求迭代整個堆棧或列表.那么,讓我們輸出這些集合的大小:
if (statesVisited % 1000 == 0) {
System.out.println(statesVisited);
System.out.println(OPEN.size());
System.out.println(CLOSED.size());
System.out.println();
}
等了一會兒后,我們看到:
40000
25947
39999
所以OPEN包含25000個元素,并且CLOSED接近40000個.這就解釋了為什么處理狀態會越來越慢.因此,我們希望選擇具有更高效的包含操作的數據結構,例如a java.util.HashSet或java.util.LinkedHashSet(它是散列集和鏈表之間的混合,允許我們按照添加的順序檢索元素).這樣做,我們得到:
public static LinkedHashSet OPEN = new LinkedHashSet();
public static HashSet CLOSED = new HashSet();
public static boolean STATE = false;
public static void main(String args[]) {
int statesVisited = 0;
String start = "123804765";
String goal = "281043765";
String X = "";
String temp = "";
OPEN.add(start);
while (OPEN.isEmpty() == false && STATE == false) {
X = OPEN.iterator().next();
OPEN.remove(X);
int pos = X.indexOf('0'); // get position of ZERO or EMPTY SPACE
if (X.equals(goal)) {
System.out.println("SUCCESS");
STATE = true;
} else {
// generate children
CLOSED.add(X);
temp = up(X, pos);
if (!(temp.equals("-1")))
OPEN.add(temp);
temp = left(X, pos);
if (!(temp.equals("-1")))
OPEN.add(temp);
temp = down(X, pos);
if (!(temp.equals("-1")))
OPEN.add(temp);
temp = right(X, pos);
if (!(temp.equals("-1")))
OPEN.add(temp);
}
}
}
/*
* MOVEMENT UP
*/
public static String up(String s, int p) {
String str = s;
if (!(p < 3)) {
char a = str.charAt(p - 3);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p - 3)) + '0' + newS.substring(p - 2);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT DOWN
*/
public static String down(String s, int p) {
String str = s;
if (!(p > 5)) {
char a = str.charAt(p + 3);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p + 3)) + '0' + newS.substring(p + 4);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT LEFT
*/
public static String left(String s, int p) {
String str = s;
if (p != 0 && p != 3 && p != 7) {
char a = str.charAt(p - 1);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p - 1)) + '0' + newS.substring(p);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT RIGHT
*/
public static String right(String s, int p) {
String str = s;
if (p != 2 && p != 5 && p != 8) {
char a = str.charAt(p + 1);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p + 1)) + '0' + newS.substring(p + 2);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
public static void print(String s) {
System.out.println(s.substring(0, 3));
System.out.println(s.substring(3, 6));
System.out.println(s.substring(6, 9));
System.out.println();
}
幾乎立即打印"SUCCESS".
總結
以上是生活随笔為你收集整理的c语言中dfs用pos做参数,使用DFS解决8-Puzzle的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： c语言调用hzk16,C语言使用HZK1
- 下一篇： range在c语言中的意思,“range