問題タブ [clique-problem]

CLIQUE 問題 -- グラフ内の最大クリークを見つける問題は NP 完全です。つまりCLIQUEは

a.) NP および b.) 多項式時間で CLIQUE に還元される NP 完全問題 (1 つは 3-SAT) です。

上記の (b) の部分は問題ありません。すべてのリソースで十分に説明されています。パート (a) については、私が知っていることから、次のことが必要です: 特定のソリューション インスタンスが与えられた場合、そのソリューションがこの問題に対する答えであることを多項式時間で検証できることを示す必要があります。したがって、たとえば、特定のグラフとそのサブグラフが与えられた場合、そのサブグラフがそのグラフで最大サイズのクリークであるかどうかを確認できるはずです。

私がこれまでに読んだリソースでは、このパート (a) を「簡単、簡単など」または「指定されたサブグラフがクリークかどうかを O(n^2) 時間で示すことができる」と表現しています。ただし、ここでの検証はクリークであるかどうかだけではなく、グラフの最大のクリークであるかどうかです。これは多項式時間でどのように決定できますか?

ここで何が欠けていますか？

レイアウトを保存し、レイアウトを新しいアクティビティのレイアウトとして設定する必要があるお気に入りのボタンにまだ直面しています..問題は、保存したレイアウトを開く必要があるアクティビティがそれを行わないことですが、私はそうしません理由がわかりません..これが私のコードです：

レイアウトを保存するためのコードは次のとおりです。

どうもありがとう ！

LE: 保存されたレイアウトを開くアクティビティの最初のコードを編集しましたが、ボタンはまだ黒いアクティビティを開きます..

以下に示すアルゴリズムを使用して最大クリークの問題を解決しようとしていますが、これまでのところ、失敗するケースを見つけることができませんでした。
アルゴリズム:
特定のグラフについて、各ノードには 1 から N までの番号が付けられます。
1. ノードを永続ノードと見なし、各ノードがこの永続ノードに接続されるようにノードのセットを形成します (セットには永続ノードも含まれます)
2 。 . 次に、形成されたセット内のすべてのノードと、セット内に存在するノード間にあるエッジのみを含むように、元のグラフのサブグラフを形成します。
3. 各ノードの次数を見つけます。
4. すべてのノードの次数が同じ場合、クリークがあります。
5. それ以外の場合は、このサブグラフから最小次数ノードを削除し、手順 3 から繰り返します。
6. グラフ内のすべてのノードについて、手順 1 ～ 5 を繰り返します。

このアルゴリズムの欠陥を指摘できる人はいますか?
ここに私のコード http://pastebin.com/tN149P9mがあります。

解決しようとしている問題があります。クリークを受け取り、そのクリークを含む最大のクリークを返すメソッドを実装したいと考えています。私が取り組んでいる方法は再帰的であり、バックトラッキングを使用して、クリークの定義に従ってソリューションを受け入れたり拒否したりします。私の問題は、メソッドにパラメーターを 1 つだけ渡したいので、Bron-Kerbosch アルゴリズムを使用したくないことです。これが私がやったことの疑似コードです：

再帰を破る条件を選択する方法についてのアイデアを手伝ってもらえますか? 次の候補の値をメソッドのパラメータに渡さずに次のループまで保持する方法がわかりません!

~17000 の加重頂点と ~75% の密度を持つグラフで既知の頂点数を持つ最大クリークを (およそ) 見つけることができるソフトウェアまたはアルゴリズムの説明はありますか? Cliquer を使用しようとしましたが、遅すぎます (結果を得るのに数日かかりました)。

念のため、私の問題について少し-それはスケジューリングの問題です.18のタイムスロットがあり、それぞれが異なる数の選択肢で満たされる可能性があります. 各変数は、1 つのスロットの 1 つの選択肢を表します。したがって、1 つのスロットのすべての代替は相互に排他的であり、異なるスロットの一部の代替は互換性がありません。2 つの代替案に互換性がある場合、それらの間に優位性があります。重みは、代替の値を表します。

この問題にしばらく苦労した後、ここでアドバイスを得たいと思っています。有意性に基づいてペアごとのグループ化ラベルを決定する自動化された方法を誰かが知っているかどうか疑問に思っています。この質問は、有意性検定とは無関係です (たとえば、パラメトリックの場合は Tukey、ノンパラメトリックの場合は Mann-Whitney) - これらのペアごとの比較を考えると、いくつかの箱ひげ図タイプの図は、これらのグループ化を下付き文字で表すことがよくあります。

私はこの例を手作業で作成しましたが、これは非常に面倒です。アルゴリズムでのラベル付けの順序は、各グループのレベル数に基づいている必要があると思います。たとえば、他のすべてのレベルとは大幅に異なる単一レベルを含むグループを最初に指定し、次に 2 つのレベルを含むグループ、次に 3 を指定する必要があります。など、新しいグループ化が新しい必要なグループ化を追加し、違反していないことを常にチェックしています。

以下の例で難しいのは、レベル 1 は 3 と 5 とグループ化する必要があるが、3 と 5 はグループ化しない (つまり、ラベルを共有する) ことをアルゴリズムに認識させることです。

コード例:

繰り返しなしで互いに隣接している画像内のすべての（順序付けられていない）ピクセルのペアをループする必要があります。私は 8 点近傍を使用しています。例えば：

ピクセルfの近傍は、その周囲の 3x3 の正方形にあります。したがって、たとえばgはfと 2 ポイント クリークを形成します。画像のすべての行と列をループすると、このクリークは 2 回カウントされます。1 回目はfが中央のピクセルのとき、もう 1 回はgが中央のピクセルのときです。残りのクリークでも同様の非効率性が発生します。

だから私がやりたいのは、各ピクセルではなく、すべてのクリークをループすることです。私がグラフ理論に精通していれば、同様の質問に対して既に与えられている回答のいくつかで十分だと思いますが、私はそうではないので、素人の言葉で効率的なアルゴリズムであなたが与えることができる助けを本当に感謝します. 前もって感謝します！

クリーク問題を一定時間で解決するブラック ボックスが与えられたとします。

ブラック ボックスに境界 k を持つ無向グラフ G を与えると、グラフ G が少なくとも k 個の頂点を持つクリークを持っていることを「はい」または「いいえ」のいずれかで出力します。

多項式時間で最大クリークの頂点を見つけるために、このブラック ボックスをどのように使用しますか?