Electronic Theses and Dissertation

Penelitian ini membahas tentang penyempurnaan algoritma findSegment dengan mengurangi backtracking. Salah satu cara untuk mengurangi backtracking yaitu dengan mencari aturan-aturan pemilihan segment pembentuk Hamiltonian cycle dan membandingkan jumlah backtracking pada setiap aturannya. Ada delapan aturan yang ditemukan, aturan-aturan tersebut disimbolkan dengan aturan I-A, I-B, II-A, II-B, III-A, III-B, IV-A, dan IV-B. Aturan dengan tipe A bermakna proses pemilihan segment dengan memilih adjacent vertex yang memiliki derajat vertex terkecil, atau |AdjV[i]-Adj| terkecil, atau |AdjV[i]-Ept| terkecil, atau |(AdjV[i]-Adj)-Ept| terkecil, dengan AdjV[i] dan Adj adalah himpunan adjacent vertex dan Ept adalah himpunan endpoint. Aturan dengan tipe B bermakna proses pemilihan segment dengan memilih adjacent vertex yang memiliki derajat vertex terbesar, atau |AdjV[i]-Adj| terbesar, atau |AdjV[i]-Ept| terbesar, atau |(AdjV[i]-Adj)-Ept| terbesar. Jika ada lebih dari satu adjacent vertex yang memenuhi syarat, maka akan dipilih adjacent vertex dengan label terkecil. Kedelapan aturan pemilihan segment tersebut diuji pada 30 graf Petersen yang pada dasarnya merupakan graf non-Hamilton maksimal kemudian dimodifikasi menjadi graf Hamilton dengan menambahkan satu edge baru. Hasil pengujian menunjukkan bahwa aturan tipe A memiliki jumlah backtracking jauh lebih sedikit dibandingkan aturan tipe B. Aturan yang memiliki jumlah backtracking terkecil yaitu aturan III-A dengan jumlah backtracking 16 kali. Aturan yang memiliki jumlah backtracking terbesar yaitu aturan I-B dengan jumlah backtracking 84 kali. Aturan I-A, II-A, dan IV-A memiliki jumlah backtracking yang berdekatan dengan aturan III-A, sedangkan aturan II-B, III-B, dan IV-B memiliki jumlah backtracking yang berdekatan dengan aturan I-B. Secara umum dapat disimpulkan bahwa aturan tipe B sangat tidak efisien untuk diterapkan pada algoritma findSegment.

Tidak Tersedia Deskripsi