Konstruksi extreme point deterministic algorithm melalui algoritma kruskal dan algoritma prim pada masalah multi-criteria minimum spanning tree

INDONESIA:

Kajian MCMST merupakan pengembangan dari masalah optimasi Minimum Spanning Tree (MST) dengan memuat dua kriteria atau lebih. Salah satu algoritma yang mampu untuk menyelesaikan masalah MCMST adalah EDPA. 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 spanning tree 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 pada 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 bobot yang termuat dalam tabel Edge List. Oleh karena itu, dengan diperolehnya banyaknya kemungkinan solusi yang lebih sedikit, maka proses penyelesaian yang dilakukan menjadi lebih singkat.

ENGLISH:

The study of MCMST is the development of Minimum Spanning Tree (MST) optimization problem by containing two or more criteria. One of the algorithms that can solve the MCMST problems is EDPA. EPDA has three stages. As the initial foundation, the first stage is built from Kruskal’s Algorithm or Prim’s Algorithm by considering the corresponding criteria one by one. Then on the second and third stages the process of mutations are carried out until the new spanning trees that is the efficient solution or Pareto Front are obtained.

By the difference between the characteristic of Kruskal's Algorithm and Prim's Algorithm, the author will explain a comparison between EPDA constructed by Kruskal's Algorithm and EPDA constructed by Prim's Algorithm.

In general, either EPDA constructed by Kruskal’s Algorithm or EPDA constructed by Prim's Algorithm produces the same solution. As for the difference found is the use of indexes. Then, to minimize the amount of the given solution, the better sides choosen by Kruskal's Algorithm or Prim's Algorithm not only consider to the criteria, but also consider to the weights contained in the table of Edge List. Therefore, by getting the amount of the given solution that is less, then the process of solving can be shorter.