Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A Minimal-State Processing Search Algorithm for Graph Coloring Problems Algoritma Carian Pemprosesan Keadaan Minimum untuk Masalah Mewarna Graf

Nobuo FUNABIKI, Teruo HIGASHINO

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

Kertas kerja ini membentangkan algoritma pewarnaan graf heuristik yang dinamakan MIPS_CLR, algoritma Carian Pemprosesan keadaan MInimal untuk masalah CoLoRing graf. Diberi graf G(V, E), matlamat masalah NP-lengkap ini adalah untuk mencari penetapan warna pada setiap bucu masuk V supaya mana-mana pasangan bucu bersebelahan tidak boleh menerima warna yang sama tetapi juga jumlah bilangan warna harus diminimumkan. Masalah pewarnaan graf telah dikaji secara meluas kerana bilangan aplikasi praktikalnya yang banyak dalam pelbagai bidang. Dalam MIPS_CLR, peringkat pembinaan mula-mula menghasilkan keadaan minimum awal yang terdiri daripada sebanyak bucu berwarna oleh algoritma tamak mudah, selepas kumpulan maksimum G ditemui oleh algoritma klik maksimum. Kemudian, peringkat penghalusan secara berulang mencari keadaan penyelesaian sambil mengekalkan keminimuman dari segi fungsi kos dengan kaedah peralihan keadaan minimum. Dalam kaedah ini, skema pemilihan warna terbaik, pemilihan warna rawak, shuffle penetapan warna dan pengembangan warna secara beransur-ansur digunakan bersama-sama untuk merealisasikan carian turunan diskret dengan keupayaan mendaki bukit. Prestasi MIPS_CLR dinilai melalui penyelesaian kejadian graf penanda aras DIMACS, di mana kualiti penyelesaian umumnya lebih baik daripada algoritma sedia ada manakala masa pengiraan adalah setanding dengan algoritma sedia ada yang terbaik. Khususnya, MIPS_CLR menyediakan penyelesaian sempadan bawah baharu untuk beberapa keadaan. Hasil simulasi mengesahkan keupayaan carian meluas pendekatan MIPS_CLR kami untuk masalah pewarnaan graf.

Jawatankuasa
IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.7 pp.1420-1430
Tarikh penerbitan
2000/07/25
Diumumkan
ISSN dalam talian
DOI
Jenis Manuskrip
PAPER
kategori
Graf dan Rangkaian

Pengarang

Kata kunci

Contents [show]