貪欲法と最小コスト成長ツリー(MST)
15796 ワード
貪欲法
このGreedyアルゴリズムと呼ばれる方法は,最終的な答えを見つけるために,各段階で1つの答えを選択し,これらの答えを集合させ,最終的に最適な答えを選択することである.
しかし、最適化の問題では
しかし,これらの貪欲な方法も比較的容易に設計され,しかも数が非常に大きいとDPのような方法は使用できない.この時、あれこれ考えて答えを見つけることができます.
しかし,最適化問題では正確性を証明しなければならない.
最小コストの拡張ツリーMST
問題の定義
質問:指定した図面から最小費用増加ツリーを求める
厳密な定義:
指定されたグラフィック:𝐺 = (𝑉, 𝐸) Gは無方向図であり,すべての頂点に接続された重みがある.
拡張ツリー(生成ツリー):𝐺のローカルグラフィックT=(𝑉, 𝐹), FはEに含まれる.
•グラフ𝐺すべての頂点を接続するツリー:𝑛 − 1
最小コスト成長ツリー(MST)=すべての成長ツリーTにおける重みの和の最小成長ツリー
Brute-Force
Greedy Approach
ステップ1:初期化
解答の集合を公の集合とする
ステップ2(選択):解答のセットに最適な要素を含めます.
コード#コード#
def prim(W):
n = len(W) - 1
F = []
nearest = [-1] * (n + 1) # 근접한 노드 보여주기위함
distance = [-1] * (n + 1) # 거리
for i in range(2, n + 1): # 1은 시작노드라서 빼고 2부터 시작
nearest[i] = 1
distance[i] = W[1][i]
print_nd(F, nearest, distance)
for _ in range(n - 1):
minValue = INF
for i in range(2, n + 1):
if (0 <= distance[i] < minValue): # 거리가 min 보다 작고 0보단 크면
minValue = distance[i] # min 변경
vnear = i # 최적의 노드값 i로 저장
edge = (nearest[vnear], vnear, W[nearest[vnear]][vnear]) # 엣지 정보 저정 (출발 노드, 도착, 노드 거릭)
F.append(edge) # add edge to F
distance[vnear] = -1 # 방문했으니 -1로 돌려버림
for i in range(2, n + 1):
if (distance[i] > W[i][vnear]): # 만약 거리가 새로운 노드간의 거리보다 크면
distance[i] = W[i][vnear] # 새로운 거리로 교체하고
nearest[i] = vnear # 연결노드 변경
print_nd(F, nearest, distance)
return F
def cost(F, W):
total = 0
for e in F:
total += W[e[0]][e[1]]
return total
def print_nd(F, nearest, distance):
print('F = ', end='')
print(F)
print(' nearest: ', end='')
print(nearest)
print(' distance: ', end='')
print(distance)
INF = 999
W = [
[-1, -1, -1, -1, -1],
[-1, 0, 1, 3, INF, INF],
[-1, 1, 0, 3, 6, INF],
[-1, 3, 3, 0, 4, 2],
[-1, INF, 6, 4, 0, 5],
[-1, INF, INF, 2, 5, 0],
]
F = prim(W)
for i in range(len(F)):
print(F[i])
print("Minimum Cost is ", cost(F, W))
m, n = map(int, input().split())
Reference
この問題について(貪欲法と最小コスト成長ツリー(MST)), 我々は、より多くの情報をここで見つけました https://velog.io/@blacklandbird/탐욕법과-최소비용신장트리MSTテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol