問題タブ [graph-algorithm]

すべての点の座標がわかっているときに、デカルト平面で2次元オブジェクトの領域を見つけるのを誰かが手伝ってくれるのではないかと思います。例：三角形の面積を計算したい。A（12,34）B（45,89）C（25,35）

2次元オブジェクトの領域を見つけるための一般的なアルゴリズムが必要です。

ありがとうございました。

約 100 万のノードと 1,000 万を超えるエッジを持つ巨大な有向グラフがあります。エッジは重み付けされていません。グラフは小さな世界のようなグラフです。実際、すべてのノードが (平均して) 3 つの中間ノードを介して別のノードに接続されていることがわかります。

このグラフを考えると、開始ノードと宛先ノードの間のすべてのパス (サイクルなし) を返す高速アルゴリズムを考えることができますが、指定された最大数 N の中間ノードまでしか返されません (私の場合、ほとんどの場合 N は0 から 3 の間)?

グラフが d colorable かどうかを判断するプログラムを作成する必要があります。基本的には、彩色インデックスが d または d+1 であるかどうかを確認する必要があります。ここで、d はすべての頂点の最大次数です (vizing の定理)。この問題はNP完全であり、基本的にブルートフォースでなければならないことを私は知っています。アイデアはあったが、それが正しいかどうかわからない -

1) deg(v) = d で頂点を見つけ、v に付随するすべてのエッジを d の異なる色で色付けします。

2) v に隣接する頂点に付随するすべてのエッジに対して、d 色のセットからいくつかの色を適用します。

3) 「発見された」エッジに対して 2) を繰り返す

すべてのエッジが d 色で着色されている場合、彩度インデックスは d であり、グラフ G の 1 つの着色があります。

いくつかのエッジを d 色のセットの色で着色できない場合は、d+1 番目の色で色を付け、残りのエッジを d+1 色のセットの色で色付けします - ここに問題があります - このスキームを使用して、クロマティック インデックスが d+1 であると宣言した場合、他の着色でクロマティック インデックスが d になる可能性はありますか? (色付けされるエッジごとに、使用できる色を 1 つ選択しています)..

また、この問題に最適なグラフ表現はどれですか? 入力ファイルでは、グラフは隣接行列で記述されます。再帰で解決できることは知っていますが、方法がわかりません。私はいくつかの複雑すぎるアイデアで立ち往生しています:S (いくつかのヒントまたは擬似コードをいただければ幸いです)。

編集：

思いついたのですが、大丈夫だと思います（純粋なブルートフォース）。私はまだこれを実装しようとしませんでした。何か間違っているところがあればコメントしてください。もう一度言います - アルゴリズムは、グラフが d または d+1 色で色付け可能かどうかをチェックする必要があります。d は、与えられた単純なグラフのすべての頂点の最大次数です。

最初に、私の英語の知識が乏しいことをお許しください。

次の問題があります: 修正順序 (例: A -> D -> F) で 2 つ以上のポイント間の最短経路を見つけなければなりません。私はダイクストラのアルゴリズムに精通しています。しかし、それは 2 つの Point 間の最短経路のみを計算します。また、TSP についても聞いたことがありますが、それも当てはまらないようです。修正順序がないためです。自分の問題を既に Web で検索しましたが、あまり人気のない問題であるか、間違ったキーワードを使用した可能性があります。

それでも、この機能をうまく提供しているルート プランナーはたくさんあるので、解決策が存在するはずです。

だから、アグロリスに名前を付けて私の問題を手伝ってくれる人、またはアドバイスをくれる人がいますか。

ご助力ありがとうございます！敬具 アンジェロ

//編集ああ、それは非常に恥ずかしいです. 私は長い間考えていたようで、実際の問題を説明できませんでした。そのようなものです：最初からしか使用できないいくつかのチケットがあります。

T1: A -> B (コスト 50) T2: B -> C (コスト 50) T3: A -> B -> C (コスト 80) 与えられたルートは A -> B -> C

ご覧のとおり、指定されたルートを 2 つの別々の問題として扱うと、総コストは 100 になりますが、明らかにチケット T3 の方が優れたソリューションです。

隣接行列が隣接リストよりも優れているアルゴリズムはありますか？逆はどうですか？

テキストの壁で申し訳ありませんが、それは私ができる限り簡潔です!

私は 1 つの非常に大きな有向グラフ G と、G 内からの頂点のサブセット S を持っています。私がやりたいことは、S によって誘導される G の部分グラフを見つけることです。 p と G の頂点 q で、誘導されたサブグラフのこれら 2 つの頂点の間にエッジが存在すること。これが重要です。通常の誘導されたサブグラフの問題よりも少し複雑です（私はそう思います）。

問題を解決するために私が考えることができる最も基本的な方法は次のとおりです（おそらく最も効率的ではないことを認識しています。実装するのに複雑すぎない他の提案があれば教えてください）：S内の頂点のすべてのペアについて、G でそれらの間のパスの存在をテストします。そのようなパスが存在する場合、誘導された部分グラフの p と q の間にエッジを挿入します。私の目的では、n^2 時間はそれほど悪くありません。

したがって、2 つの質問があると思います。1) 2 つの頂点間にパスが存在するかどうかを判断する最速の方法は何ですか? パスが存在するかどうかだけで、パスを知る必要はありません。さらに、この計算を高速化するためにグラフ全体に対して実行できる前処理がある場合、頂点の各ペア間でこの計算を実行する必要があるため、それは何でしょうか?

2）私が説明した誘導サブグラフのタイプを見つけるために私が提案した方法よりも速い方法はありますか？

助けてくれてどうもありがとう！

以下に示すグラフ理論（組み合わせ論にも関連しています）の問題があり、それを解決するためのアルゴリズムを設計するための最良のアプローチは何でしょうか。

6つのノードの4つの異なるグラフ（異なる、つまり、STAR、LINE、COMPLETEなどの異なる構造を意味します）と24の一意のオブジェクトが与えられた場合、これらのオブジェクトをこれらの4つのグラフに4回割り当てるアルゴリズムを設計します。 4つの割り当てにわたってグラフ上で隣接するものを繰り返すことは最小限に抑えられます。たとえば、オブジェクトAとBが1つの割り当ての4つのグラフの1つで隣接している場合、最良の場合、AとBは他の3つの割り当てで再び隣接することはありません。

明らかに、そのような最小化が進むことができる程度は、与えられた特定のグラフ構造に依存します。しかし、私はここで一般的な解決策にもっと興味があります。そのため、4つのグラフ構造が与えられた場合、そのような最小化はアルゴリズムの結果として保証されます。

この問題を解決するための提案/アイデアは歓迎されます。設計を説明するには、いくつかの擬似コードで十分な場合があります。ありがとうございました。

値のセットがあり、各値には可能なグループがあります。値は繰り返すことができますが、グループが異なります。

最小数のグループを取得するための最適なアルゴリズムは何ですか

サンプルセット：（12、グループb）（38、グループa）（12、グループa）

望ましい結果：（38、グループa）（12、グループa）

（1つのグループのみが使用されます）

--編集：上記のサンプルのようなセットから最小数のグループを見つけるためのアルゴリズムが必要です。私が悪いアルゴリズムを持っている場合、それは（12、グループb）（38、グループa）を選択しますこれは私が望むものではなく、1つを使用する代わりに同じ値の2つのグループです

今夜、私はグラフ距離アルゴリズムについて考えていて、車で運転しているときにこれを思いつきました:

とてもエレガントに見えたので、最初はかなり自慢していました。しかし、それがうまくいかないことに気付きました.corecursionがループに陥る可能性があります.

私は自分自身を納得させるためにそれをコーディングしなければなりませんでした：

でも今思うと、よく考えていたなと思います。

コアカーシブなデータを処理する際の一般的なエラーとアンチパターンのリストを読み進めて、コアカーシブで考えるように脳を訓練できるようにすることはできますか? コアカーシブ以外のデータを考えることについては、経験によってかなりよく訓練されていますが、できれば他の人の間違いから学びたいと思っています。

パイプライン業界でルーティングを目的としたアルゴリズムを作成する必要があります。4 つのパイプラインが利用可能で、その間に石油を注入するか、任意のステーションで取り出すことができます。30000 ユニットの容量があり、35000 (荷送人からの指定) を輸送する必要がある場合、指定を削減する必要があります。しかし、最大ボリュームに対応できるように、どのようにそれを削減し、どのようにスケジューリングするのでしょうか?

巡回セールスマン問題 (TSP) やその他の NP 困難な問題を使用して解決しようとしましたが、成功しませんでした。