Minimalisasi Panjang Kabel

Masalah saya seperti ini:

1. Saya memiliki tata letak fisik yang direpresentasikan sebagai grafik. Node mewakili kait / saluran di mana kawat dapat berlabuh dan Tepi adalah koneksi yang mungkin antara 2 node dari mana kawat bisa pergi.

2. Ada beberapa Node khusus, yang disebut splitter, dari mana satu kawat dapat dipecah menjadi 2 atau lebih hingga k. K dapat diambil konstan untuk saat ini tetapi bervariasi dari node ke node. Tidak semua node adalah splitter.

3. Ada satu sumber daya dari mana kawat akan muncul. Itu sumbernya. Kawat harus dibawa ke n tenggelam.

4. Tepi dapat mengambil sejumlah kabel yang melewatinya ke arah mana pun.

5. Panjang total kawat harus diminimalkan.

6. Sifat grafik, planar atau euclidean tidak diketahui.

Contoh : Di bawah ini adalah contoh jaringan. Node diberi nama sebagai angka dan tepi disediakan dengan bobot yang sama dari 1. Sumber adalah Node1 dan Sinks adalah Node5, Node9 dan Node13. Dalam kasus 1 Node6 adalah simpul Splitter. Dalam kasus 2 Node6 dan Node4 adalah node splitter. Simpul splitter's k = 3, yaitu, ia dapat mengambil dalam satu kawat dan membaginya menjadi 3 kabel.

Kasus 1 . Hanya satu Node splitter. Masuk akal untuk membagi di Node6.

Kasus 2 . Dua Node pembagi. Masuk akal untuk membagi di Node4 bukan Node6.

Saya mencari strategi yang berbeda untuk menemukan solusi umum untuk masalah ini. Grafik yang disajikan di sini adalah skala yang lebih kecil dibandingkan dengan masalah yang ada. Grafiknya statis dan tidak bisa diubah (maksud saya solusinya tidak boleh menyarankan tepi baru atau mengusulkan lokasi splitter baru). Setiap referensi ke makalah penelitian yang diterbitkan tentang masalah semacam ini juga disambut baik.

Kasus 3 . Dua Node pembagi. Masuk akal untuk memecah pada Node4 dan Node14. Perhatikan bahwa case ini memiliki bobot tepi berubah untuk Edge 8-12, 6-10 dan 10-11. Yang penting dalam hal ini adalah menelusuri kembali kawat setelah terpisah dari Node14.

Masalah ini NP-hard.

Asumsikan setiap titik adalah pembagi yang dapat dibagi ke sejumlah derajat, maka masalah Anda justru masalah pohon Steiner pada grafik , di mana set simpul sumber dan wastafel adalah simpul yang diperlukan.

$i$$k_i$

Penyederhanaannya adalah Anda dapat menghilangkan semua node perantara (persegi). Buat grafik hanya dengan simpul sumber, simpul wastafel, dan simpul splitter.

1. Dalam grafik asli Anda temukan jalur terpendek dari node sumber ke setiap node splitter dan tambahkan tepi pada grafik baru dari node sumber ke node splitter dengan panjang itu.

2. $i$$j$$i$$j$$i$$j$

3. $i$$j$$i$$j$$i$$j$

$N$$i$$k_i$

$k_i$

@Chao Xu, saya juga menemukan Steiner menjadi perkiraan terdekat untuk masalah saya. Saya menjelajahi sistem berbasis Ant untuk mengatasi masalah ini.