laporan ai modul 3-if b 2014-14102055-deprilana ego prakasa
TRANSCRIPT
Sekolah Tinggi Teknologi Telematika Telkom
Laporan Praktikum Kecerdasan Buatan
Modul 3 – Implementasi DFS dan BFS pada
Permainan Labirin
Dosen Pengampu: Muhammad Zidny Naf’an,S.Kom., M.Kom.
Nama Mahasiswa : Deprilana Ego Prakasa
NIM : 14102055
Kelas : S1 IF B 2014
Jawaban Latihan Soal
1. Berdasarkan pohon pelacakan di atas, hasil penelusuran metode DFS adalah : (1,1), (1,2), (2,1), (3,1), (3,2), (3,3), (3,4), (4,3)
2. Berdasarkan pohon pelacakan di atas, hasil penelusuran metode BFS adalah :
(1,1), (1,2), (2,1), (3,1), (3,2), (4,1), (3,3), (3,4), (4,3) 3. Jalankan program yang telah dibuat, hasilnya :
Node.java package AIDFSBFS;
import java.util.ArrayList; import java.util.List; public class Node {
int row; int col;
boolean wasVisited; String label; List<Node> adjNode;
Node(int row, int col) { this.row = row; this.col = col; this.label = "("+Integer.toString(row)+","+Integer.toString(col)+")"; this.wasVisited = false; adjNode = new ArrayList<Node>();
} }
MazeSolver.java package AIDFSBFS;
import java.util.ArrayList; import java.util.List; import java.util.LinkedList; import java.util.Queue; import java.util.Stack;
public class MazeSolver {
private int myMaze[][]={{1,1,1,1,1}, {1,0,0,1,0}, {1,0,1,1,1}, {1,0,0,0,0}, {1,0,1,0,1}};
List<Node> nodes;
String moveOrder; private final int MAX_ROWS=5, MAX_COLS=5; private int newRow, newCol;
Stack<Node> stackNodes; Queue<Node> queueNodes; List<Node> listVisitedNodes;
Node startNode; Node goalNode;
public MazeSolver(String moveOrder)
{
super(); nodes = new ArrayList<Node>(); stackNodes = new Stack<Node>(); queueNodes = new LinkedList<Node>(); listVisitedNodes = new ArrayList<Node>(); this.moveOrder = moveOrder; generateNode(); generateAdjacentNode();
}
private boolean isPossibleMove(int row, int col, char direction) {
boolean possible = false;
switch(direction) {
case 'N': if(row-1>=0 && myMaze[row-1][col] == 0)
possible = true; newRow = row-1; newCol = col;
break; case 'S':
if(row+1<MAX_ROWS && myMaze[row+1][col] == 0) possible = true; newRow = row+1; newCol = col;
break; case 'E':
if(col+1<MAX_COLS && myMaze[row][col+1] == 0) possible = true; newRow = row; newCol = col+1;
break; case 'W':
if(col-1>=0 && myMaze[row][col-1] == 0) possible = true; newRow = row; newCol = col-1;
break; } return possible;
}
private void generateNode() {
for(int i=0; i<MAX_ROWS; i++) {
for(int j=0; j<MAX_COLS; j++)
{
if(myMaze[i][j] == 0) {
Node node = new Node(i, j); nodes.add(node);
} }
} }
private void generateAdjacentNode() {
for(Node node: nodes) {
int row = node.row; int col = node.col;
for(int i=0; i<4; i++) {
char direction = moveOrder.charAt(i); if(isPossibleMove(row, col, direction)) {
Node tmpNode = new Node(newRow, newCol); Node adjNode = nodes.get(getIndex(tmpNode)); node.adjNode.add(adjNode);
} }
} }
private int getIndex(Node tmpNode) {
for(int i=0; i<nodes.size(); i++) {
Node node = nodes.get(i); if(node.row == tmpNode.row && node.col ==
tmpNode.col) return i; } return -1;
}
private void clearVisited() {
for(int i=0; i<nodes.size(); i++) {
nodes.get(i).wasVisited = false; }
}
private void displayNode()
{
for(Node node: listVisitedNodes) {
System.out.println(node.label); }
}
private Node getUnvisitedAdjacentNode(Node currentNode) {
Node adjNode = null;
for(int i=0; i<currentNode.adjNode.size(); i++) {
if(currentNode.adjNode.get(i).wasVisited == false) return currentNode.adjNode.get(i);
} return adjNode;
}
private boolean solveWithDFS(Node startNode, Node goalNode) {
listVisitedNodes.clear();
Node currentNode = nodes.get(getIndex(startNode));
nodes.get(getIndex(startNode)).wasVisited = true;
stackNodes.push(currentNode);
listVisitedNodes.add(currentNode);
while(!stackNodes.isEmpty()) {
Node tmpNode = stackNodes.peek();
currentNode = getUnvisitedAdjacentNode(tmpNode);
if(currentNode != null) {
nodes.get(getIndex(currentNode)).wasVisited = true; listVisitedNodes.add(currentNode); if(currentNode.label.contentEquals(goalNode.label)) {
clearVisited(); return true;
}
stackNodes.push(currentNode); } else {
stackNodes.pop();
}
}
clearVisited(); return false;
}
private boolean solveWithBFS(Node startNode, Node goalNode) {
listVisitedNodes.clear();
Node currentNode = nodes.get(getIndex(startNode));
nodes.get(getIndex(startNode)).wasVisited = true;
queueNodes.add(currentNode);
listVisitedNodes.add(currentNode);
while(!queueNodes.isEmpty()) {
Node tmpNode = queueNodes.peek();
currentNode = getUnvisitedAdjacentNode(tmpNode);
if(currentNode != null) {
nodes.get(getIndex(currentNode)).wasVisited = true;
listVisitedNodes.add(currentNode);
if(currentNode.label.contentEquals(goalNode.label)) {
clearVisited(); return true;
}
queueNodes.add(currentNode);
} else { queueNodes.remove();
} }
clearVisited(); return false;
}
public static void main(String[] args) { // TODO code application logic here
MazeSolver ms = new MazeSolver("NESW");
ms.startNode = new Node(1,1); ms.goalNode = new Node(4,3);
for(Node node: ms.nodes) {
System.out.print(node.label+":\t"); for(Node nodeAdj: node.adjNode) {
System.out.print(nodeAdj.label+" "); } System.out.println();
}
System.out.println("Solve with DFS");
if(ms.solveWithDFS(ms.startNode, ms.goalNode)) {
ms.displayNode(); System.out.println("Solving with
"+ms.listVisitedNodes.size()+" visiting node"); } else {
System.out.println("Goal State didn\'t find"); }
System.out.println("\n\nSolve with BFS : "); if(ms.solveWithBFS(ms.startNode, ms.goalNode)) {
ms.displayNode(); System.out.println("Solving with
"+ms.listVisitedNodes.size()+" visiting node"); } else {
System.out.println("Goal State didn\'t find"); }
}
}
Screenshot hasil :
4. Dengan menggunakan DFS dan BFS coba ganti urutan operator menjadi NORTH-EAST-SOUTH-WEST. Bagaimana hasilnya ?
Untuk selanjutnya menggunakan labirin berikut :
5. Deklarasi array 2-dimensi untuk labirin diatas :
6. Pohon pelacakan labirin di atas ?
(0,2)
(1,2)
(1,1) (1,3)
(1,0) (2,1) (2,3)
(0,0) (3,1) (3,3)
(4,1) (3,2) (3,4)
(4,4)
Koding untuk nomor 7 dan 8 :
Node.java package AIDFSBFS;
import java.util.ArrayList; import java.util.List; public class Node {
int row; int col; boolean wasVisited; String label; List<Node> adjNode;
Node(int row, int col) { this.row = row; this.col = col; this.label = "("+Integer.toString(row)+","+Integer.toString(col)+")"; this.wasVisited = false; adjNode = new ArrayList<Node>();
} }
MazeSolver.java package AIDFSBFS;
import java.util.ArrayList; import java.util.List; import java.util.LinkedList; import java.util.Queue; import java.util.Stack;
public class MazeSolver {
private int myMaze[][]={{0,1,0,1,1}, {0,0,0,0,1}, {1,0,1,0,1}, {1,0,0,0,0}, {1,0,1,1,0}};
List<Node> nodes;
String moveOrder; private final int MAX_ROWS=5, MAX_COLS=5; private int newRow, newCol;
Stack<Node> stackNodes; Queue<Node> queueNodes; List<Node> listVisitedNodes;
Node startNode; Node goalNode;
public MazeSolver(String moveOrder) {
super(); nodes = new ArrayList<Node>(); stackNodes = new Stack<Node>(); queueNodes = new LinkedList<Node>(); listVisitedNodes = new ArrayList<Node>(); this.moveOrder = moveOrder; generateNode(); generateAdjacentNode();
}
private boolean isPossibleMove(int row, int col, char direction) {
boolean possible = false;
switch(direction) {
case 'N': if(row-1>=0 && myMaze[row-1][col] == 0)
possible = true; newRow = row-1; newCol = col;
break; case 'S':
if(row+1<MAX_ROWS && myMaze[row+1][col] == 0) possible = true; newRow = row+1; newCol = col;
break; case 'E':
if(col+1<MAX_COLS && myMaze[row][col+1] == 0) possible = true; newRow = row; newCol = col+1;
break;
case 'W':
if(col-1>=0 && myMaze[row][col-1] == 0) possible = true; newRow = row; newCol = col-1;
break; } return possible;
}
private void generateNode() {
for(int i=0; i<MAX_ROWS; i++) {
for(int j=0; j<MAX_COLS; j++) {
if(myMaze[i][j] == 0) {
Node node = new Node(i, j); nodes.add(node);
} }
} }
private void generateAdjacentNode() {
for(Node node: nodes) {
int row = node.row; int col = node.col;
for(int i=0; i<4; i++) {
char direction = moveOrder.charAt(i); if(isPossibleMove(row, col, direction)) {
Node tmpNode = new Node(newRow, newCol); Node adjNode = nodes.get(getIndex(tmpNode)); node.adjNode.add(adjNode);
} }
} }
private int getIndex(Node tmpNode) {
for(int i=0; i<nodes.size(); i++) {
Node node = nodes.get(i);
if(node.row == tmpNode.row && node.col ==
tmpNode.col) return i; } return -1;
}
private void clearVisited() {
for(int i=0; i<nodes.size(); i++) {
nodes.get(i).wasVisited = false; }
}
private void displayNode() {
for(Node node: listVisitedNodes) {
System.out.println(node.label); }
}
private Node getUnvisitedAdjacentNode(Node currentNode) {
Node adjNode = null;
for(int i=0; i<currentNode.adjNode.size(); i++) {
if(currentNode.adjNode.get(i).wasVisited == false) return currentNode.adjNode.get(i);
} return adjNode;
}
private boolean solveWithDFS(Node startNode, Node goalNode) {
listVisitedNodes.clear();
Node currentNode = nodes.get(getIndex(startNode));
nodes.get(getIndex(startNode)).wasVisited = true;
stackNodes.push(currentNode);
listVisitedNodes.add(currentNode);
while(!stackNodes.isEmpty()) {
Node tmpNode = stackNodes.peek();
currentNode = getUnvisitedAdjacentNode(tmpNode);
if(currentNode != null) {
nodes.get(getIndex(currentNode)).wasVisited = true; listVisitedNodes.add(currentNode); if(currentNode.label.contentEquals(goalNode.label)) {
clearVisited(); return true;
}
stackNodes.push(currentNode); } else {
stackNodes.pop(); }
}
clearVisited(); return false;
}
private boolean solveWithBFS(Node startNode, Node goalNode) {
listVisitedNodes.clear();
Node currentNode = nodes.get(getIndex(startNode));
nodes.get(getIndex(startNode)).wasVisited = true;
queueNodes.add(currentNode);
listVisitedNodes.add(currentNode);
while(!queueNodes.isEmpty()) {
Node tmpNode = queueNodes.peek();
currentNode = getUnvisitedAdjacentNode(tmpNode);
if(currentNode != null) {
nodes.get(getIndex(currentNode)).wasVisited = true;
listVisitedNodes.add(currentNode);
if(currentNode.label.contentEquals(goalNode.label)) {
clearVisited(); return true;
}
queueNodes.add(currentNode);
} else { queueNodes.remove();
} }
clearVisited(); return false;
}
public static void main(String[] args) { // TODO code application logic here MazeSolver ms = new MazeSolver("NSEW");
ms.startNode = new Node(0,2); ms.goalNode = new Node(4,4);
for(Node node: ms.nodes) {
System.out.print(node.label+":\t"); for(Node nodeAdj: node.adjNode) {
System.out.print(nodeAdj.label+" "); } System.out.println();
}
System.out.println("Solve with DFS");
if(ms.solveWithDFS(ms.startNode, ms.goalNode)) {
ms.displayNode(); System.out.println("Solving with
"+ms.listVisitedNodes.size()+" visiting node"); } else {
System.out.println("Goal State didn\'t find"); }
System.out.println("\n\nSolve with BFS : "); if(ms.solveWithBFS(ms.startNode, ms.goalNode)) {
ms.displayNode(); System.out.println("Solving with
"+ms.listVisitedNodes.size()+" visiting node"); } else {
System.out.println("Goal State didn\'t find"); }
}
}
7. Hasil penelusuran DFS dengan urutan operator NORTH-SOUTH-EAST-WEST :
(0,2), (1,2), (1,3), (2,3), (3,3), (3,4), (4,4)
8. Hasil penelusuran BFS dengan urutan operator NORTH-SOUTH-EAST-WEST : (0,2),
(1,2), (1,3), (1,1), (2,3), (2,1), (1,0), (3,3), (3,1), (0,0), (3,4), (3,2), (4,1), (4,4)
9. Kesimpulan anda ?
- Pada metode DFS, program akan menelusuri suatu node sampai ke child yang paling
ujung sebelum melanjutkan ke node selanjutnya yang levelnya lebih tinggi.
- Pada metode BFS, program akan melakukan pencarian dimulai dari node-node
dengan level paling tinggi sebelum menuju ke node dengan level yang lebih rendah
