12

私のアルゴリズム クラスの課題の 1 つは、クリーク問題を解決するための徹底的な検索アルゴリズムを設計することです。つまり、サイズnのグラフが与えられた場合、アルゴリズムは、サイズkの完全なサブグラフがあるかどうかを判断することになっています。答えは出たと思いますが、改善できると思わずにはいられません。ここに私が持っているものがあります:

バージョン 1

input : 配列 A[0,... n -1] で表されるグラフ、検索するサブグラフのサイズk 。

output : サブグラフが存在する場合は 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

input : サイズ n × n の隣接行列、k は検索する部分グラフのサイズ

output : サイズ 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

幸いなことに、課題を提出する前に教授に相談しました。私が書いた疑似コードを彼に見せたとき、彼は微笑んで、私があまりにも多くの仕事をしたと言った. 1 つには、疑似コードを提出する必要がありませんでした。問題を理解していることを証明する必要がありました。2 つ目は、彼は力ずくで解決することを望んでいたことです。それで、私が提出したものは次のようになりました。

入力: グラフ G = (V,E)、kを見つけるためのクリークのサイズ

output : クリークが存在する場合は true、そうでない場合は false

アルゴリズム:

  1. デカルト積 V kを求めます。
  2. 結果のタプルごとに、各頂点が互いに接続されているかどうかをテストします。すべて接続されている場合は、true を返して終了します。
  3. false を返して終了します。

更新: 2 番目のバージョンを追加しました。(私が知っている)派手な動的プログラミングを追加していませんが、これは良くなっていると思います。

更新 2 : バージョン 2 をより読みやすくするために、いくつかのコメントとドキュメントを追加しました。これはおそらく今日私が提出するバージョンです。みんなの助けに感謝します！複数の回答を受け入れることができればいいのですが、私を最も助けてくれた人の回答を受け入れました. 先生の考えをお伝えします。

4

4 に答える 4

8

いくつかのコメント：

  • すべてのkタプル（それらのn ^ k）ではなく、頂点のn-choose-kの組み合わせのみを考慮する必要があります。
  • connected(tuple)正しく見えません。unconnectedループ内でリセットする必要はありませんか？
  • 他の人が示唆しているように、これをブルートフォースするより良い方法があります。次の漸化式を考えてみましょう。最初のk個の頂点がクリークを形成し、頂点（k + 1）が最初のk個の頂点のそれぞれに隣接している場合、サブグラフはクリークです。これは2つの方向に適用できます。
    • 1クリークから始めて、希望のサイズになるまでクリークを徐々に広げていきます。たとえば、mが現在のクリークで最大の頂点である場合は、頂点{m + 1、m + 2、...、n-1}を追加して、1頂点大きいクリークを取得してみてください。（これは、深さ優先のツリートラバーサルに似ています。ツリーノードの子は、現在のクリークの最大の頂点よりも大きい頂点です。）
    • 目的のサイズのサブグラフから始めて、漸化式を使用して、それがクリークであるかどうかを確認します。途中で結果を保存するためのメモ化テーブルを設定します。
  • （実装の提案）隣接行列（0-1）を使用して、グラフのエッジを表します。
  • （最初の剪定）次数がk未満のすべての頂点を破棄します。
于 2009-02-04T02:31:31.647 に答える
2

私はかつて、グラフ内のすべての最大クリークを見つけるアルゴリズムを実装しました。これは、あなたと同様の問題です。私がそれを行った方法は、この論文に基づいていました：http: //portal.acm.org/citation.cfm ?doid =362342.362367-それは私がガイドとして非常に役立つと思ったバックトラッキングソリューションを説明しましたが、私はかなり変更しましたその紙。それを取得するにはサブスクリプションが必要ですが、あなたの大学ではサブスクリプションを利用できると思います。

しかし、その論文についての1つのことは、他の方法では混乱しすぎるため、「設定されていない」を「すでに設定されている」と名付けるべきだったと思います。

于 2009-02-04T02:39:54.173 に答える
2

「頂点のkタプルごとに、それがクリークの場合はtrueを返す」というアルゴリズムは確実に機能します。ただし、これは総当たりであり、おそらくアルゴリズムのコースが探しているものではありません。代わりに、次のことを考慮してください。

  1. すべての頂点は 1 クリークです。
  2. 1-クリークごとに、1-クリークの頂点に接続するすべての頂点が 2-クリークに寄与します。
  3. 2 クリークごとに、2 クリークの各頂点に接続するすべての頂点が 3 クリークに寄与します。
  4. ...
  5. (k-1) クリークごとに、(k-1) クリーク内の各頂点に接続するすべての頂点が k クリークに寄与します。

このアイデアは、より良いアプローチにつながる可能性があります。

于 2009-02-04T02:48:47.430 に答える
0

質問として入力すると、今書いた内容について何が表示されるかは驚くべきことです。この行：

P = A x A x A  //Cartesian product

これである必要があります：

P = A k //デカルト積

A^k とはどういう意味ですか? マトリックス製品を服用していますか？もしそうなら、Aは隣接行列ですか（あなたはそれがn + 1要素の配列だと言いました）？

setbuilder 表記法では、次のようになります。

P = {(x0, x1, ... xk) | x0 ∈ A かつ x1 ∈ A ... かつ xk ∈ A}

これは基本的に、A を k 回とった単なるデカルト積です。紙の上では、k は A の上付き文字であると書き留めました (マークダウンを使用してその方法を理解したところです)。

さらに、A は、隣接性に関係なく、個々の頂点の単なる配列です。

于 2009-02-04T02:03:57.490 に答える