Perkenalan

1. Introduction

Diberikan sebuah graf berbobot tak berarah G = (V, E) dan sebuah bilangan bulat s yang mempartisi himpunan simpul V = [0, 1, ..., |V|-1] menjadi himpunan simpul diperlukan R = [0, 1, ..., s-1] dan himpunan simpul Steiner S = [s, s+1, ..., |V|-1], masalah Pohon Steiner Umum menanyakan sebuah sub-himpunan S' ⊆ S dari himpuan simpul Steiner dan pohon perentangan T = (R ⋃ S', E) dengan beban minimum. Beban dari sebuah pohon T adalah jumlah dari beban sisi-sisinya.


Masalah Pohon Steiner Umum adalah sebuah generalisasi dari masalah yang lebih terkenal yakni Pohon Perentangan Minimum (MST).


Tidak seperti MST, yang mempunyai solusi waktu polinomial (seperti, O(E log V) algoritma Kruskal/Prim), masalah Pohon Steiner Umum ini adalah masalah kombinatorik optimisasi NP-hard.

1-1. Variasi Masalah Pohon Steiner Lainnya

Ada beberapa varian lain dari masalah umum Pohon Steiner ini, seperti masalah Pohon Steiner Euclidean dan Pohon Steiner Metric.


Dalam masalah Pohon Steiner Euclidean, terdapat V titik yang berbeda (set R) pada bidang Euclidean (2 dimensi), tugasnya adalah menemukan satu set tambahan (mungkin kosong) dari titik-titik Steiner S (dapat berada di mana saja pada bidang 2 dimensi) dan sebuah pohon perentangan T = (R ⋃ S, E) sedemikian rupa sehingga bobot T diminimalkan. Bobot antara dua titik apa pun hanyalah jarak Euclidean dari kedua titik tersebut.


Dalam masalah Pohon Steiner Metric, ini mirip dengan Pohon Steiner Euclidean, tetapi kali ini titik-titik Steiner tambahan diberikan sebagai satu set S di awal. Bobot antara dua titik apa pun harus memenuhi sifat-sifat ruang metric.


Pohon Steiner Euclidean, Pohon Steiner Metric, dan masalah umum Pohon Steiner yang divisualisasikan di situs web ini, semuanya adalah masalah optimisasi NP-hard.

2. Visualisasi

Lihat visualisasi dari algoritma Pohon Steiner yang dipilih di sini.


Awalnya, semua simpul dan sisi dalam graf input diwarnai dengan garis hitam standar. Saat visualisasi berjalan, warna biru muda biru muda akan digunakan untuk menunjukkan set simpul yang diperlukan R dan warna oranye oranye akan digunakan untuk menunjukkan simpul Steiner yang sedang digunakan.


Di akhir algoritma Pohon Steiner yang dipilih, kami menampilkan pohon rentang terbaik = pohon Steiner T.

3. Masukan

Terdapat dua metode berbeda untuk membuat graf masukan:

  1. Ubah graf: Anda dapat mengubah graf tak berbobot tak terarah.
  2. Graf contoh: Anda dapat memilih dari graf contoh terhubung tak berbobot tak berarah yang tersedia.
Suatu hari, kami akan menyediakan cara mudah untuk memberi label ulang verteks-verteks dalam graf yang saat ini dimuat sehingga set verteks yang diperlukan R selalu dinomori dengan [0, 1, ..., s-1] (sehingga sisanya adalah simpul potensial Steiner S).

4. Algoritma Eksak

Terdapat 3 kasus spesial dari masalah Pohon Steiner dengan solusi waktu polinomial:

  1. s = 2, yakni simpul yang diperlukan hanya R = [0, 1], kita bisa menggunakan O((V+E) log V) algoritma Dijkstra untuk mencari Pohon Perentangan Jalur Terpendek yang menghubungni simpul awal 0 dengan simpul akhir 1 (atau sebaliknya). Pohon perentangan ini juga merupakan Pohon Steiner yang diminta.
  2. s = |V|, yakni semua |V| simpul diperlukan R = [0, 1, ..., |V|-1], kita bisa menjalakan O(E log V) algoritma Kruskal/Prim untuk mencari Pohon Perentangan Minimum (MST) dari keseluruhan graf. MST tersebut adalah Pohon Steiner yang diminta.
  3. Jika G adalah pohon: Rincian TBA.

4-1. Algoritma Eksak - Pencarian Komplet

Tetapi ketika s = [3, 4, ..., |V|-2], kita tidak punya pilihan selain menjalankan algoritma eksponensial karena kasus-kasus ini termasuk dalam kasus umum masalah Steiner-Tree umum yang NP-hard.

Salah satu cara yang mungkin adalah mencoba semua subset dari |V|-s simpul yang dapat menjadi bagian dari Steiner Tree optimal. Setiap kali, kita menggabungkan simpul-simpul dalam R = [0, 1, ..., s-1] dengan subset simpul Steiner potensial yang dipilih saat ini, menjalankan algoritma Kruskal O(E) (tanpa menyortir ulang daftar tepi berdasarkan bobot lagi) untuk masing-masing dari 2|V|-s subset yang mungkin, dan melaporkan Steiner Tree terbaik. Ini adalah algoritma eksponensial dan halaman visualisasi ini menunjukkan algoritma ini.

4-2. Algoritma Eksak - Pemrograman Dinamis

Ada algoritma eksponensial yang lebih dioptimalkan yang disebut algoritma Pemrograman Dinamis (DP) Dreyfus-Wagner yang menghindari penghitungan ulang sub-masalah.

Sayangnya, bagian ini belum didigitalkan/divisualisasikan dan sedang dalam proses pengerjaan.

5. Aproksimasi

Sialahkan melihat catatan kuliah CS4234 untuk rincian lebih lanjut.