Konstruksi Extreme Point Deterministic Algorithm Melalui Algoritma Kruskal dan Algoritma Prim pada Masalah Multi-Criteria Minimum Spanning Tree

Abstract

Kajian MCMST merupakan pengembangan dari masalah optimasi MST dengan memuat dua
kriteria atau lebih. Salah satu algoritma yang mampu untuk menyelesaikan masalah MCMST adalah EPDA.
EPDA memiliki tiga tahapan. Sebagai fondasi awal, pada tahap pertama dibangun dari Algoritma Kruskal
atau Algoritma Prim dengan memperhatikan kriteria yang bersesuaian satu per satu. Kemudian pada
tahap kedua dan ketiga dilakukan proses mutasi sampai akhirnya didapatkan pohon merentang baru yang
menjadi solusi efisien atau Pareto Front. Dengan perbedaan karakteristik yang dimiliki Algoritma Kruskal
dan Algoritma Prim, penulis ingin menjelaskan perbandingan antara EPDA yang dibangun dari Algoritma
Kruskal dan EPDA yang dibangun dari Algoritma Prim.
Secara umum, baik EPDA dengan Algoritma Kruskal maupun EPDA dengan Algoritma Prim
menghasilkan solusi yang sama. Adapun perbedaan yang dihasilkan terdapat ada indeks yang digunakan.
Kemudian untuk memperkecil banyaknya kemungkinan solusi yang diberikan, maka pada saat pemilihan
sisi baik untuk Algoritma Kruskal maupun Algoritma Prim tidak hanya memperhatikan kriteria yang
dikerjakan, namun sekaligus memperhatikan pertimbangan solusi yang termuat dalam tabel Edge List.
Oleh karena itu, dengan diperoleh banyaknya kemungkinan solusi yang lebih sedikit, maka proses
penyelesaian yang dilakukan menjadi lebih singkat.