問題タブ [clique]

ウェブ上のどこでクリークを見つけるためのブロン・ケルボッシュアルゴリズムの説明を見つけることができるか、またはここでそれがどのように機能するかを説明できますか?

「アルゴリズム 457: 無向グラフのすべてのクリークを見つける」という本に掲載されていることは知っていますが、アルゴリズムを説明する無料のソースが見つかりません。

アルゴリズムのソース コードは必要ありません。アルゴリズムの仕組みの説明が必要です。

グラフは、任意の頂点が残りの頂点と接続されているグラフのサブグラフです。

k-問題では、入力は無向グラフと数値 k であり、出力は、存在する場合はサイズ k の clof (または、サイズ k のすべての cl) です。

Androidインターフェースのネットワークインターフェースは、/ sys / class /net/のファイルシステムにディレクトリとしてリストされています。

ほとんどのAndroidデバイスでは、gprsトラフィックのネットワークインターフェイスはrmnet0と呼ばれ、Wi-Fiの場合は通常eth0またはtiwlan0です。

Motorola CLIQ XTのセルインターフェイスはrmnet0だと思いますが、これを確認して、Wi-Fiインターフェイスの名前を知ってもらいたいと思います。

また、このモデルのデバイスIDを知っておくとよいでしょう。これは、 JavaSDKでandroid.os.Build.DEVICEとして使用できる値です。（たとえば、T-Mobile G1は夢を使用し、Samsung GalaxyはGT-I7500を使用し、Motorolda Droidは穴を使用します。）

約100個の頂点を持つグラフのクリーク数のみ（実際にはクリークを検出せずに）を検出する高速アルゴリズムを知りたいです。

私は次の問題を解決しようとしています。 http://uva.onlinejudge.org/external/1/193.html

約 100 個の頂点を持つ完全なグラフ (少なくとも 1 つの弦を持つ奇数サイクルを持つグラフ) で最大のクリークのサイズを見つけるための高速アルゴリズム ??

これは完全なグラフであり、多項式時間の解があるはずなので、ブルートフォースよりも簡単な方法はありますか。しかし、アルゴリズムを見つけることができません。

貪欲な色付けは、すべての完全なグラフで最適な色付けを行いますか??

特定の問題に遭遇し、そのためのアルゴリズムを探していました。解決すべき問題は以下のとおりです。

以下のような組み合わせがあるとしましょう

1 - 3 - 5

1 - 4 - 5

1 - 8 - 5

2 - 4 - 5

3 - 4 - 5

2 - 4 - 7

これらの組み合わせは、特定のセットから生成されました。この特定のケースでは、

{1},{3,4,8},{5}

{2,3}、{4}、{5}

{2}、{4}、{7}

私がやりたいのは、これらの組み合わせからセットを再作成することです。これらの組み合わせには、複数のソリューションがあることを知っています。

最初の解決策

{1}、{3、4、8}、{5}

{2, 3}, {4}, {5}

{2}、{4}、{7}

2番目のソリューション

{1}、{3、8}、{5}

{1, 2, 3}, {4}, {5}

{2}、{4}、{7}

3番目のソリューション

{1}、{3、4、8}、{5}

{3}、{4}、{5}

{2}、{4}、{5、7}

しかし、最終的な (最適な) 解決策は、可能な限りセット数の少ないものか、セット数に関してすべてが同等である場合のランダムなものです。

そのような問題のアルゴリズムは存在しますか? この種の問題を扱ってきた人が私にヒントを与えることができれば幸いです。

編集:私が探しているのは、n-ary積(Nのデカルト積)の分解であるように見えます

編集: このトピックについてさらに調査した結果、この問題は「グラフ理論」で「最小クリークカバー」問題として知られていることがわかりました

よろしく、バズ

要するに、私の素朴なコード (Ruby) は次のようになります。

そして私のBron Kerboschの実装：

また、ピボットと縮退順序付けを実装しました。これにより、bron_kerbosch の実行時間が短縮されましたが、最初のソリューションを追い越すには十分ではありませんでした。これが事実であるというのは間違っているようです。私が見逃しているアルゴリズムの洞察は何ですか？完全に機能するコードを確認する必要がある場合は、ここに詳細が記載された記事があります。私はこれを疑似ランダム セットで最大 100 万個程度のサイズのエッジでテストしました。

ピボットを使用した BK クリーク検出に関するウィキペディアの疑似コード:

P union X が空であるとどうなるかは不明です。u は定義されていないので、関数は N(u) を空集合として続行しますか (つまり、P の頂点 v ごとに続行します)、それとも呼び出し元に戻りますか?

この問題があり、助けが必要です。これが私のコードです:

最初にグラフを検索してクリークを見つけ、その後長さ 3 のクリークかどうかをテストし、それが true の場合は 1 つのエッジを削除したいので、complete-graph(3) を削除できます。どうやってやるの？

ありがとう

23 点が 6 次元に広がっているデータセットがある場合、この演習の最初の部分では次のことを行う必要があります。

• CLIQUE アルゴリズムの最初のステップ (すべての高密度セルの検出) を計算します。ドメイン 0..100 の次元ごとに 3 つの等間隔を使用し、セルに少なくとも 5 つのオブジェクトが含まれている場合、そのセルは密集していると見なします。

これは些細なことであり、単純に数える問題です。ただし、次の部分では次のことが求められます。

• Preprocess、Classify、Cluster、または Associate のタブで提供される Weka の関数のみを使用して、上記の CLIQUE の結果を計算する方法を特定します。 ヒント : 必要なタブは 2 つだけです。

私はこれを1時間以上試していますが、ここで解決策に近づくことができないようです. 誰かがヒント、またはwekaについてもう少し洞察を与える便利なチュートリアルを持っていれば、それは非常にありがたいです!