問題タブ [graph-algorithm]

タイトルが言ったように、私は与えられたグラフのノードのすべてのペア間の距離を見つけるアルゴリズムを実装しようとしています。しかし、もっとあります:(あなたを助けるかもしれないもの）

• グラフは重み付けされていません。すべてのエッジの重みが1であると見なすことができることを意味します。
• |E| <= 4*|V|
• グラフはかなり大きいです（最大で約144の深さ）
• グラフは
• サイクルがあるかもしれません
• 私はPythonでコードを書いています（アルゴリズムを参照する場合は、コードもいいでしょう:)）

ジョンソンのアルゴリズム、フロイド-ワーシャル、およびすべてのペアのダイクストラについて知っています。ただし、これらのアルゴリズムは、グラフに重みがある場合に適しています。

これらのアルゴリズムは重み付きグラフを対象としているため、私の場合により良いアルゴリズムがあるかどうか疑問に思いました。

ありがとう！

まず、知らない人のために-Anytime Algorithmは、実行可能な時間を入力として取得するアルゴリズムであり、その時間に可能な最善のソリューションを提供する必要があります。

重み付けされたA*はA*と同じですが、f関数に1つの違いがあります。

（ここで、gはノードまでのパスコストであり、hはゴールに到達するまでのパスの終わりまでのヒューリスティックです）

私のいつでもアルゴリズムは、制限時間に達するまで、1から0.5までの重みを減らしてWeightedA*を実行します。

私の問題は、ほとんどの場合、これが解決策に到達するまでにかなりの時間がかかることです。10秒のようなものが与えられた場合、通常は解決策が見つかりませんが、ビームのような他のアルゴリズムは0.0001秒で解決策を見つけます。

何をすべきかアイデアはありますか？

私は現在、技術的なプログラミング面接の準備に関するSteve Yeggeのアドバイスに従っています：http ：//steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

グラフに関する彼のセクションで、彼は次のように述べています。

メモリ内のグラフを表現するための3つの基本的な方法（オブジェクトとポインタ、マトリックス、および隣接リスト）があり、各表現とその長所と短所をよく理解する必要があります。

行列と隣接リストの表現の長所と短所はCLRSで説明されていますが、これらをオブジェクトの表現と比較するリソースを見つけることができませんでした。

考えてみるだけで、自分で推測することもできますが、大切なことを見逃していないことを確認したいと思います。誰かがこれを包括的に説明するか、そうするリソースを私に指摘することができれば、私はそれを大いに感謝します。

それは私に正しい答えを与えていません。はい、有効なパスを返します。ただし、返されるパスは最短パスではありません。問題は、屋外の合計距離が maxDistOutdoors の制約よりも大きい場合にパスをスキップするという太字の行にありますが、それを変更する方法がわかりません。その太線を削除すると、正しい最小パスが得られますが、屋外の合計距離が maxDistOutdoors 未満の最小パスを見つけたいので、そのようなチェックが必要な場合。

私はすでに印刷ステートメントを試しましたが、あきらめようとしています。なぜそれが間違っているのか、今は理解できません。

openglでメッシュ/グリッドを変形する必要があります（2d zのみが同じままです）

変形とは、ユーザーがマウスを使用するか、特定の頂点をタッチしてドラッグし、残りが続くことを意味します

ここに私が必要なものを正確に説明するリンク（http://www.gamasutra.com/view/feature/3432/2d_surface_deformation.php ）がありますが、自分で実装するのは難しすぎるようです。より簡単な方法を提案する（グラフィックライブラリなどを使用して）それは素晴らしいことです

複数のレストラン（たとえば20）へのフードデリバリーを想定しましょう。利用可能な（たとえば10個の）ドライバーがあります。さらに、これらのレストランから家庭に食べ物を配達するために、4時間で100件の注文があったとします。

そのため、ドライバーは、ある場所で食べ物を受け取り、自宅の顧客に配達するように調整する必要があります。

主な目標は、配達までの時間、つまり注文から自宅に到着するまでの時間を最小限に抑えることです。2番目の目標は、ドライバーの容量を最大化することです（つまり、すべての注文を配信するための最小時間）。

注文は4時間以上かかるので、均等に、つまり3分ごとに注文することに注意してください。また、注文がランダムに20軒のレストランに向けられていると仮定します。

任意の場所から目的地、そして秒までの移動時間を計算できると仮定します。

私はすべてのドライバーの位置をリアルタイムで知っています。私は彼らのステータスも知っています。つまり、彼らは現在注文を受け取る途中（既知の目的地に行くため）であり、すでに注文を受け取り、既知の目的地に向かう途中ですか。

制約は次のとおりです。1）指定された時間の後に注文を受け取る必要があります（つまり、レストランの食事の準備時間）2）45分以内に注文を配信する必要があります（それ以外の場合はアラートがスローされます）3）時間に対応するために「x」分で時間を埋める必要があります注文を受け取るために店まで歩いて過ごしたなど。4）顧客への注文の配送と支払いの回収に費やした時間に対応するために、時間を「y」分で埋める必要があります。5）ドライバーは、特定の支払い方法のセット（Cash、Visa、Amex、MasterCardなど）しか持っていません。顧客の要求（現金、ビザなど）とドライバーの能力（現金、ビザ、アメックスなど）を一致させる必要があります。

したがって、たとえば、目的地の近くと集荷場所の近くで2つの注文を受け取った場合、別の「無料」ドライバー（何もしていない）があったとしても、同じドライバーを使用して両方の注文を集荷して配達する方が効率的です。両方の注文。

各レストランに配達ゾーンが適用されると想定できます。つまり、レストランから注文するほとんどの人は、レストランの近くにいる可能性があります。したがって、このアルゴリズムは、ドライバーを自動的に都市ゾーンにセグメント化し、ゾーン内のドライバーをすでに優先するように管理する必要があります。

一連の操作が与えられた場合：

a * b * a * b * a * a * b * a * b

サブストリングの再利用を可能にするために最適なサブディビジョンを取得する方法はありますか。

作る

a * b * a * b * a * a * b * a * b => c * a * c、ここでc = a * b * a * b

そしてそれを見て

a * b * a * b => d * d、ここでd = a * b

全体として、8つの初期操作をここで説明する4つに減らしますか？

（c =（d = a * b）* d）* a * c

もちろん、目標は操作の数を最小限に抑えることです

ある種の接尾辞木を検討しています。

私は特に線形時間ヒューリスティックまたはソリューションに興味があります。'*'演算は、実際には行列の乗算です。

親グラフのすべてのサブグラフを列挙するための効率的なアルゴリズムは何ですか? 私の特定のケースでは、親グラフは分子グラフであるため、接続され、通常は 100 未満の頂点が含まれます。

編集:接続されたサブグラフにのみ興味があります。

この質問は、有向グラフでサイクルを検出するための優れた答えを持っています。残念ながら、MapReduceバージョンを作成するのは簡単ではないようです。

具体的には、有向グラフからサイクルを削除するためのMapReduceアルゴリズムに興味があります。

幅優先探索（BFS）アルゴリズムを使用して評価しましたが、サイクルを遮断するために2つの異なるエッジが同時に削除される可能性があるという問題があります。このシナリオの影響は、削除できるエッジが多すぎることです。削除されるエッジの数を最小限に抑えながら、サイクルを削除することが重要です。

利用可能な証明を備えたソリューションが推奨されます！

ありがとう。

キュー (queue_len) 内のエントリ数を計算する Python 2.6 の監視アプリケーションがあります。これらの queue_len の経時変化率の値を使用して、そこからトレンドを抽出できる単純な関数を作成したいと考えています。

目標は、フリップフロップではなく、時間の経過に伴う +ive または -ive の傾向に応じて、キュー処理ノードを起動またはシャットダウンすることです。

金融分野のMACDは、私が必要としているもののように見えますか? ここで助けを探しています。