Pertanyaan Berapa biaya minimum untuk menghubungkan semua pulau?


Ada ukuran kisi N x M. Beberapa sel pulau-pulau dilambangkan dengan '0' dan yang lainnya air. Setiap sel air memiliki nomor di atasnya yang menunjukkan biaya sebuah jembatan yang dibuat pada sel itu. Anda harus menemukan biaya minimum untuk semua pulau yang dapat dihubungkan. Sebuah sel terhubung ke sel lain jika ia memiliki tepi atau titik.

Algoritme apa yang dapat digunakan untuk memecahkan masalah ini?
Edit: Apa yang bisa digunakan sebagai pendekatan brute force jika nilai N, M sangat kecil, katakan NxM <= 100?

Contoh: Dalam gambar yang diberikan, sel hijau menunjukkan pulau, sel biru menunjukkan air dan sel biru muda menunjukkan sel di mana jembatan harus dibuat. Jadi untuk gambar berikut, jawabannya akan 17.

http://i.imgur.com/ClcboBy.png

Awalnya saya berpikir untuk menandai semua pulau sebagai simpul dan menghubungkan setiap pasang pulau dengan jembatan terpendek. Kemudian masalah bisa dikurangi menjadi pohon rentang Minimum, tetapi dalam pendekatan ini saya melewatkan kasus di mana ujung-ujungnya tumpang tindih. Sebagai contoh, pada gambar berikut, jarak terpendek antara dua pulau adalah 7(ditandai dengan warna kuning), jadi dengan menggunakan Pohon Rentang Minimum, jawabannya adalah 14, tetapi jawabannya seharusnya 11 (ditandai dengan warna biru muda).

image2


75
2018-05-31 08:57


asal


Jawaban:


Untuk mendekati masalah ini, saya akan menggunakan kerangka kerja pemrograman integer dan menetapkan tiga set variabel keputusan:

  • x_ij: Sebuah variabel indikator biner untuk apakah kita membangun jembatan di lokasi air (i, j).
  • y_ijbcn: Indikator biner untuk menentukan apakah lokasi air (i, j) adalah lokasi n yang menghubungkan pulau b ke pulau c.
  • l_bc: Sebuah variabel indikator biner untuk apakah pulau b dan c terhubung langsung (alias Anda bisa berjalan hanya di alun-alun jembatan dari b ke c).

Untuk biaya pembangunan jembatan c_ij, nilai obyektif untuk meminimalkan adalah sum_ij c_ij * x_ij. Kita perlu menambahkan batasan berikut ke model:

  • Kami perlu memastikan y_ijbcn variabel valid. Kita selalu bisa mencapai air jika kita membangun jembatan di sana, jadi y_ijbcn <= x_ij untuk setiap lokasi air (i, j). Lebih lanjut, y_ijbc1 harus sama dengan 0 jika (i, j) tidak membatasi pulau b. Akhirnya, untuk n> 1, y_ijbcn hanya dapat digunakan jika lokasi perairan terdekat digunakan pada langkah n-1. Mendefinisikan N(i, j) untuk menjadi kotak air tetangga (i, j), ini setara dengan y_ijbcn <= sum_{(l, m) in N(i, j)} y_lmbc(n-1).
  • Kami perlu memastikan l_bc variabel hanya disetel jika b dan c ditautkan. Jika kita mendefinisikan I(c) untuk menjadi lokasi yang berbatasan dengan pulau c, ini dapat dicapai dengan l_bc <= sum_{(i, j) in I(c), n} y_ijbcn.
  • Kami perlu memastikan bahwa semua pulau terhubung, baik secara langsung maupun tidak langsung. Hal ini dapat dilakukan dengan cara berikut: untuk setiap subset S pulau yang tidak kosong, mengharuskan setidaknya satu pulau di S dikaitkan dengan setidaknya satu pulau dalam pelengkap S, yang akan kita sebut S '. Dalam batasan, kita dapat menerapkan ini dengan menambahkan kendala untuk setiap set ukuran S yang tidak kosong <= K / 2 (di mana K adalah jumlah pulau), sum_{b in S} sum_{c in S'} l_bc >= 1.

Untuk masalah misalnya dengan K pulau, W kotak air, dan ditentukan panjang jalur maksimum N, ini adalah model pemrograman integer campuran dengan O(K^2WN) variabel dan O(K^2WN + 2^K) kendala. Jelas ini akan menjadi sulit karena ukuran masalah menjadi besar, tetapi mungkin dapat dipecahkan untuk ukuran yang Anda minati. Untuk mendapatkan rasa skalabilitas, saya akan menerapkannya dengan python menggunakan paket pulp. Mari kita mulai dengan peta 7 x 9 yang lebih kecil dengan 3 pulau di bagian bawah pertanyaan:

import itertools
import pulp
water = {(0, 2): 2.0, (0, 3): 1.0, (0, 4): 1.0, (0, 5): 1.0, (0, 6): 2.0,
         (1, 0): 2.0, (1, 1): 9.0, (1, 2): 1.0, (1, 3): 9.0, (1, 4): 9.0,
         (1, 5): 9.0, (1, 6): 1.0, (1, 7): 9.0, (1, 8): 2.0,
         (2, 0): 1.0, (2, 1): 9.0, (2, 2): 9.0, (2, 3): 1.0, (2, 4): 9.0,
         (2, 5): 1.0, (2, 6): 9.0, (2, 7): 9.0, (2, 8): 1.0,
         (3, 0): 9.0, (3, 1): 1.0, (3, 2): 9.0, (3, 3): 9.0, (3, 4): 5.0,
         (3, 5): 9.0, (3, 6): 9.0, (3, 7): 1.0, (3, 8): 9.0,
         (4, 0): 9.0, (4, 1): 9.0, (4, 2): 1.0, (4, 3): 9.0, (4, 4): 1.0,
         (4, 5): 9.0, (4, 6): 1.0, (4, 7): 9.0, (4, 8): 9.0,
         (5, 0): 9.0, (5, 1): 9.0, (5, 2): 9.0, (5, 3): 2.0, (5, 4): 1.0,
         (5, 5): 2.0, (5, 6): 9.0, (5, 7): 9.0, (5, 8): 9.0,
         (6, 0): 9.0, (6, 1): 9.0, (6, 2): 9.0, (6, 6): 9.0, (6, 7): 9.0,
         (6, 8): 9.0}
islands = {0: [(0, 0), (0, 1)], 1: [(0, 7), (0, 8)], 2: [(6, 3), (6, 4), (6, 5)]}
N = 6

# Island borders
iborders = {}
for k in islands:
    iborders[k] = {}
    for i, j in islands[k]:
        for dx in [-1, 0, 1]:
            for dy in [-1, 0, 1]:
                if (i+dx, j+dy) in water:
                    iborders[k][(i+dx, j+dy)] = True

# Create models with specified variables
x = pulp.LpVariable.dicts("x", water.keys(), lowBound=0, upBound=1, cat=pulp.LpInteger)
pairs = [(b, c) for b in islands for c in islands if b < c]
yvals = []
for i, j in water:
    for b, c in pairs:
        for n in range(N):
            yvals.append((i, j, b, c, n))

y = pulp.LpVariable.dicts("y", yvals, lowBound=0, upBound=1)
l = pulp.LpVariable.dicts("l", pairs, lowBound=0, upBound=1)
mod = pulp.LpProblem("Islands", pulp.LpMinimize)

# Objective
mod += sum([water[k] * x[k] for k in water])

# Valid y
for k in yvals:
    i, j, b, c, n = k
    mod += y[k] <= x[(i, j)]
    if n == 0 and not (i, j) in iborders[b]:
        mod += y[k] == 0
    elif n > 0:
        mod += y[k] <= sum([y[(i+dx, j+dy, b, c, n-1)] for dx in [-1, 0, 1] for dy in [-1, 0, 1] if (i+dx, j+dy) in water])

# Valid l
for b, c in pairs:
    mod += l[(b, c)] <= sum([y[(i, j, B, C, n)] for i, j, B, C, n in yvals if (i, j) in iborders[c] and B==b and C==c])

# All islands connected (directly or indirectly)
ikeys = islands.keys()
for size in range(1, len(ikeys)/2+1):
    for S in itertools.combinations(ikeys, size):
        thisSubset = {m: True for m in S}
        Sprime = [m for m in ikeys if not m in thisSubset]
        mod += sum([l[(min(b, c), max(b, c))] for b in S for c in Sprime]) >= 1

# Solve and output
mod.solve()
for row in range(min([m[0] for m in water]), max([m[0] for m in water])+1):
    for col in range(min([m[1] for m in water]), max([m[1] for m in water])+1):
        if (row, col) in water:
            if x[(row, col)].value() > 0.999:
                print "B",
            else:
                print "-",
        else:
            print "I",
    print ""

Ini membutuhkan waktu 1,4 detik untuk berjalan menggunakan pemecah default dari paket pulp (pemecah CBC) dan menghasilkan solusi yang tepat:

I I - - - - - I I 
- - B - - - B - - 
- - - B - B - - - 
- - - - B - - - - 
- - - - B - - - - 
- - - - B - - - - 
- - - I I I - - - 

Selanjutnya, pertimbangkan masalah lengkap di bagian atas pertanyaan, yaitu grid 13 x 14 dengan 7 pulau:

water = {(i, j): 1.0 for i in range(13) for j in range(14)}
islands = {0: [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)],
           1: [(9, 0), (9, 1), (10, 0), (10, 1), (10, 2), (11, 0), (11, 1),
               (11, 2), (12, 0)],
           2: [(0, 7), (0, 8), (1, 7), (1, 8), (2, 7)],
           3: [(7, 7), (8, 6), (8, 7), (8, 8), (9, 7)],
           4: [(0, 11), (0, 12), (0, 13), (1, 12)],
           5: [(4, 10), (4, 11), (5, 10), (5, 11)],
           6: [(11, 8), (11, 9), (11, 13), (12, 8), (12, 9), (12, 10), (12, 11),
               (12, 12), (12, 13)]}
for k in islands:
    for i, j in islands[k]:
        del water[(i, j)]

for i, j in [(10, 7), (10, 8), (10, 9), (10, 10), (10, 11), (10, 12),
             (11, 7), (12, 7)]:
    water[(i, j)] = 20.0

N = 7

Pemecah MIP sering mendapatkan solusi yang baik dengan relatif cepat dan kemudian menghabiskan banyak waktu mencoba untuk membuktikan optimalitas solusi. Menggunakan kode pemecah yang sama seperti di atas, program tidak selesai dalam 30 menit. Namun, Anda dapat memberikan batas waktu kepada pemecah untuk mendapatkan solusi perkiraan:

mod.solve(pulp.solvers.PULP_CBC_CMD(maxSeconds=120))

Ini menghasilkan solusi dengan nilai obyektif 17:

I I - - - - - I I - - I I I 
I I - - - - - I I - - - I - 
I I - - - - - I - B - B - - 
- - B - - - B - - - B - - - 
- - - B - B - - - - I I - - 
- - - - B - - - - - I I - - 
- - - - - B - - - - - B - - 
- - - - - B - I - - - - B - 
- - - - B - I I I - - B - - 
I I - B - - - I - - - - B - 
I I I - - - - - - - - - - B 
I I I - - - - - I I - - - I 
I - - - - - - - I I I I I I 

Untuk meningkatkan kualitas solusi yang Anda peroleh, Anda dapat menggunakan pemecah MIP komersial (ini gratis jika Anda berada di lembaga akademis dan kemungkinan tidak bebas). Sebagai contoh, inilah kinerja Gurobi 6.0.4, lagi-lagi dengan batas waktu 2 menit (meskipun dari log solusi kami membaca bahwa solver menemukan solusi terbaik saat ini dalam 7 detik):

mod.solve(pulp.solvers.GUROBI(timeLimit=120))

Ini benar-benar menemukan solusi dari nilai obyektif 16, yang lebih baik daripada OP dapat menemukannya dengan tangan!

I I - - - - - I I - - I I I 
I I - - - - - I I - - - I - 
I I - - - - - I - B - B - - 
- - B - - - - - - - B - - - 
- - - B - - - - - - I I - - 
- - - - B - - - - - I I - - 
- - - - - B - - B B - - - - 
- - - - - B - I - - B - - - 
- - - - B - I I I - - B - - 
I I - B - - - I - - - - B - 
I I I - - - - - - - - - - B 
I I I - - - - - I I - - - I 
I - - - - - - - I I I I I I 

57
2018-06-24 21:51



Masalah ini adalah varian dari pohon Steiner yang disebut pohon Steiner berbobot simpul, khusus kelas tertentu dari grafik. Secara kompak, pohon Steiner berbobot node, diberi graf tak berarah berbobot simpul di mana beberapa node adalah terminal, menemukan set termurah dari node termasuk semua terminal yang menginduksi subgraph yang terhubung. Sayangnya, saya tidak dapat menemukan pemecah apa pun dalam beberapa pencarian sepintas lalu.

Untuk merumuskan sebagai program bilangan bulat, buatlah variabel 0-1 untuk setiap node non-terminal, kemudian untuk semua himpunan bagian dari simpul non-terminal yang penghapusannya dari grafik awal memutus dua terminal, mengharuskan jumlah variabel dalam subset berada pada Setidaknya 1. Ini menyebabkan terlalu banyak kendala, jadi Anda harus menerapkannya dengan malas, menggunakan algoritma yang efisien untuk konektivitas node (aliran maks, pada dasarnya) untuk mendeteksi kendala yang dilanggar secara maksimal. Maaf karena tidak ada detailnya, tetapi ini akan merepotkan jika Anda sudah familiar dengan pemrograman integer.


3
2018-06-16 16:58



Pendekatan brute force, dalam pseudo-code:

start with a horrible "best" answer
given an nxm map,
    try all 2^(n*m) combinations of bridge/no-bridge for each cell
        if the result is connected, and better than previous best, store it

return best

Di C ++, ini bisa ditulis sebagai

// map = linearized map; map[x*n + y] is the equivalent of map2d[y][x]
// nm = n*m
// bridged = true if bridge there, false if not. Also linearized
// nBridged = depth of recursion (= current bridge being considered)
// cost = total cost of bridges in 'bridged'
// best, bestCost = best answer so far. Initialized to "horrible"
void findBestBridges(char map[], int nm,
   bool bridged[], int nBridged, int cost, bool best[], int &bestCost) {
   if (nBridged == nm) {
      if (connected(map, nm, bridged) && cost < bestCost) {
          memcpy(best, bridged, nBridged);
          bestCost = best;
      }
      return;
   }
   if (map[nBridged] != 0) {
      // try with a bridge there
      bridged[nBridged] = true;
      cost += map[nBridged];

      // see how it turns out
      findBestBridges(map, nm, bridged, nBridged+1, cost, best, bestCost);         

      // remove bridge for further recursion
      bridged[nBridged] = false;
      cost -= map[nBridged];
   }
   // and try without a bridge there
   findBestBridges(map, nm, bridged, nBridged+1, cost, best, bestCost);
}

Setelah membuat panggilan pertama (saya mengasumsikan Anda mengubah peta 2d Anda menjadi larik 1d untuk kemudahan menyalin di sekitar), bestCost akan berisi biaya jawaban terbaik, dan best akan berisi pola jembatan yang menghasilkannya. Ini sangat lambat.

Pengoptimalan:

  • Dengan menggunakan "batas jembatan", dan menjalankan algoritme untuk meningkatkan jumlah jembatan maksimum, Anda dapat menemukan jawaban minimal tanpa menjelajahi seluruh pohon. Menemukan jawaban 1-jembatan, jika ada, akan menjadi O (nm) bukan O (2 ^ nm) - peningkatan drastis.
  • Anda dapat menghindari pencarian (dengan menghentikan rekursi; ini juga disebut "pemangkasan") setelah Anda melampaui bestCost, karena tidak masuk akal untuk terus mencari sesudahnya. Jika tidak bisa menjadi lebih baik, jangan terus menggali.
  • Pemangkasan di atas bekerja lebih baik jika Anda melihat kandidat "baik" sebelum melihat yang "buruk" (seperti itu, sel semuanya dilihat dari kiri ke kanan, dari atas ke bawah). Heuristik yang baik adalah mempertimbangkan sel yang dekat dengan beberapa komponen yang tidak tersambung sebagai prioritas yang lebih tinggi daripada sel yang tidak. Namun, setelah Anda menambahkan heuristik, penelusuran Anda mulai menyerupai SEBUAH* (dan Anda perlu semacam antrean prioritas juga).
  • Gandakan jembatan dan jembatan ke mana pun harus dihindari. Jembatan apa pun yang tidak memutus jaringan pulau jika dihapus adalah mubazir.

Algoritma pencarian umum seperti SEBUAH* memungkinkan pencarian lebih cepat, meskipun menemukan heuristik yang lebih baik bukanlah tugas yang sederhana. Untuk pendekatan yang lebih spesifik masalah, gunakan hasil yang ada Pohon Steiner, seperti yang disarankan oleh @Gassa, adalah cara untuk pergi. Namun, perlu diketahui bahwa masalah membangun pohon Steiner pada grid ortogonal adalah NP-Complete, berdasarkan ini makalah oleh Garey dan Johnson.

Jika "cukup baik" sudah cukup, algoritma genetika mungkin dapat menemukan solusi yang dapat diterima dengan cepat, selama Anda menambahkan beberapa heuristik kunci sebagai penempatan jembatan yang disukai.


3
2018-06-08 16:42



Mengingat bahwa masalah ini terjadi di grid, dan Anda memiliki parameter yang terdefinisi dengan baik, saya akan mendekati masalah dengan penghapusan sistematis dari ruang masalah melalui pembuatan pohon rentang minimum. Dengan demikian, masuk akal bagi saya jika Anda mendekati masalah ini dengan Algoritma Prim.

Sayangnya, Anda sekarang mengalami masalah mengaburkan grid untuk membuat set node dan tepi ... ergo masalah sebenarnya dari posting ini adalah bagaimana cara mengonversi kotak n x m ke {V} dan {E}?

Proses konversi ini, sekilas, mungkin NP-Hard karena banyaknya kombinasi yang mungkin (menganggap bahwa semua biaya saluran air identik). Untuk menangani kejadian di mana jalur tumpang tindih, Anda harus mempertimbangkan membuat pulau virtual.

Ketika ini selesai, jalankan Algoritma Prim dan Anda akan sampai pada solusi optimal.

Saya tidak percaya bahwa Pemrograman Dinamis dapat dijalankan secara efektif di sini karena tidak ada prinsip optimalitas yang dapat diamati. Jika kita menemukan biaya minimum antara dua pulau, itu tidak berarti bahwa kita dapat menemukan biaya minimum antara kedua pulau tersebut dan pulau ketiga, atau bagian lain dari pulau yang akan (menurut definisi saya untuk menemukan MST melalui Prim) terhubung.

Jika Anda ingin kode (pseudo atau lainnya) untuk mengubah grid Anda menjadi satu set {V} dan {E}, silakan kirimi saya pesan pribadi dan saya akan melihat ke dalam penggabungan bersama implementasi.


-1
2018-06-16 17:24



Saya setuju bahwa ini adalah masalah salesman keliling, tetapi dapat dipaksakan dengan n = 7. Hitung jalur biaya min antara setiap pulau dan Anda hanya akan memiliki n (n-1) / 2 solusi = 21 perhitungan


-6
2018-06-08 14:42