- Adversarial search bekerja dengan cara mencari berbagai kemungkinan solusi atas sebuah masalah. menyelidiki dua penggunaan pencarian di mana kita dapat menerapkan strategi lain untuk mencari ruang state. jadi operator tertentu diluar control anda, anda tidak bisa mengontrol gerak lawan.
Adversarial Search pada Problem Game
• Initial State: posisi board dan pemain
• Successor Function: mengembalikan daftar
kemungkinan langka pemain
• Terminal Test: penentuan syarat game
berakhir
• Utility function: nilai dari setiap state
• Game Tree: kemungkinan langkah pemain
(state) berdasarkan langkah sebelumnya
contoh : game catur , tic tac toe
CSP atau Constraint Satisfaction Problem adalah permasalahan yang tujuannya adalah mendapatkan suatu kombinasi variabel-variabel tertentu yang memenuhi aturan-aturan (constraints) tertentu.
contoh : Pemetaan 3 warna pada peta
2. Logika Proposisi (Propositional Logic) menawarkan logika dalam bentuk sederhana sehingga mudah dipahami. Meskipun begitu, Logika Proposisi sudah mampu membantu menarik kesimpulan. Namun, banyak kasus yang muncul akan menjadi terlihat panjang dan rumit saat diwujudkan dalam bentuk Logika Proposisi. Dan itu bisa lebih panjang dan rumit dibandingkan problem itu sendiri.
Beberapa contoh operator logika adalah:
~ (negasi)
^ (konjungsi)
V (disjungsi)
=> (implikasi)
<=> (ekuivalensi)
Tabel kebenaran
contoh :
p : motor itu bannya kurang angin
q : motor itu kehabisan bahan bakar
Motor itu bannya kurang angin dan kehabisan bahan bakar dapat disimbolkan dengan
p ^ q
3. contoh codingan A* java
| package aStar; |
| import java.util.ArrayList; |
| import java.util.Collections; |
| import aStar.heuristics.AStarHeuristic; |
| import aStar.utils.Logger; |
| publicclassAStar{ |
| privateAreaMap map; |
| privateAStarHeuristic heuristic; |
| //private int startX; |
| //private int startY; |
| //private int goalX; |
| //private int goalY; |
| /** |
| privateArrayList<Node> closedList; |
| privateSortedNodeList openList; |
| privatePath shortestPath; |
| Logger log =newLogger(); |
| AStar(AreaMap map,AStarHeuristic heuristic){ |
| this.map = map; |
| this.heuristic = heuristic; |
| closedList =newArrayList<Node>(); |
| openList =newSortedNodeList(); |
| } |
| publicPath calcShortestPath(int startX,int startY,int goalX,int goalY){ |
| //this.startX = startX; |
| //this.startY = startY; |
| //this.goalX = goalX; |
| //this.goalY = goalY; |
| |
| map.setStartLocation(startX, startY); |
| map.setGoalLocation(goalX, goalY); |
| |
| if(map.getNode(goalX, goalY).isObstacle){ |
| returnnull; |
| } |
| map.getStartNode().setDistanceFromStart(0); |
| closedList.clear(); |
| openList.clear(); |
| openList.add(map.getStartNode()); |
| |
| while(openList.size()!=0){ |
| |
| Node current = openList.getFirst(); |
| |
| if(current.getX()== map.getGoalLocationX()&& current.
getY()== map.getGoalLocationY()){ |
| return reconstructPath(current); |
| } |
| openList.remove(current); |
| closedList.add(current); |
| |
| for(Node neighbor : current.getNeighborList()){ |
| boolean neighborIsBetter; |
| |
| if(closedList.contains(neighbor)) |
| continue; |
| |
| if(!neighbor.isObstacle){ |
| |
| float neighborDistanceFromStart =(current.getDistanceFromStart()+ map.getDistanceBetween(current, neighbor)); |
| |
| if(!openList.contains(neighbor)){ |
| openList.add(neighbor); |
| neighborIsBetter =true; |
| |
| }elseif(neighborDistanceFromStart < current.getDistanceFromStart()){ |
| neighborIsBetter =true; |
| }else{ |
| neighborIsBetter =false; |
| } |
| |
| if(neighborIsBetter){ |
| neighbor.setPreviousNode(current); |
| eighbor.setDistanceFromStart(neighborDistanceFromStart); |
| neighbor.setHeuristicDistanceFromGoal(heuristic.getEstimated
DistanceToGoal(neighbor.getX(),neighbor.getY(), map.getGoalLocationX(), map.getGoalLocationY())); |
| } |
| } |
| } |
| } |
| returnnull; |
| } |
| publicvoid printPath(){ |
| Node node; |
| for(int x=0; x<map.getMapWith(); x++){ |
| if(x==0){ |
| for(int i=0; i<=map.getMapWith(); i++) |
| System.out.print(“-“); |
| System.out.println(); |
| } |
| System.out.print(“|”); |
| for(int y=0; y<map.getMapHeight(); y++){ |
| node = map.getNode(x, y); |
| if(node.isObstacle){ |
| System.out.print(“X”); |
| }elseif(node.isStart){ |
| System.out.print(“s”); |
| }elseif(node.isGoal){ |
| System.out.print(“g”); |
| }elseif(shortestPath.contains(node.getX(), node.getY())){ |
| System.out.print(“¤”); |
| }else{ |
| System.out.print(” “); |
| } |
| if(y==map.getMapHeight()) |
| System.out.print(“_”); |
| } |
| System.out.print(“|”); |
| System.out.println(); |
| } |
| for(int i=0; i<=map.getMapWith(); i++) |
| System.out.print(“-“); |
| } |
| privatePath reconstructPath(Node node){ |
| Path path =newPath(); |
| while(!(node.getPreviousNode()==null)){ |
| path.prependWayPoint(node); |
| node = node.getPreviousNode(); |
| } |
| this.shortestPath = path; |
| return path; |
| } |
| privateclassSortedNodeList{ |
| privateArrayList<Node> list =newArrayList<Node>(); |
| publicNode getFirst(){ |
| return list.get(0); |
| } |
| publicvoid clear(){ |
| list.clear(); |
| } |
| publicvoid add(Node node){ |
| list.add(node); |
| Collections.sort(list); |
| } |
| publicvoid remove(Node n){ |
| list.remove(n); |
| } |
| publicint size(){ |
| return list.size(); |
| } |
| publicboolean contains(Node n){ |
| return list.contains(n); |
| } |
| } |
| } |
www.binus.ac.id