Büyüklükte bir kafes varN x M. Bazı hücreler vardıradalar'0' ve diğerleri . tarafından belirtilen ^em>su. Her su cep numarası bir köprü hücre üzerinde yapılan maliyeti ifade etti. Bunun için tüm adalar birbirine bağlanabilir minimum maliyetle bulmak zorunda. Bir hücre eğer bir kenar veya tepe noktası paylaşır ise başka bir hücreye bağlı.

Ne algoritması bu sorunu çözmek için kullanılabilir mi ?
Düzenleme:Eğer N, M değerleri çok küçük bir kaba kuvvet yaklaşımı olarak kullanılabilir, bu yüzden olmak üzere < ki;= 100?

ÖrnekVerilen görüntü, yeşil hücre Adaları, mavi hücreleri su ve açık mavi hücreler üzerinde bir köprü yapılmalıdır hücreleri gösterir işaret eder. Aşağıdaki resim için böylece cevabı olacaktır17.

Başlangıçta düğümler olarak tüm adalar işaretleme ve kısa bir köprü ile adalar her çift birbirine bağlayan düşündüm. O zaman sorun Minimum yayılan ağaç için azaltılmış olabilir, ama bu yaklaşım kenarları üst üste olması durumunda özledim.Örneğinaşağıdaki görüntüde, her iki ada arasındaki en kısa mesafedir7(sarı işaretli), yani en Az Kapsayan Ağaç kullanarak cevap olacak14cevabı olmalı ama11(mavi işaretli).

Bu sorunla ilgili olarak, tamsayı programlama bir çerçeve kullanmak ve karar değişkenleri üç set tanımlamak istiyorum:

• x_ij: Su konumu (i, j) bir köprü inşa ediyoruz olsun için ikili gösterge değişken.
• y_ijbcnBir ikili su konumu (i, j) n^th olup konumu ada c ada b bağlama göstergesi.
• l_bc: İkili bir gösterge olup olmadığını Adaları b ve c için değişken doğrudan sadece c için b) meydanlarda yürüyebilir aka () bağlantılıdır.

Köprü inşa masrafları içinc_ij, en aza indirmek için objektif değeri sum_ij c_ij * x_ij. Modele aşağıdaki kısıtlar ekleyelim:

• Bu emin olmamız gerekiry_ijbcndeğişkenler geçerlidir. Her zaman sadece bir köprü var, her yer su için y_ijbcn <= x_ij (i, j) biz de yapsak su bir kare ulaşabiliriz. Daha fazla 0 eğer (i, j) eşit olmalıdır sınır ada b değildir. Son olarak, n ^ için . 1, y_ijbcn yalnızca komşu su bir konuma adımda n-1 kullanılmış olabilir. Su kareler komşu olmak N(i, j) (i, j) tanımlama, bu y_ijbcn <= sum_{(l, m) in N(i, j)} y_lmbc(n-1) eşdeğerdir.
• Bu emin olmamız gerekirl_bcdeğişkenleri yalnızca b kümesi ve c bağlı. Biz I(c) yerler ada c sınır olarak tanımlarsanız, bu l_bc <= sum_{(i, j) in I(c), n} y_ijbcn ile yapılabilir.
• Tüm adalar, doğrudan veya dolaylı olarak bağlı olduğundan emin olmamız gerekir. Bu yapılabilir şu şekilde: her boş olmayan uygun alt S Adaları, gerektiren en az bir adada S bağlı en az bir adada tamamlayan, hangi ararız S'. Kısıtlamaları, biz uygulamak bu ekleyerek bir kısıtlama için her boş olmayan S kümesi boyutu <= K/2 (K) sayısıdır Adaları), sum_{b in S} sum_{c in S'} l_bc >= 1.

K adalar, su meydanları, ve belirtilen maksimum yol uzunluğu N W ile ilgili bir sorun örneğin, bu O(K^2WN) değişkenler ve O(K^2WN 2^K) kısıtlamaları ile karışık tamsayı programlama modelidir. Açıkçası bu boyutu büyük olur sorun gibi inatçı olacak, ama değer verdiğin ölçüler için çözülebilir olabilir. Güç sağlıyor bir anlamda almak için, python bu hamuru paketini kullanarak yerine getireceğim. Soru dibinde 3 adalar: küçük 7 x 9 harita ile hadi başlayalım

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
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

# 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 ""

Bu 1.4 saniye hamuru paketinden varsayılan çözücü (CBC çözücü) kullanarak ve çıkışları çalıştırmak için gereken doğru çözüm:

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

Sonraki, 7 ada ile 13 x 14 kılavuz olan soru üst: tam sorununu ele alalım

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

MİP çözücüler genellikle iyi çözümler nispeten hızlı bir şekilde elde ve çözümün zaman kavramı kanıtlamaya çalıştığı hakkında büyük bir harcama. Yukarıdaki kod çözücü kullanarak, programını 30 dakika içinde tamamlanmaz. Ancak, çözücü için bir zaman aşımı yaklaşık bir çözüm elde edilmesini sağlar

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

Bu amaç değeri 17 ile bir çözüm üretir:

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 

Elde ettiğimiz çözümlerin kalitesini yükseltmek için, ticari MİP bir çözücü (eğer akademik bir kurumda iseniz, ücretsiz ve büyük olasılıkla serbest yoksa) kullanabilirsiniz. Örneğin, burada performans Gurobi 6.0.4, tekrar ile 2 dakika zaman sınırı (gerçi çözüm günlük okuduğumuz çözücü bulunan mevcut en iyi çözüm içinde 7 saniye):

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

Bu aslında objektif değer bir çözüm 16, OP el bulmak ile mümkün olandan daha iyisini bulur!

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