4

シンプルにするために、単一のノード タイプと単一のリレーションシップ タイプを持つ neo4j データベースがあるとします。すべての関係には「コスト」プロパティがあり (従来のグラフの問題と同様)、その値は負ではありません。

ここで、ID A のノードと ID B のノードの間のすべての可能なパスを見つけたいとします。パスの長さの上限 (10 など) を使用して、パスの合計コストが特定の定数 (20 など) 以下になるようにします。 .

これを実現する Cypher コードは次のとおりです (動作します)。

START a = node(A), b = node(B)
MATCH (a) -[r*0..10]-> (b)
WITH extract(x in r | x.cost) as costs, reduce(acc = 0, x in r | acc + x.cost) as totalcost
WHERE totalcost < 20
RETURN costs, totalcost

このクエリの問題は、コストが非負であるという事実を利用していないため、総コスト制限を超えるパスが削除される可能性があることです。代わりに、ノード A と B の間の長さ 0 から 10 までのすべての可能なパスをリストし (これは途方もなく高価になる可能性があります)、総コストを計算してから、制限を超えるパスを除外します。時間内にパスを剪定すると、パフォーマンスが大幅に向上します。

これは、BranchStates を使用し、関連する場合は拡張を防止することで、トラバーサル フレームワークで実行できることを知っていますが、Cypher ソリューションを見つけたいと思います (主にここで公開されている理由による)。

問題があれば、現在バージョン 2.2.2 を使用しています。

4

1 に答える 1

0

抽出前の関係コストの合計で十分でしょうか?

START a = node(A), b = node(B)
MATCH (a)-[r*0..10]->(b)
WHERE sum(r.cost) < 20
WITH extract(x in r | x.cost) as costs, reduce(acc = 0, x in r | acc + x.cost) as totalcost
RETURN costs, totalcost

ちなみに、剪定したいということは、命令的な方法が欲しいということです!

また、Cypherを少し助けてください、ラベルを使用してください

于 2015-06-23T20:14:05.023 に答える