貪欲法と最小コスト成長ツリー(MST)

貪欲法

このGreedyアルゴリズムと呼ばれる方法は,最終的な答えを見つけるために,各段階で1つの答えを選択し,これらの答えを集合させ,最終的に最適な答えを選択することである.
しかし、最適化の問題では

が最適ですが、

答えが最良であることは保証できません

このような問題が発生する可能性があります.
しかし,これらの貪欲な方法も比較的容易に設計され,しかも数が非常に大きいとDPのような方法は使用できない.この時、あれこれ考えて答えを見つけることができます.
しかし,最適化問題では正確性を証明しなければならない.

については、貪欲法を説明する文章に詳しく書く.

最小コストの拡張ツリーMST

問題の定義

質問:指定した図面から最小費用増加ツリーを求める
厳密な定義:

指定されたグラフィック:𝐺 = (𝑉, 𝐸) Gは無方向図であり,すべての頂点に接続された重みがある.

拡張ツリー(生成ツリー):𝐺のローカルグラフィックT=(𝑉, 𝐹), FはEに含まれる.
•グラフ𝐺すべての頂点を接続するツリー:𝑛 − 1

最小コスト成長ツリー(MST)=すべての成長ツリーTにおける重みの和の最小成長ツリー

Brute-Force

すべての伸長ツリーを検索し、重み付けと最小の

を選択します.

の木を成長させる方法を探しています

本の幹線数がn-1の連結木(無環)である場合、幹線

を1本ずつ削除する.

Greedy Approach

ステップ1:初期化
解答の集合を公の集合とする

幹線集合Eの部分集合Fは空集合

である.
ステップ2(選択):解答のセットに最適な要素を含めます.

𝐸最適な幹線を抽出𝐹取り込む

最適な

の方法を選択しますか?フリムvsクルースカル

手順3(チェック):回答セットが最終的な場合は、手順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())