Archive for the ‘Algorithm’ Category

Region Growing Algorithm is one of pathfinding solutions and it is simple to implement.  For example,  in a game you have a map of two-dimensional-array and you want to move a character from start point to end point. The advantages if you use Region Growing are you don’t have to check every tiles and effective if your map is not perfect maze.

Here’s the preudocode :
1. Create a list of the four adjacent cells (right left up down), with a counter variable of the current element’s counter variable + 1
2. Check all cells in each list for the following two conditions:
– If the cell is a wall, remove it from the list
– If there is an element in the main list with the same coordinate and an equal or lower counter, remove it from the list
3. Add all remaining cells in the list to the end of the main list
4. Go to the next item in the list
5. Stop if :
– You find the goal
– All adjacent cells are invalid and you still can’t find the goal (impossible)
6. If you found the goal, track solution path in reversed way.

Here’s the example, a character (start) and a goal. the obstacles are trees (we will ignore them). In images below, we need 5 iterations before we find the goal, and once the goal is found, we’ll built the solution in reversed way ( starting from 5 to 0; 5-4-3-2-1-0 )

Problem yang pertama adalah mengenai longest common subsequence dengan menggunakan tiga sekuen. Algoritma ini memiliki tujuan untuk mendapatkan subsekuen yang sama secara berurutan dan tentunya yang paling panjang dari ketiga subsekuen.

Contoh :

Sekuen Pertama : SURABAYA
Sekuen Kedua : SURAKARTA
Sekuen Ketiga : PASURUAN
Hasil : SURA


Algoritma solusi menggunakan solusi dynamic programming. Sebenarnya LCS dengan tiga sekuen sama saja dengan LCS menggunakan dua sekuen. Namun bedanya disini, dalam mengelesaikan LCS dengan tiga string, dibutuhkan array tiga dimensi yang volumenya adalah X.Y.Z dimana X, Y, dan Z adalah panjang dari ketiga sekuen.
Solusi optimal yang dihasilkan akan didapatkan di elemen array yang terakhir, yaitu array dengan indeks X-1, Y-1, dan Z-1
Petbedaan lainnya dalam LCS menggunakan tiga sekuen, arah/direction yang perlu di-cek adalah sebanyak tujuh arah. Tujuh arah tersebut yang direpresentasikan dengan angka adalah sebagai berikut :

0 menuju ke c[i – 1, j – 1, k – 1]
1 menuju ke c[i – 1, j – 1, k]
2 menuju ke c[i – 1, j, k – 1]
3 menuju ke c[i, j – 1, k – 1]
4 menuju ke c[i, j, k – 1]
5 menuju ke c[i, j – 1, k]
6 menuju ke c[i – 1, j, k]


Sorting Algorithm

Posted: July 28, 2008 in Algorithm, Programming
Tags: ,

Lets talk about something hard….its about algorithm…yep of source..its a logic
udahan bahasa inggrisnya
langsung aja ke pembahasan: