Gale Shapley - Stable Matches Algorithm Explained

GALE - SHAPLEY ALGORITHM

 

 

 

Intinya mencari kombinasi yang terbaik yang akan dipasangkan, 

 

 

Contohnya  Kita Memiliki Biro Jodoh terdapat beberapa laki laki dan perempuan, mereka harus memilih pasangan yang lain agar dipasangkan satu sama lain , tabel di bawah menunjukan semua pria dan pilihan nya: 

 

Nama Lelaki	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Alex	Fiona	Emily	Gemma	Harrlet
Bill	Gemma	Harrlet	Fiona	Emily
Callum	Gemma	Fiona	Harrlet	Emily
David	Emily	Harrlet	Gemma	Fiona

* Setiap pilihan diurutkan berdasarkan keinginan si lelaki

 

 

Dan Diberikan pula pilihan perempuan nya

Nama Perempuan	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Emily	Callum	David	Bill	Alex
Fiona	Callum	Bill	Alex	David
Gemma	Alex	Bill	Callum	David
Harrlet	David	Callum	Bill	Alex

 

 

STEP 1

Pertama lihat alex, pilihan pertama alex memilih fiona dalam pilihan satu dam fiona memilih alex dalam pilihan 3

Nama Lelaki	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Alex	Fiona	Emily	Gemma	Harrlet
Bill	Gemma	Harrlet	Fiona	Emily
Callum	Gemma	Fiona	Harrlet	Emily
David	Emily	Harrlet	Gemma	Fiona

 

Nama Perempuan	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Emily	Callum	David	Bill	Alex
Fiona	Callum	Bill	Alex	David
Gemma	Alex	Bill	Callum	David
Harrlet	David	Callum	Bill	Alex

 

STEP 2

Lihat Bill, pilihan pertama bill memilih Gemma dalam pilihan satu dam Gemma memilih Bill dalam pilihan 2

Nama Lelaki	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Alex	Fiona	Emily	Gemma	Harrlet
Bill	Gemma	Harrlet	Fiona	Emily
Callum	Gemma	Fiona	Harrlet	Emily
David	Emily	Harrlet	Gemma	Fiona

 

Nama Perempuan	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Emily	Callum	David	Bill	Alex
Fiona	Callum	Bill	Alex	David
Gemma	Alex	Bill	Callum	David
Harrlet	David	Callum	Bill	Alex

 

 

STEP 3

Lihat Callum, pilihan pertama callum memilih Gemma dalam pilihan satu dam Gemma memilih Bill dalam pilihan 2 dan Callum pada pilihan 3 karena bill lebih dipilih karena Bill lebih dipilih sebagai prioritas daripada callum maka Gemma tidak Dipilih 

Nama Lelaki	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Alex	Fiona	Emily	Gemma	Harrlet
Bill	Gemma	Harrlet	Fiona	Emily
Callum	Gemma	Fiona	Harrlet	Emily
David	Emily	Harrlet	Gemma	Fiona

 

Nama Perempuan	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Emily	Callum	David	Bill	Alex
Fiona	Callum	Bill	Alex	David
Gemma	Alex	Bill	Callum	David
Harrlet	David	Callum	Bill	Alex

 

 

 

 

 

 

 

 

 

 

STEP 4

Lihat Callum, pilihan kedua callum memilih Fiona dalam pilihan dua dan Fiona memilih Callum pada pilihan 1 tapi dalam pilihan 3 callum memilih alex, oleh karena itu alex tidak dipilih oleh fiona , dan alex menjadi tidak terpilih. 

Nama Lelaki	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Alex	Fiona	Emily	Gemma	Harrlet
Bill	Gemma	Harrlet	Fiona	Emily
Callum	Gemma	Fiona	Harrlet	Emily
David	Emily	Harrlet	Gemma	Fiona

 

Nama Perempuan	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Emily	Callum	David	Bill	Alex
Fiona	Callum	Bill	Alex	David
Gemma	Alex	Bill	Callum	David
Harrlet	David	Callum	Bill	Alex

 

 

STEP 4

Kembali ke alex, karena fiona sudah dipilih oleh callum maka. Kita pilih emily sebagai pilihan kedua dari alex. Dan emily menerima alex pada pilihan ke 4 nya

Nama Lelaki	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Alex	Fiona	Emily	Gemma	Harrlet
Bill	Gemma	Harrlet	Fiona	Emily
Callum	Gemma	Fiona	Harrlet	Emily
David	Emily	Harrlet	Gemma	Fiona

 

Nama Perempuan	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Emily	Callum	David	Bill	Alex
Fiona	Callum	Bill	Alex	David
Gemma	Alex	Bill	Callum	David
Harrlet	David	Callum	Bill	Alex

 

 

 

 

 

 

 

 

 

 

 

STEP 5

Lihat David, David memilih Emily Sebagai Pilihan Pertama, dan Emily sudah memilih alex pada pilihan ke 4 karena david ada pada pilihan 2 maka David dipilih emily and membuat alex menjadi tidak terpilih lagi.

 

Nama Lelaki	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Alex	Fiona	Emily	Gemma	Harrlet
Bill	Gemma	Harrlet	Fiona	Emily
Callum	Gemma	Fiona	Harrlet	Emily
David	Emily	Harrlet	Gemma	Fiona

 

Nama Perempuan	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Emily	Callum	David	Bill	Alex
Fiona	Callum	Bill	Alex	David
Gemma	Alex	Bill	Callum	David
Harrlet	David	Callum	Bill	Alex

 

 

STEP 6

Lihat Alex lagi, alex memilih gemma pada pilihan 3 tetapi gemma telah memilih bill pada pilihan 2 dan alex ada pada pilihan pertama, maka bill tidak terpilih

Nama Lelaki	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Alex	Fiona	Emily	Gemma	Harrlet
Bill	Gemma	Harrlet	Fiona	Emily
Callum	Gemma	Fiona	Harrlet	Emily
David	Emily	Harrlet	Gemma	Fiona

 

Nama Perempuan	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Emily	Callum	David	Bill	Alex
Fiona	Callum	Bill	Alex	David
Gemma	Alex	Bill	Callum	David
Harrlet	David	Callum	Bill	Alex

 

 

 

 

 

 

 

 

 

 

STEP 6

Lihat Bill, Gemma sudah dipilih alex maka harrlet akan terpilih pada pilihan 2. Dan harrlet telah memilih bill pada pilihan 3, maka bill dipilih oleh harrlet

Nama Lelaki	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Alex	Fiona	Emily	Gemma	Harrlet
Bill	Gemma	Harrlet	Fiona	Emily
Callum	Gemma	Fiona	Harrlet	Emily
David	Emily	Harrlet	Gemma	Fiona

 

Nama Perempuan	Pilihan 1	Pilihan 2	Pilihan 3	Pilihan 4
Emily	Callum	David	Bill	Alex
Fiona	Callum	Bill	Alex	David
Gemma	Alex	Bill	Callum	David
Harrlet	David	Callum	Bill	Alex

 

Maka inilah stable matches yang telah diproses.

 

 

(ALEX ~ Gemma) , (Bill ~ Harrlet) , (Callum ~ Fiona) , (David ~ Emily)