問題タブ [graph-traversal]

無向で正の重み付きグラフGが与えられた場合、 Gの一部のエッジの重みは不明です。例えば、

ここで、edge(B, C) の重みは不明です。

AからBへの移動には7のコストがかかります。BからCへ、またはその逆にトラバースすることで未知の重みe = weight(B,C)を導き出すことができ、 eのコストがかかり、最終的に既知の重みになります。そして、 AからCからBを通って歩くと、合計でe+7のコストがかかります。

私の質問は、開始点が与えられたときに、どのくらいの速さですべての未知の重量を取得できるでしょうか? つまり、開始点 (たとえばA ) からすべての未知の重みエッジを可能な限り小さいコストでトラバースします。

未知数が1個の場合は単純です。最初に、開始点から目的のエッジの頂点までの最短パスを見つけ、未知の重みエッジをトラバースできます。しかし、未知の重みエッジの数が 1 より大きくなった場合の解決方法がわかりません。

誰でもこれを行う方法を理解できますか?

したがって、無向無加重グラフがあります。サイクルが含まれています。どのノードにも繰り返しアクセスせずに、最も多くのノードをアクセスするパスを見つけたいと思います。これはグラフ トラバーサルであるため、任意のノードで開始および終了できます。

背景調査: 巡回セールスマン問題 (TSP) を見てきました。この問題は異なり、開始した場所から終了することはできず、ウェイトはありません。他のアルゴリズムをいくつか調べましたが、この問題に適したものは見つかりませんでした。

グラフ サイズ: グラフには 100 個のノードがあります。10 個の切断されたノードを使用します。

更新:これを次の場所に移動しました: https://math.stackexchange.com/questions/243375/what-is-the-maximum-number-of-nodes-i-can-traverse-in-an-undirected-graph-訪問

デカルト平面上のグラフの最適なツアーを毎回解決する分枝限定アルゴリズムを設計する必要があります。ランタイムの早い段階で絶望的な分岐を特定すると、「100 倍速く」実行されるプログラムに統合されるというヒントが与えられました。開始/終了ノードに接続された最短のエッジがツアーの最初または最後のエッジになると仮定するという考えがありましたが、薄いひし形のグラフはそうではないことを証明しています。これらの絶望的なブランチを排除する方法や、これについて言及しているリファレンスを持っている人はいますか?

基本的に、辞書順だけでなく、ソリューションのサブセットに分岐するためのより良い方法はありますか? 最初の分岐はエッジ ab を含めて除外し、2 番目の分岐は分岐 ac を含めて除外します

ベクトルを使用して頂点とエッジを格納する、クラスとして設定したグラフのトラバースに取り組んでいます。グラフで深さ優先検索を使用して、通過するパスを表示していますが、コードを取得して、次のような形式で頂点を順番に表示したいと思います。

「u」と「v」は両方とも開始頂点であり（同じ頂点で開始および終了する必要があります）、「i」値は途中で通過する頂点です。

これは私がこれまでに持っていた DFS の機能で、一般的なリファレンスとして使用できるように単純化しました。これを希望どおりに表示するために、ここで変更できるものはありますか? (現在、何も表示するように設定されていません)。

簡単に言えば、私の質問は、Neo4j で使用されるトラバーサル ロジックを変更できるかどうかです。到達可能性の計算中に、どのエッジがトラバースされ、どのエッジがトラバースされないかを制御する方法です。

完全な説明：

現在の DB から neo4j への移行を検討していますが、neo4j が次のタスクに適しているかどうか疑問に思っています。

約 10M の単純なノードを持つ大きなグラフがあります。それらの属性は単一の ID のみです。
エッジも「スタンダード」「オープン」「クロージング」の3種類をご用意。「オープニング」と「クロージング」も「色」属性を持っているので、一致させます。各「開始」エッジには、一致する「終了」エッジが 1 つだけあります。たとえば、「3」の色の開始エッジが 1 つあるため、同じ色の終了エッジも 1 つあります。

トラバーサルのルールがかなり単純な 2 つのノード間の到達可能性を解決する必要があります。通常のエッジを好きなように通過したり、開いているエッジを好きなように通過したりできます。スタックしますが (これはトリッキーな部分です)、いくつかの「閉じた」エッジがあるジャンクションに到達した場合は、最後に遭遇した「開いた」エッジと一致する閉じたエッジを通過し、その「開いた」エッジをスタック。

例えば：

a -[STANDARD]->B-[Open color:3]->C-[Standard]->D-[Close color:3]->E
および
D-[Close color:4]->F

D には、色の異なる 2 つの「閉じた」エッジがあることに注意してください。上記で定義されたルールにより、カラー スタックの一番上に [3] があるため、E は A から到達可能です。
ただし、F は A から到達できません。

このようなグラフ トラバーサル ロジック用に neo4j を構成できますか? ありがとう！！

Traversal API を使用して、特定の一連の企業ノードについて、製品ノード リストに含まれるすべての製品を提供する企業ノードのみを取得しようとしています。Cypher を使用する以前の試みはうまく機能しませんでした。この例では:

3 つの会社すべてが会社リスト クエリに含まれており、製品 A と C がクエリの製品リストに含まれている場合、製品 A と C を提供しているため、会社 2 と 3 のみを返す必要があります。クエリは次のとおりです。

を使用すると、リストEvaluator.includeWhereEndNodeIs(productNodes)内のいずれかの製品を提供するすべての会社が返されproductNodesます (上記の例では 3 つの会社すべて)。エバリュエーターを使用する場合Evaluators.includeIfContainsAll(productNodes)、製品ノード リストに複数の製品がある場合、企業ノードは返されません。

任意の提案をいただければ幸いです。

無向の重み付きエッジを持つ完全グラフがあり、グラフノードのサブセットを通じて最低のコストサイクルを見つける必要があります。巡回セールスマンとは異なり、どのノードにも複数回アクセスでき、すべてのノードにアクセスする必要はありません。コストによって、パスの通過エッジの重みの合計が最小になる必要があります。

たとえば、隣接行列形式のグラフは次のとおりです。

ここで、各エッジの重みは各要素に使用されます。で開始および終了するサイクルはa、次[b,d]のようになります。

これに最適なアルゴリズム、または本当に優れたヒューリスティックアルゴリズムはありますか？

4 ビットと連続シフトを使用して可能な組み合わせの数を把握しようとしています。白と黒のマークが付いた紙片を読み取る4つの光センサーの配列があります。その位置を把握したい。

繰り返しのないユニークな可能性の最大数を知る必要があります。手動で計算しようとしましたが、14 を超えることはできません。可能であれば 16 に到達したいと考えています。

これが私のシーケンスです：

ところで、私は行方不明0101で、1010

行*列グリッドがあり、グリッド上の各ノードに整数（状態）値があるとします。

の値が

state[row][0] == state[row][NUMBER_OF_COLUMNS -1]

この2点から同じ状態だけで構成された「パス」があるかどうかを確認したい。

パスとは、左、右、下、または上の状態が元の状態と同じであることを意味します。

重要かどうかはわかりませんが、状態がバイナリ（＃または-）であるとしましょう。したがって、state == "-"のパスをチェックしている場合、状態がNになったら、パスを続行できます。 E、S、Wも== "-"

終了行は開始行と同じである必要があります。

成功例：

また

また

失敗の例：

また

また

失敗します。

どうすればよいですか？私はObjectiveCでコーディングしていますが、手順を理解するのに役立つ擬似コードで十分です。

パスのBOOL存在をチェックすることに加えて、パス内のすべてのグリッド座標の配列を返したいと思います。

これは実装が簡単ですか、それとも私は頭を悩ませていますか？

私はNeo4jグラフデータベースに使用しており、Javaを使用してそこからパスを抽出しています。次のようなパスがあります。

パス内のノード ID をそのプロパティに置き換えたい。元。プロパティ を持つノード ID 3 の場合"name=ABC"、出力は"[(ABC)--[KNOWS,5]....]" How it can be done?のようになります。