貪欲法と最小コスト成長ツリー(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())