クリーク問題のアルゴリズム設計
https://stackoverflow.com/questions/509808
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私のアルゴリズム クラスの課題の 1 つは、クリーク問題を解決するための徹底的な検索アルゴリズムを設計することです。つまり、サイズのグラフが与えられると、 n, 、アルゴリズムは、サイズの完全なサブグラフがあるかどうかを判断することになっています。 k. 。答えは得られたと思いますが、改善できる可能性があると思わずにはいられません。私が持っているものは次のとおりです。
バージョン1
入力:配列 A[0,... で表されるグラフn-1]、サイズ k 検索するサブグラフの。
出力:サブグラフが存在する場合は True、存在しない場合は False
アルゴリズム (Python のような疑似コードで):
def clique(A, k):
P = A x A x A //Cartesian product
for tuple in P:
if connected(tuple):
return true
return false
def connected(tuple):
unconnected = tuple
for vertex in tuple:
for test_vertex in unconnected:
if vertex is linked to test_vertex:
remove test_vertex from unconnected
if unconnected is empty:
return true
else:
return false
バージョン2
入力:サイズ n × n の隣接行列、k は検索するサブグラフのサイズ
出力:サイズ k の A 内のすべての完全なサブグラフ。
アルゴリズム (今回は関数/Python 疑似コードで):
//Base case: return all vertices in a list since each
//one is a 1-clique
def clique(A, 1):
S = new list
for i in range(0 to n-1):
add i to S
return S
//Get a tuple representing all the cliques where
//k = k - 1, then find any cliques for k
def clique(A,k):
C = clique(A, k-1)
S = new list
for tuple in C:
for i in range(0 to n-1):
//make sure the ith vertex is linked to each
//vertex in tuple
for j in tuple:
if A[i,j] != 1:
break
//This means that vertex i makes a clique
if j is the last element:
newtuple = (i | tuple) //make a new tuple with i added
add newtuple to S
//Return the list of k-cliques
return S
何かご意見、コメント、提案のある方はいらっしゃいますか?これには、私が見落とした可能性のあるバグや、これを読みやすくする方法が含まれています (私は疑似コードをあまり使用することに慣れていません)。
バージョン3
幸いなことに、課題を提出する前に教授に相談しました。私が書いた疑似コードを彼に見せると、彼は微笑んで、私が書いたものだと言いました。 方法 働き過ぎ。まず、疑似コードを送信する必要がありませんでした。私は問題を理解していることを証明する必要がありました。そして2つ目、彼は だった ブルートフォースソリューションを望んでいます。それで私が提出したものは次のようになりました。
入力:グラフ G = (V,E)、見つけるクリークのサイズ k
出力:クリークが存在する場合は true、存在しない場合は false
アルゴリズム:
- デカルト積 V を求めるk.
- 結果内の各タプルについて、各頂点が互いに接続されているかどうかをテストします。すべて接続されている場合は、true を返して終了します。
- false を返して終了します。
アップデート:第 2 バージョンを追加しました。(私が知っている限り) 派手な動的プログラミングは追加していませんが、これは改善されていると思います。
更新 2:バージョン 2 をさらに読みやすくするために、コメントとドキュメントを追加しました。おそらくこれが今日私が提出するバージョンになるでしょう。みんなの助けに感謝します！複数の回答を受け入れられればよかったのですが、私を最も助けてくれた人の回答を受け入れました。先生の考えを皆さんにお伝えします。
解決
いくつかのコメント:
- すべての k タプル (n^k 個) を考慮する必要はなく、n-choose-k 個の頂点の組み合わせのみを考慮する必要があります。
connected(tuple)正しくないようです。リセットする必要はないですかunconnectedループの中？- 他の人が示唆しているように、これをブルートフォースするより良い方法があります。次の再帰関係を考えてみましょう。最初の k 個の頂点がクリークを形成し、頂点 (k+1) が最初の k 個の頂点のそれぞれに隣接している場合、(k+1) サブグラフはクリークです。これは 2 つの方向に適用できます。
- 1 クリークから始めて、目的のサイズが得られるまでクリークを徐々に拡大していきます。たとえば、m が現在のクリークの最大の頂点である場合、頂点 {m+1, m+2, ..., n-1} を追加して、1 頂点大きいクリークを取得してみます。(これは深さ優先のツリー トラバーサルに似ており、ツリー ノードの子は現在のクリーク内の最大の頂点よりも大きい頂点になります。)
- 目的のサイズのサブグラフから開始し、再帰関係を使用してそれがクリークであるかどうかを確認します。をセットアップします メモ化 途中で結果を保存するテーブル。
- (実装の提案) 隣接行列 (0 ～ 1) を使用してグラフ内のエッジを表します。
- (初期枝刈り) 次数 k 未満の頂点をすべて破棄します。
他のヒント
私はかつてあなたに似た問題であり、グラフ内のすべての極大クリークを見つけるためのアルゴリズムを実装しました。 http://portal.acm.org：私はそれをやった方法は、この論文に基づいていました/citation.cfm?doid=362342.362367 の - 私はその紙から非常に多くの変更が、それは、私がガイドとして非常に有用であることが分かっバックトラッキングソリューションを説明しました。あなたは、そのかかわらず、で取得するサブスクリプションを必要とするだろうが、私はあなたの大学が使用可能なものを持っているだろうと推測ます。
この論文についての一つのことは、しかし、私は本当に彼らがそれがそうでなければあまりにも混乱だから「すでにみなさセット」「設定されていない」と命名しているべきだと考えています。
「頂点の k タプルごとに、クリークの場合は true を返す」アルゴリズムは確実に機能します。ただし、これは総当り的なものであり、おそらくアルゴリズムのコースで求めているものではありません。代わりに、次のことを考慮してください。
- すべての頂点は 1 クリークです。
- 1 クリークごとに、1 クリーク内の頂点に接続するすべての頂点が 2 クリークに寄与します。
- 2 クリークごとに、2 クリーク内の各頂点に接続するすべての頂点が 3 クリークに寄与します。
- ...
- すべての (k-1) クリークについて、(k-1) クリーク内の各頂点に接続するすべての頂点が k クリークに寄与します。
このアイデアは、より良いアプローチにつながる可能性があります。
おそらく、動的なプログラミング技術をしようとします。
それはあなたがちょうど書いたかについてを紹介します質問など何タイピングのものを下に驚くべきことです。この行：
P = A x A x A //Cartesian product
これをする必要があります：
P = A K //デカルト積
あなたはA ^ kで何を意味するのですか？あなたは行列積を取っていますか？そうである場合、隣接行列である（それは、N + 1個の要素のアレイと言った）
setbuilderの表記では、それは次のようになります：
P = {（X0、X1、... XK）| X0∈AとX1∈A ...とXK∈A}
これは、基本的に撮影したk回のちょうどデカルト積です。紙の上で、私は（私はちょうど今、マークダウンを使用していることを行う方法を考え出し）Aの上付き文字対象のKとして、それを書き留めます。
さらに、Aは、隣接関係を考慮せずに、各個々の頂点のちょうど配列である。
