接続されたリングを完全に切断する最小数を決定するにはどうすればよいですか？

Question

checkio - Break Ringsの質問ですが、可能なすべてのブレーク方法をテストして最小限のものを見つけることで、O（n * 2^n）の複雑さで悪い方法しか使用できません。

問題： 鍛冶屋は見習いの仕事をして、リングを選択するように指示しました。見習いは技術にまだ熟練しておらず、その結果、いくつかの（正直に言うと、大部分の）リングがつながっていました。今すぐ彼はあなたの助けを求めてリングを分離し、最大限の数のリングを可能にするのに十分なリングを解放する方法を決める。

すべてのリングに番号が付けられ、どのリングが接続されているかがわかります。この情報は一連の集合として与えられる。各セットは、接続されたリングを記述する。たとえば、{1,2}は1番目と2番目のリングが接続されていることを示します。別々のリングを最大限に利用するためには、何本のリングを壊す必要があるかを数えてください。各リングは1からNの範囲で番号が付けられており、Nはリングの総量です。あなたが接続を見ることができます上の画像で

https://static.checkio.org/media/task/media/0d98b24304034e2e9017ba00fc51f6e3/example-rings.svg

例リング

（申し訳ありませんが、私は写真にマックでSVGを変更する方法を知りません。）

：（ {1,2}、{2,3}、{3,4}、{4,5}、{4,6}、{6,5}）ここでの最適な解決策は、3つのリングを分割し、3つの完全なリングと別々のリングを作ることです。その結果は3です。

入力：整数を含むセットのタプルとしての接続されたリングに関する情報。

出力：整数で折れるリングの数。それは実用的ではないので、テストケースが小さい場合にのみ動作します

は

from functools import reduce 
import copy 

def break_rings(rings): 
    max_ring = max(reduce(set.union,rings)) 
    rings = list(rings) 
    possible_set = [list(bin(i)[2:].rjust(max_ring,'0')) for i in range(2**max_ring)] 
    possible_set = [list(map(int,j)) for j in possible_set] 
    min_result = max_ring 
    for test_case in possible_set: 
     tmp = copy.copy(rings) 
     tmp2 = copy.copy(rings) 
     for index, value in enumerate(test_case): 
      if value: 
       for set_connect in tmp: 
        if index+1 in set_connect and set_connect in tmp2: 
         tmp2.remove(set_connect) 
     if not tmp2: 
      min_result = min(sum(test_case),min_result) 
    return min_result 

だから、私はそれがおよそアルゴリズムについて考えなければならないと思います（私はそれもテストに合格することができないと思います）グラフ、しかし私はちょうど私が直面している問題の種類を知らない。

アルゴリズムを改善できますか？

ありがとうございます！

Answer 1

これは、vertex coverというグラフの問題の一種と考えることができます。

各リングの頂点と各接続のエッジ、つまり結合されたリングの各ペアを持つグラフを描画します。

あなたの仕事は最小限の破損でリングを切断することです。いずれかの端のリングが壊れていると、接続が切断されます。つまり、すべての接続（エッジ）が選択したリングに1つずつ入るように、リング（頂点）のセットを選択する必要があります。

これはまさに頂点カバーの問題です。

頂点カバーはNP完全であるため、現在知られている非指数アルゴリズムはありません。

不正なケースを先に拒否することで、アルゴリズムの速度を向上させることをお勧めします。たとえば、各リングについて、破棄するかどうかを決定するバックトラッキングアルゴリズムを使用します。あなたがそれを壊さないことを選択した場合、あなたはすぐに他の多くのリングが壊れていなければならないと結論づけることができます。