Welcome to our blog

1.  Apa yang dimaksud Adversarial Search & Constraint Satisfaction Problems? Berikan contoh?

Adversary search merupakan teknik pencarian yang diterapkan dalam permainan game antara dua pihak yang saling berlawanan. Ruang keadaan dalam kasus ini direpresentasikan dengan pohon (tree) atau grafik, yang memuat giliran yang memungkinkan bagi kedua pemain. Setiap level ruang pencarian yang berlaku menunjukkan keadaan giliran yang hanya berlaku untuk satu pemain. Teknik pencarian ini terdiri atas dua tipe algoritma. Algoritma pertama yang lebih sederhana dinamakan MINIMAX, sedangkan yang lainnya (yang lebih kompleks) adalah Alpha-beta Cutoff Procedure.

Contoh : permainan Tic Tac Toe

Constraint Satisfaction Problem adalah suatu permasalahan seseorang harus mencari nilai untuk set variabel (finite) yang memenuhi set constraint (finite). Constraint Satisfaction Problem merupakan sebuah pendekatan dari problem yang bersifat matematis dengan tujuan menemukan keadaan atau obyek yang memenuhi sejumlah persyaratan atau kiteria. Sebuah Constraint diartikan sebagai batasan solusi memungkinkan dalam sebuah problem optimasi.

Contoh : Cryptarithmetic, Map-Coloring

2. Apa itu Propositional Logic? Berikan contoh?

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. Buat coding (boleh C, C++ atau Java) untuk  Algoritma A & Algoritma A* (A Star) ?

ArrayList SolutionPathList = new ArrayList();

//Create a node containing the goal state node_goal

Node node_goal = new Node(null,null,1,15,15);

//Create a node containing the start state node_start

Node node_start = new Node(null,node_goal,1,0,0);

//Create OPEN and CLOSED list

SortedCostNodeList OPEN = new SortedCostNodeList ();

SortedCostNodeList CLOSED = new SortedCostNodeList ();

//Put node_start on the OPEN list

OPEN.push (node_start);

//while the OPEN list is not empty

while (OPEN.Count>0)

{

//Get the node off the open list

//with the lowest f and call it node_current

Node node_current = OPEN.pop ();

//if node_current is the same state as node_goal we

//have found the solution;

//break from the while loop;

if (node_current.isMatch (node_goal))

{

node_goal.parentNode = node_current.parentNode ;

break;

}

//Generate each state node_successor that can come after node_current

ArrayList successors = node_current.GetSuccessors ();

//for each node_successor or node_current

foreach (Node node_successor in successors)

{

//Set the cost of node_successor to be the cost of node_current plus

//the cost to get to node_successor from node_current

//–> already set while we were getting successors

//find node_successor on the OPEN list

int oFound = OPEN.IndexOf (node_successor);

//if node_successor is on the OPEN list but the existing one is as good

//or better then discard this successor and continue

if (oFound>0)

{

Node existing_node = OPEN.NodeAt (oFound);

if (existing_node.CompareTo (node_current) <= 0)

continue;

}

//find node_successor on the CLOSED list

int cFound = CLOSED.IndexOf (node_successor);

//if node_successor is on the CLOSED list

//but the existing one is as good

//or better then discard this successor and continue;

if (cFound>0)

{

Node existing_node = CLOSED.NodeAt (cFound);

if (existing_node.CompareTo (node_current) <= 0 )

continue;

}

//Remove occurences of node_successor from OPEN and CLOSED

if (oFound!=-1)

OPEN.RemoveAt (oFound);

if (cFound!=-1)

CLOSED.RemoveAt (cFound);

//Set the parent of node_successor to node_current;

//–> already set while we were getting successors

//Set h to be the estimated distance to node_goal

//(Using heuristic function)

//–> already set while we were getting successors

//Add node_successor to the OPEN list

OPEN.push (node_successor);

}

//Add node_current to the CLOSED list

CLOSED.push (node_current);

}