perceptron

Hebian Learning

gerbang logika

backpropagation

stable mariage

The Stable Marriage Problem

Ada 8 pasang pria (man) dan wanita (woman), maka array yang terbentuk adalah sebagai berikut :
1. man = 8
2. woman = 8
3. rank = 8
4. mP(man, rank) = mP (8, 8)
contoh:

Man\ Rank 1 2 3 4 5 6 7 8
Man 1 select woman 3 6 7 1 8 4 5 2
2 6 3 1 3 5 8 2 7
3 8 4 1 5 6 3 7 2
4 3 8 4 2 5 6 7 1
5 8 3 4 5 6 1 7 2
6 8 7 5 2 4 3 1 6
7 2 4 6 3 1 7 5 8
8 6 1 4 2 7 5 3 8

5. wP(woman, rank) = wP(8, 8)
6. m(man) = m(8)
7. w(woman) = w(8)
8. single(woman) = single(8) = (T, T, T, T, T, T, T, T)  merupakan array Boolean
ABSTRAKSI
PROCEDURE try(man,sukses)
r = ranking
FOR r = 1 sampai 8
Pemilihan woman oleh man berdasarkan ranking
IF woman tsb single ?
THEN Pasangkan man dengan woman single dan woman tsb tidak single
IF man<8 THEN CALL try(man+1, sukses_berikut ELSE cetak pasangan Batalkan Pasangan RETURN ANALISA 1. Level = 8 2. Prioritas = 8 3. Ambil tindakan = Pasangkan man dengan woman single dan single = false for (int i = 0; i < m.length; i++) { System.out.println(i + " + " + m[i]); } 4. if tindakan dapat dilakukan = Apakah Wanita tsb single ? int[] single = new int[n]; final int TRUE = -1; for (int i = 0; i < single.length; i++) single[i] = TRUE; for (int i = 0; i < single.length; i++) PriaFree.add(i); int[] next = new int[n]; while (!PriaFree.isEmpty()) { int m = PriaFree.remove(); int w = mP[m][next[m]]; next[m]++; System.out.println("m=" + m + " w=" + w); if (single[w] == TRUE) { single[w] = m; 5. batalkan tindakan = Batalkan Pernikahan(Pilih wanita/pria lain) int m1 = single[w]; if (prefers(w, m, m1)) { single[w] = m; PriaFree.add(m1); } else { PriaFree.add(m); } private boolean prefers(int w, int x, int y) { for (int i = 0; i < 8; i++) { int pref = wP[w][i]; if (pref == x) return true; if (pref == y) return false; } // This should never happen. System.out.println("Error in wP list " + w); return false; } Program import java.util.*; import java.io.*; public class StableMarriage { private int n ; private int[][] mP; private int[][] wP; private static final boolean DEBUGGING = false; private Random rand = new Random(); public static void main(String[] args) { if (args.length != 1) { int n = 8; StableMarriage sm = new StableMarriage(n); if (n <= 10) sm.printPrefTables(); int[] marriage = sm.stable(); if (n <= 10) sm.printMarriage(marriage); return; } } public StableMarriage(int n) { this.n = n; mP = new int[n][]; wP = new int[n][]; for (int i = 0; i < n; i++) { mP[i] = new int[n]; createRandomPrefs(mP[i]); wP[i] = new int[n]; createRandomPrefs(wP[i]); } } private void createRandomPrefs(int[] v) { for (int i = 0; i < v.length; i++) v[i] = i; for (int i = v.length - 1; i > 0; i--) {
int j = rand.nextInt(i+1);
int temp = v[i];
v[i] = v[j];
v[j] = temp;
}
}
public int[] stable() {
int[] single = new int[n];
final int TRUE = -1;
for (int i = 0; i < single.length; i++) single[i] = TRUE; LinkedList PriaFree = new LinkedList();
for (int i = 0; i < single.length; i++) PriaFree.add(i); int[] next = new int[n]; while (!PriaFree.isEmpty()) { int m = PriaFree.remove(); int w = mP[m][next[m]]; next[m]++; System.out.println("Pasangan”); System.out.println("m=" + m + " w=" + w); if (single[w] == TRUE) { single[w] = m; } else { int m1 = single[w]; if (prefers(w, m, m1)) { single[w] = m; PriaFree.add(m1); } else { PriaFree.add(m); } } } return single; } private boolean prefers(int w, int x, int y) { for (int i = 0; i < 4; i++) { int pref = wP[w][i]; if (pref == x) return true; if (pref == y) return false; } System.out.println("Error in wP list " + w); return false; } public void printPrefTables() { System.out.println("Man List:"); printMatrix(mP); System.out.println("Woman List:"); printMatrix(wP); } private void printMarriage(int[] m) { System.out.println("Pernikahan: "); for (int i = 0; i < m.length; i++) System.out.println(‘(’ + i + " + " + m[i] + ‘)’); } private void printDebug(String s) { if (DEBUGGING) { System.out.println(s); } } private void printMatrix(int[][] v) { if (v == null) { System.out.println("");
return;
}
for (int i = 0; i < v.length; i++) {
for (int j = 0; j < v[i].length; j++)
System.out.print(v[i][j] + " ");
System.out.println();
}
}
}

HASIL :

Man List

Woman List

Pasangan

Pernikahan :
(0,4)
(1,5)
(2,7)
(3,6)
(4,1)
(5,0)
(6,3)
(7,2)

Urut data array dengan metode insertion Sort

CALL InputVectorDariRandom(X,N)
document.write" Metode pengurutan data dengan Insertion Sort
"
document.write "
"
CALL Cetak(x,n," Sebelum Sorting :")
CALL insertionSort(x,n)
CALL Cetak(x,n," Setelah Sorting :")

SUB InputVectorDariRandom(byRef v(), byRef N)
RANDOMIZE
N = cint(InputBox("Masukkan Jumlah Elemen Array"))
REDIM v(N)
FOR c=1 TO N
v(c)=10+int(rnd*90)
NEXT
END SUB

SUB insertionSort(byRef v(), byVal N)
FOR i=1 TO N
temp=v(i)
j=i-1
do while (j>=0) and (v(j)>temp)
v(j+1)=v(j)
j=j-1
loop
v(j+1)=temp
NEXT
END SUB

SUB Cetak(byVal v(), byVal N, message)
document.write "Isi Vektor " & message & "
"
FOR c=1 TO N
document.write v(c) & ", "
NEXT
document.write "
"
document.write "
"
END SUB

Urut data array dengan metode Selection Sort

CALL InputVectorDariRandom(X,N)
document.write" Metode pengurutan data dengan Selection Sort
"
document.write "
"
CALL Cetak(x,n," Sebelum Sorting :")
CALL SelectionSort(x,n)
CALL Cetak(x,n," Setelah Sorting :")

SUB InputVectorDariRandom(byRef v(), byRef N)
RANDOMIZE
N = cint(InputBox("Masukkan Jumlah Elemen Array"))
REDIM v(N)
FOR c=1 TO N
v(c)=10+int(rnd*90)
NEXT
END SUB

SUB SelectionSort(byRef v(), byVal jumlah)
FOR i=1 TO jumlah-1
MIN = i
FOR j=I+1 TO jumlah
IF v(j)< v ( MIN ) THEN MIN=j NEXT IF i<>MIN THEN
temp=v(i)
v(i)=v(MIN)
v(MIN)=temp
END IF
NEXT
END SUB

SUB Cetak(byVal v(), byVal N, message)
document.write "Isi Vektor " & message & "
"
FOR c=1 TO N
document.write v(c) & ", "
NEXT
document.write "
"
document.write "
"
END SUB