問題タブ [graph-algorithm]

無向および連結グラフでは、各エッジに色（赤、緑、または青）があります。
有効なパスは、各色のエッジが少なくとも1つあるパスです。
問題は、最短の有効なパスを見つける方法、またはパスが存在しないと判断する方法です。

BFSを使おうとしましたが、解決策がわかりませんでした。
始める方法について何かアイデアはありますか？

以下のプロパティを満たすすべての可能な DFA から選択された決定論的有限オートマトン (DFA) を生成する必要があります。DFA は一様分布で選択する必要があります。

DFA には、次の 4 つのプロパティが必要です。

• DFA には N 個のノードがあります。
• 各ノードには 2 つの発信トランジションがあります。
• 各ノードは、他のすべてのノードから到達可能です。
• DFA は、すべての可能性から完全に均一なランダム性で選択されます。

ノードや遷移のラベル付けは考えていません。2 つの DFA に同じラベルのない有向グラフがある場合、それらは同じと見なされます。

動作しない 3 つのアルゴリズムは次のとおりです。

アルゴリズム #1

1. A と呼ばれる N 個のノードのセットから始めます。
2. A からノードを選択し、セット B に入れます。

3. セットAにノードが残っている間

   /li>

4. B の各ノード n に対して

   /li>

アルゴリズム #2

1. N 個の頂点とアークのない有向グラフから始めます。
2. N 個の頂点のランダム順列を生成してランダムなハミルトニアン サイクルを生成し、それをグラフに追加します。
3. 頂点ごとに、ランダムに選択された頂点に 1 つの出力アークを追加します。

アルゴリズム #3

1. N 個の頂点とアークのない有向グラフから始めます。
2. N から 2N の間の長さのランダム有向サイクルを生成し、グラフに追加します。
3. 頂点ごとに、ランダムに選択された頂点に 1 つの出力アークを追加します。

アルゴリズム #2 に基づいてアルゴリズム #3 を作成しましたが、ランダムな有向サイクルを選択して均一な分布を作成する方法がわかりません。それが可能かどうかさえわかりません。

どんな助けでも大歓迎です。

有向グラフで負の重みサイクルを見つけるアルゴリズムについて考えていました。問題は次のとおりです。グラフG（V、E）があり、負の重みを持つサイクルを見つけるための効率的なアルゴリズムを見つける必要があります。このPDFドキュメントのアルゴリズムを理解しています

簡単に言うと、このアルゴリズムは、| V | -1回反復して緩和を行うことにより、ベルマンフォードアルゴリズムを適用しています。その後、さらにリラックスできるエッジがあるかどうかをチェックし、負の重みサイクルが存在し、親ポインターによってそれをさかのぼることができ、すべてがうまくいくと、負の重みサイクルが見つかります。

ただし、グラフ上で深さ優先探索（DFS）を使用して、移動した距離のこれまでの合計を追跡する別のアルゴリズムを考えていました。最初はすべてのノードを白でマークし、私がいるときは灰色にします。パスを検索し、終了時に黒でマークします。これにより、訪問したノードが見つかり、それが（パス内で）灰色であり、深さによってすでに終了している黒ではない場合にのみ、サイクルが見つかることがわかります。 -最初の検索なので、私のアルゴリズムでは、すでにアクセスした灰色のノードに到達した場合、更新内容（新しい距離）を確認し、以前よりも低い場合は、負の重みがあることがわかりますサイクルし、それをさかのぼることができます。

私のアルゴリズムは間違っていますか？もしそうなら、あなたは反例を見つけることができますか？そうでない場合は、私がそれを証明するのを手伝ってくれませんか？

ありがとうございました

ツリーの 2 つのフラットな表現があります。

ツリーは次のとおりです。

ご覧のとおり、状態には複数のイベントと状態を含めることができます。名前は気にしないでください。関連性はありません。要素のタイプを示すだけです。

最初のリストはツリーの深さ優先のボトムアップ トラバーサルであり、2 番目のリストは深さ優先のトップダウン トラバーサルであると思います。

2 つのフラット リストからツリーを再作成する必要があります。つまり、各状態またはイベントをその親状態 (または最上位) に割り当てます。これは可能ですか？もしそうなら、どのように？

私のコードで基本的に起こることは次のとおりです。

Traverse* 機能を変更できません。

私は２軒の家を借りる必要があります。できるだけ近づけてほしい。約300戸の賃貸住宅があります。Google Maps Directions APIを使用して、利用可能な2つの家の間の歩行距離を計算し、リストを並べ替えて、近い2つの家を選択できるようにしたいと思います。

Googleが1日あたり2,500クエリの理論上の制限を設定していることを除いて、すべてがうまく機能します（実際には、制限ははるかに低く、1日あたりわずか250です）。300 ² /2-300 = 44,700のクエリを実行する必要があるため、この制限では明らかに不十分です。

これは1回限りのことですが、Google Maps APIで必要なことをどのように達成できるかについてのヒントはありますか？どういうわけか、制限が1つのインスタンスにのみ影響するように、分散されたプログラムを実行できますか？Google App Engineは役に立ちますか？

アルゴリズムを改善するためのアドバイスも歓迎します。2つの家が遠く離れていて、別の家が1つに近い場合は、おそらく遠く離れているため、残りの家で3番目の家をチェックする必要がないことを意味します。また、正確な距離ではなく、アルゴリズムの質的な性質に関心があるため、クエリが少なくなるような簡単な近似ができるかもしれません。

ありがとう、

私はホームタスクを持っています：

平面グラフの埋め込みのビジュアライザーを作成する（または、このプロセスの正しい単語がわからない）。

平面グラフは平面グラフと同形であり、平面グラフはエッジが交差しない平面上に描かれたグラフです。

これを行うにはアルゴリズムが必要です。ロシア語の記事が1つあり、「ガンマアルゴリズム」という名前のアルゴリズムがそこに記述されていますが、さらに情報を見つけたいのですが、「ガンマアルゴリズム」については何も見つかりませんでした。英語、それは別の名前を持っているようです）、または英語の他のアルゴリズムについても。

誰かがアルゴリズムの名前とそれらの説明へのリンクを提案できますか？

私の英語が下手ならごめんなさい:)

TSP に関する相対的な (2000 年以降の) 新しい論文を探しています。私が見つけたすべての論文は非常に難しく、高レベルの数学スキルが必要でした。簡単な大学の数学の知識があり、Java と C のプログラミングの知識が豊富な人にとって読みやすい論文を探しています (これらの言語で TSP を実装する現在の論文は見つかりませんでした)。

どんなヒントでも大歓迎です。

（編集）

私が言おうとしているのは、難しい公式を理解する必要のない論文を探しているということです。たとえば、一部の論文では、アルゴリズムやソリューションの哲学について説明しています。そのアルゴリズムを実装する必要はありません。テクニックを説明するだけです。たぶん、いくつかの単純なジオメトリを使用しています...

Lin-Kernighan 法に基づいたいくつかの論文を見つけましたが、これは問題ないように思われました ...

目標は、300 万の頂点を持つグラフで多くの循環チェーンを作成することです。

問題は、ダイクストラのアルゴリズムを使用して、MySQL データベースにエッジを保存し、高速を維持し、循環チェーンを検索する方法です。

ウィキペディアやブログへのリンクを私の顔に投げ始める前に、私に聞いてください。

依存関係の並べ替えを行うのに最適なアルゴリズム/関数を見つけようとしています... 各アイテムには、依存関係のリストがあります。

イテレータベースのものが欲しいのですが、それはそれほど重要ではありません。

重要なのは、アルゴリズムがどのアイテムが依存関係サイクルの一部であるかを正確に指摘することです。この場合の詳細なエラー情報を提供したいと思います。

実際には、仕事を遂行するために必要なブール値/関数を持つ「依存関係ノード」クラスからアイテムをサブクラス化することを考えています。かっこいい（しかし説明的な）名前は大歓迎です:)

M x N2 つのランダムに指定された と が与えられexitた行列があるとしますentrance。

マトリックス内の各ノードを 1 回だけカバーするからentranceまでのパス (上、下、左、右) を見つけますか?exit