問題タブ [graph-algorithm]

無向グラフ G = (V,E) と一連のノード P が与えられた場合、これらのノードを含むサイクル (最短の長さのサイクルではない) を見つける必要がありますか? このサイクルを見つけるにはどうすればよいですか？

次のグラフについて考えてみます。

ソースノードからターゲットノードへのすべての可能なパスを列挙する方法を見つけようとしています。たとえば、AからEまで、次のパスが考えられます。

ACDEの場合、パスの1つはエッジF3を使用し、もう1つはエッジF5を使用するため、実際には2つのパスがあることに注意してください。また、AとCの間にサイクルがあるため、パスの数が無限になる可能性がありますが、この目的のために、ソースからターゲットへのパスでノードが繰り返されないパスにのみ関心があります。

深さ優先探索（DFS）アルゴリズムを作成しましたが、問題は、2つのノード間に複数のエッジがある場合（上記のエッジF3とF5など）、それを処理する方法がわからないことです。A C D E私のアルゴリズムはパスを戻すだけA C Eで、他のパスは返しません。の場合A B C E、理由は理解できます。Aから開始してCに移動し、それらのパスを構築しますが、DFSがノードBに戻ると、Cに移動しようとしますが、Cはすでにアクセスされているためです。止まります。

とにかく、これを行う方法があるのか​​、それともこれがNP完全であるのか疑問に思いました。

私のDFSをご覧になりたい場合は、以下のコードをご覧ください（マクロの乱用については申し訳ありませんが、コンテストプログラミングで使用しているので、少し習慣になっています）。

出力：

ロングショットですが、汚い仕事を始める前にやってみようかなと思いました。

定義された入力ステーション（頂点）と線（エッジ）、つまり、いくつかの公共交通機関の実際の地図に対して、特定の地図をメトロ地図に図式化するアプリケーションを構築するプロジェクトがあります。私はこの問題についていくつかの調査を行いましたが、これは3-SAT問題と同等のNP完全問題です。そのようなマップを生成する方法についてもいくつかの理論的なアイデアがありますが、それらは十分に詳細ではありません。

私が探しているのは、この問題の他の既存の解決策、ある種の擬似コード、（ほぼ）他のプログラミング言語の実際のコードなど、アルゴリズム自体の作業に費やす時間を短縮するものです。 、その見返りに、アプリケーションの他の側面に取り組むためのより多くの時間を与えてくれます。

誰かが私を助けることができる何かを見たことがあれば、私はそれをとても感謝します。

次のことを行うアルゴリズムを設計しようとしています。

入力：

プロパティのセットにマップされたキーのセット (合計 n) があります。プロパティには、各プロパティの重みとプロパティの値が含まれています。

出力：

プロパティのセットとそれぞれの重みと値に基づいて、修飾されたキーのセット (合計 k) を特定します。

さらに、勝者を選択するサイクルごとにデータを変更して、次のサイクルで選ばれなかった人の可能性が上がるようにする必要があります (一方、勝者の可能性は、その人がまったく新しい人であるかのようになります)。システム）。

うまくいけば、当面の問題は明確です。基本的に、プロパティの値とそれぞれの重みによって、どのキーが勝つ可能性が高いかが決まり (値が大きく、重みが大きいほど、そのキーが勝つ可能性が高くなります)、最終的には全員を選択することになります。

これを行う方法についてのご意見をいただければ幸いです。

ありがとう！- アジーム

フローチャートを表すデータがあります。(一連の Jira ステータスと他のステータスへの遷移。)

また、OpenOffice Draw ドキュメントの A4 ページに各フローチャート項目を配置する大雑把な方法もあります。（ただし、より良い提案は歓迎します。）

ただし、特にフローチャートを数回再生成する必要がある場合があるため、ボックスの行を出力して手動で再配置する必要はありません。

これはよくある問題のように思えるので、いくつかの項目 (およびそれらの間のリンク) を分析し、それらを適切な位置に配置する適切な仕事を行う既存のアルゴリズム/手法が必要です。

これを行う最善の方法について何か提案はありますか?

重み付けされていない接続グラフがあります。特定のノード セットを確実に含み、エクストラをできるだけ少なくした、接続されたサブグラフを見つけたいと考えています。これはどのように達成できますか？

念のため、より正確な言葉を使用して質問を言い直します。G(V,E) を無向、無向、連結グラフとします。N を V の部分集合とします。N が V' の部分集合となるような G(V,E) の最小連結部分グラフ G'(V',E') を見つける最良の方法は何ですか?

近似は問題ありません。

たとえば、A+B=C C+D=E E+F=G のように、各ノードに変更が加えられると、関連するノードが再計算されます。下の画像は、私がやろうとしていることの単純な例です。

詳細説明 各オブジェクトの構造は同一です。入力は価格であり、価格が変化するたびに下流の価格にカスケード効果があります。上記の例では、A+B=C は 5+6=11 になります。等

変更は常に (おそらく毎秒) 行われます。各値が変更されると、通知を受ける必要があります (イベントが発生します)。

無向連結グラフ G が与えられたとき、直径が最小の全域木を見つけます。

偶数の頂点を持つ完全な重み付きグラフで、次のプロパティを持つエッジのセットを見つけるための効率的なアルゴリズムはありますか？

• セットには、他の可能な基準を満たしたセットの最小、最大のエッジウェイトがあります
• すべての頂点は、セット内の1つのエッジに接続されています

すべての重みは正です

dブルートフォースよりも優れたものは考えられませんが、NP困難とは認識していません。

さまざまな一般的な検索アルゴリズムが互いにどのように関連しているかをよりよく理解したいと思います。階層図や簡潔なテキストによる説明など、リソースを知っている人はいますか?

私が意味することの小さな例は次のとおりです。

等

ありがとう！