私はredditでこの質問をしましたが、まだ解決策に収束していません。検索の多くでStackOverflowが表示されるので、これを試してみることにしました。これが私の問題の簡単な定式化です：
重み付き無向グラフG（V、E、w）とGの頂点Sのサブセットが与えられた場合、Sにまたがる最小/最大重みツリーを見つけます。頂点の追加は許可されていません。基本モデルの拡張は、重みが0のエッジと、除外する必要のある頂点を追加することです。これは、ここで尋ねられる質問に似ているようです。
エッジが取ることができる値についてのより多くの洞察もあります。各エッジは実際には相関確率であり、いくつかの方法でエンコードできるため、グラフに尋ねたい主な質問は次のとおりです。
- 接続する必要のあるk個の頂点がある場合、それらを接続する上位Xの最小/最大スパニングツリーは何ですか？また、それらはどの頂点を通過しますか？私が理解しているように、これは、k個の頂点すべてを接続する可能性が最も高いグラフを尋ねるのと同じ質問です。
- もっと曖昧になって、ノードをクラスター化する論理的な方法はありますか？
実装に関しては、Boostライブラリをインストールしており、フレームワークがこの問題に対応できるようになったら、マルチスレッド化の方法（適切な場合）、使用するグラフの種類、および保存/キャッシュの方法を処理できます。頂点とエッジの数が非常に多くなるため、データ。
更新 私が解決しようとしている問題を見ると、NP完全であることが理にかなっています。私が解決しようとしている現実の問題には、医学的診断が含まれます。特に、医学界が特定のアイデアを念頭に置いて問題に取り組んでいる場合、彼らは一歩下がって、どのようにしてそこにたどり着いたかを再考する必要があります。私が設計しようとしているプログラムに欲しいのは、次のとおりです。
- いくつかの条件、テスト、症状、年齢、性別、季節、確定診断、タイムラインを考えると、それらをどのように関連付けることができますか？どの細胞/組織/器官/システムが触れられていますか？それらは関連していますか？
- 条件/症状が属することができる定義済みのグループに加えて、条件/症状を論理的にグループ化する方法はありますか？
例 インフルエンザのような症状、赤目、初期の肺炎、および糖尿病の兆候のいくつか。すべての症状を関連付ける方法はありますか？判別を容易にするために実行できるテストはありますか？どのようなシステムが関係していますか？
これを1つまたは複数のグラフにマッピングし、さまざまな症状/状態間の相関関係として確率を使用するのは自然なことのように思われました。