N x M 크기의 격자가 있습니다 . 일부 세포는 ‘0’으로 표시된 섬 이고 다른 세포는 물 입니다. 각 워터 셀에는 해당 셀에 만들어진 다리의 비용을 나타내는 숫자가 있습니다. 모든 섬을 연결할 수있는 최소 비용을 찾아야합니다. 셀이 모서리 또는 정점을 공유하는 경우 다른 셀에 연결됩니다.
이 문제를 해결하기 위해 어떤 알고리즘을 사용할 수 있습니까? N, M의 값이 매우 작은 경우 (예 : NxM <= 100) 무차별 대입 접근 방식으로 사용할 수있는 것은 무엇입니까?
예 : 주어진 이미지에서 녹색 셀은 섬을 나타내고 파란색 셀은 물을, 하늘색 셀은 다리를 만들어야하는 셀을 나타냅니다. 따라서 다음 이미지의 경우 답은 17 입니다.
처음에는 모든 섬을 노드로 표시하고 가장 짧은 다리로 모든 섬을 연결하는 것을 생각했습니다. 그런 다음 문제를 최소 스패닝 트리로 줄일 수 있지만이 접근 방식에서는 가장자리가 겹치는 경우를 놓쳤습니다. 예를 들어 , 다음 이미지에서 두 섬 사이의 최단 거리는 7 (노란색으로 표시)이므로 최소 스패닝 트리를 사용하면 답은 14 가되지만 답은 11 (연한 파란색으로 표시) 이어야합니다 .
답변
이 문제에 접근하기 위해 정수 프로그래밍 프레임 워크를 사용하고 세 가지 의사 결정 변수 세트를 정의합니다.
- x_ij : 물 위치 (i, j)에 다리를 건설하는지 여부를 나타내는 이진 표시기 변수입니다.
- y_ijbcn : 물 위치 (i, j)가 섬 b와 섬 c를 연결하는 n 번째 위치인지 여부를 나타내는 이진 표시기입니다.
- l_bc : 섬 b와 c가 직접 연결되어 있는지 여부에 대한 이진 표시기 변수 (즉, b에서 c까지의 다리 광장에서만 걸을 수 있음).
교량 건설 비용 c_ij의 경우 최소화 할 목표 값은 sum_ij c_ij * x_ij입니다. 모델에 다음 제약 조건을 추가해야합니다.
- y_ijbcn 변수가 유효한지 확인해야 합니다. 우리는 그곳에 다리를 건설해야만 항상 워터 스퀘어에 도달 할 수 있습니다.
y_ijbcn <= x_ij모든 물 위치 (i, j)에 대해 . 또한y_ijbc1(i, j)가 아일랜드 b와 접하지 않으면 0이어야합니다. 마지막으로 n> 1 인y_ijbcn경우 n-1 단계에서 인접한 물 위치가 사용 된 경우에만 사용할 수 있습니다.N(i, j)(i, j)에 인접한 물의 제곱으로 정의 하면y_ijbcn <= sum_{(l, m) in N(i, j)} y_lmbc(n-1). - 우리는 l_bc 변수는 b와 c가 연결된 경우에만 설정 .
I(c)섬 c와 접하는 위치로 정의 하면l_bc <= sum_{(i, j) in I(c), n} y_ijbcn. - 모든 섬이 직간접 적으로 연결되도록해야합니다. 이는 다음과 같은 방법으로 수행 할 수 있습니다. 비어 있지 않은 모든 적절한 섬의 하위 집합 S에 대해 S에있는 하나 이상의 섬이 S의 보완 물에있는 하나 이상의 섬에 연결되어야합니다.이를 S ‘라고합니다. 제약 조건에서 우리는 크기가 <= K / 2 인 비어 있지 않은 모든 세트 S (여기서 K는 섬의 수)에 대한 제약 조건을 추가하여이를 구현할 수 있습니다
sum_{b in S} sum_{c in S'} l_bc >= 1.
K 아일랜드, W 워터 스퀘어 및 지정된 최대 경로 길이 N이있는 문제 인스턴스의 경우 이것은 O(K^2WN)변수와O(K^2WN + 2^K) 제약 조건 . 분명히 이것은 문제 크기가 커짐에 따라 다루기 어렵지만 관심있는 크기에 대해서는 해결할 수 있습니다. 확장 성을 이해하기 위해 pulp 패키지를 사용하여 파이썬으로 구현할 것입니다. 먼저 질문 하단에 3 개의 섬이있는 작은 7 x 9지도부터 시작하겠습니다.
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 ""
펄프 패키지의 기본 솔버 (CBC 솔버)를 사용하여 실행하는 데 1.4 초가 걸리며 올바른 솔루션을 출력합니다.
I I - - - - - I I
- - B - - - B - -
- - - B - B - - -
- - - - B - - - -
- - - - B - - - -
- - - - B - - - -
- - - I I I - - -
다음으로, 7 개의 섬이있는 13 x 14 그리드 인 질문 상단의 전체 문제를 고려하십시오.
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
MIP 솔버는 종종 좋은 솔루션을 비교적 빠르게 얻은 다음 솔루션의 최적 성을 증명하는 데 많은 시간을 소비합니다. 위와 동일한 솔버 코드를 사용하면 프로그램이 30 분 이내에 완료되지 않습니다. 그러나 대략적인 솔루션을 얻기 위해 솔버에 시간 제한을 제공 할 수 있습니다.
mod.solve(pulp.solvers.PULP_CBC_CMD(maxSeconds=120))
이렇게하면 목표 값이 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
획득 한 솔루션의 품질을 개선하기 위해 상용 MIP 솔버를 사용할 수 있습니다 (교육 기관에있는 경우 무료이며 그렇지 않으면 무료 일 가능성이 없음). 예를 들어, Gurobi 6.0.4의 성능은 다시 2 분 시간 제한이 있습니다 (솔버가 7 초 이내에 현재 최상의 솔루션을 찾았다는 것을 솔루션 로그에서 읽었음에도 불구하고).
mod.solve(pulp.solvers.GUROBI(timeLimit=120))
이것은 실제로 OP가 손으로 찾을 수있는 것보다 나은 객관적인 값 16의 솔루션을 찾습니다!
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
답변
의사 코드에서 무차별 대입 접근 방식 :
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
C ++에서는 다음과 같이 작성할 수 있습니다.
// 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);
}
첫 번째 호출을 한 후 (복사하기 쉽도록 2D 맵을 1D 배열로 변환한다고 가정합니다), bestCost최상의 답변 비용을 best포함하고이를 산출하는 브리지 패턴을 포함합니다. 그러나 이것은 매우 느립니다.
최적화 :
- “브리지 제한”을 사용하고 최대 브리지 수를 늘리는 알고리즘을 실행하면 전체 트리를 탐색하지 않고도 최소한의 답을 찾을 수 있습니다. 1-bridge 답을 찾는 것은 존재한다면 O (2 ^ nm) 대신 O (nm)가 될 것입니다.
- 를 초과하면 검색을 피할 수 있습니다 (재귀를 중지하여 “pruning”이라고도 함)
bestCost. 나중에 계속 검색하는 것은 의미가 없기 때문입니다. 나아질 수 없다면 계속 파지 마십시오. - 위의 가지 치기는 “나쁜”후보를보기 전에 “좋은”후보를 보면 더 잘 작동합니다 (그대로 셀은 모두 왼쪽에서 오른쪽, 위에서 아래 순서로 표시됨). 좋은 휴리스틱은 연결되지 않은 여러 구성 요소에 가까운 셀을 그렇지 않은 셀보다 우선 순위가 높은 것으로 간주하는 것입니다. 그러나 휴리스틱 스를 추가하면 검색이 A * 와 비슷해지기 시작합니다 (그리고 일종의 우선 순위 대기열도 필요합니다).
- 중복 된 교량과 교량은 피해야합니다. 제거해도 아일랜드 네트워크의 연결을 끊지 않는 브리지는 중복됩니다.
A * 와 같은 일반 검색 알고리즘 은 더 나은 휴리스틱을 찾는 것이 간단한 작업이 아니지만 훨씬 빠른 검색을 허용합니다. 좀 더 문제에 특화된 접근 방식의 경우 @Gassa가 제안한 것처럼 Steiner 트리의 기존 결과를 사용하는 것이 좋습니다. 그러나 Garey와 Johnson 이 작성한 이 논문에 따르면 직교 그리드에 Steiner 트리를 구축하는 문제는 NP-Complete 입니다.
“충분히 좋은”것으로 충분하다면, 선호하는 브리지 배치에 대한 몇 가지 핵심 휴리스틱 스를 추가하는 한 유전 알고리즘은 수용 가능한 솔루션을 빠르게 찾을 수 있습니다.
답변
이 문제는 특정 클래스의 그래프를 전문화 한 노드 가중치 스타이너 트리 라고하는 스타이너 트리의 변형입니다 . 간결하게 노드 가중치 스타이너 트리는 일부 노드가 터미널 인 노드 가중치 무 방향 그래프가 주어지면 연결된 하위 그래프를 유도하는 모든 터미널을 포함하여 가장 저렴한 노드 집합을 찾습니다. 슬프게도 일부 간단한 검색에서 솔버를 찾을 수없는 것 같습니다.
정수 프로그램으로 공식화하려면 각 비 터미널 노드에 대해 0-1 변수를 만든 다음 시작 그래프에서 제거하여 두 터미널의 연결을 끊는 비 터미널 노드의 모든 하위 집합에 대해 하위 집합의 변수 합계가 다음과 같아야합니다. 이는 너무 많은 제약을 유도하므로 노드 연결을위한 효율적인 알고리즘 (기본적으로 최대 흐름)을 사용하여 최대로 위반 된 제약 조건을 감지하여 제약 조건을 느리게 적용해야합니다. 세부 사항이 부족해서 미안하지만 정수 프로그래밍에 이미 익숙하더라도 구현하기가 어려울 것입니다.
답변
이 문제가 그리드에서 발생하고 매개 변수가 잘 정의되어 있으므로 최소 스패닝 트리를 생성하여 문제 공간을 체계적으로 제거하여 문제에 접근합니다. 그렇게 할 때 Prim의 알고리즘을 사용하여이 문제에 접근하면 이해가됩니다.
안타깝게도 이제 그리드를 추상화하여 노드와 에지 세트를 생성하는 문제에 직면했습니다.이 게시물의 실제 문제는 nxm 그리드를 {V} 및 {E}로 변환하는 방법입니다.
이 변환 과정은 가능한 조합의 수가 많기 때문에 한눈에 NP-Hard 일 가능성이 높습니다 (모든 수로 비용이 동일하다고 가정). 경로가 겹치는 인스턴스를 처리하려면 가상 섬을 만드는 것을 고려해야 합니다.
이 작업이 완료되면 Prim의 알고리즘을 실행하면 최적의 솔루션에 도달해야합니다.
관찰 가능한 최적의 원칙이 없기 때문에 동적 프로그래밍이 여기서 효과적으로 실행될 수 있다고 생각하지 않습니다. 두 섬 사이의 최소 비용을 찾았다 고해서 반드시 두 섬과 세 번째 섬 사이의 최소 비용을 찾을 수 있다는 의미는 아닙니다. 또는 다른 섬의 하위 집합 (내 정의에 따라 Prim을 통해 MST를 찾는 것)을 찾을 수 있습니다. 연결되었습니다.
그리드를 {V} 및 {E}의 집합으로 변환하는 코드 (의사 또는 기타)를 원하는 경우 개인 메시지를 보내 주시면 구현을 결합하는 방법을 살펴 보겠습니다.
답변
