とすると、質問には次のようになります。重み付けされていないツリーが私に提供され、配列内に与えられた特定のノードだけを訪れると予想されるノードから開始できます。私の目標は、必要なすべてのノードに移動するのにかかる時間を見つけることです。各辺は1分で移動できます。Dijkstraのアルゴリズムの帰り旅行時間を
私はすでに訪れたいノードから始まり、そこから最短経路を形成しようと試みるためにDijkstraのアルゴリズムを実装しようと試みました。 しかし、私の問題は、ソリューションが提供されているにもかかわらず、Dijkstraのアルゴリズムが同じエッジを2回移動することを強制する方法がわからないため、最も効率的ではない可能性があります。 
上記の画像にこの問題の例があります。私がノード[90,50,20,75]に行きたいと仮定し、私はノード90で始まり、ノード50に続いてノード20に行きました。どのようにしてダイクストラのアルゴリズムがノード20に到達する前にノード50への戻り旅行時間を考慮する？
私のコメントで詳しく説明しましょう：まず、ツリー内の任意のルートを修正して、ツリーがルートされているかどうかを確認します（おそらくルートツリーがあります）。次に、最初のステップでは、ルートから始まり、ルートで終了し、すべての目的のノードを通過する最小長さのサイクルを見つけます。
これは、分割征服のアプローチで行うことができます。任意のノードにいる場合は、そのノードをパスに含める必要があるかどうかを確認できます。そうなら、あなたはそうします。次に、すべてのサブツリーについて、同じアプローチを使用し、必要に応じてパスを拡張するだけです。最後に、サブパスが現在のサブツリーのルート（コードに続く）に戻ることを確認します。
サイクルを見つけたら、最後に非循環パスになるように最長のサブパスを削除する必要があります。これは、サイクルを歩くだけで線形時間で行うことができます。私の実装では、サイクル抽出でノードのシーケンスだけでなく、パスが単にノードを通過するかどうかを決定するフラグも出すようにしました。したがって、このステップでは、実際に訪問された任意の2つのノード間のパスセグメントを単純に見つけます。
最適性をアサートするために必要なステップがまだありません。しかし、この時点までのコードを見せてください。私はJavaScriptで実装しています。あなたはそれをそのままSO上で実行できるからです。この実装は効率性ではなく理解可能性を目的としています。
//the tree from your example
var tree = { value: 90, children: [{ value: 50, children: [{ value: 20, children: [{ value: 5 }, { value: 25 }] }, { value: 75, children: [{ value: 66 }, { value: 80 }] }] }, { value: 150, children: [{ value: 95, children: [{ value: 92 }, { value: 111 }] }, { value: 175, children: [{ value: 166 }, { value: 200 }] }] }] };
var nodesToVisit = [90, 50, 20, 75];
//var nodesToVisit = [92, 111, 166];
function findCycle(treeNode, nodesToVisit) {
\t var subPath = [];
\t var currentNodeIncluded = false;
\t if(nodesToVisit.indexOf(treeNode.value) != -1) {
\t \t //this node should be visited
\t \t subPath.push({node: treeNode, passThrough: false});
\t \t currentNodeIncluded = true;
\t }
\t
\t //find the subpath for all subtrees
\t if(treeNode.children) {
\t \t for(var i = 0; i < treeNode.children.length; ++i) {
\t \t \t var subTreePath = findCycle(treeNode.children[i], nodesToVisit);
\t \t \t if(subTreePath.length > 0) {
\t \t \t \t if(!currentNodeIncluded) {
\t \t \t \t \t subPath.push({node: treeNode, passThrough: true});
\t \t \t \t \t currentNodeIncluded = true;
\t \t \t \t } \t \t \t
\t \t \t \t //if we need to visit this subtree, merge it to the current path
\t \t \t \t subPath = subPath.concat(subTreePath);
\t \t \t \t subPath.push({node: treeNode, passThrough: true}); //go back to the current node
\t \t \t }
\t \t }
\t }
\t
\t return subPath;
}
function removeLongestPassThroughSegment(cycle) {
\t var longestSegmentStart = -1;
\t var longestSegmentEnd = -1;
\t
\t //the start of the current pass-through segment between non-pass-through nodes
\t var currentStart = -1;
\t var segmentLengthAtStart = -1;
\t for(var i = 0; i < cycle.length; ++i) {
\t \t if(!cycle[i].passThrough) {
\t \t \t //we have found a node that we need to visit
\t \t \t if(currentStart != -1) {
\t \t \t \t var length = i - currentStart;
\t \t \t \t if(length > longestSegmentEnd - longestSegmentStart) {
\t \t \t \t \t longestSegmentStart = currentStart;
\t \t \t \t \t longestSegmentEnd = i;
\t \t \t \t }
\t \t \t } else
\t \t \t \t segmentLengthAtStart = i;
\t \t \t currentStart = i;
\t \t }
\t }
\t
\t //check the path segment that wraps around
\t if(cycle.length - currentStart + segmentLengthAtStart > longestSegmentEnd - longestSegmentStart) {
\t \t longestSegmentStart = currentStart;
\t \t longestSegmentEnd = segmentLengthAtStart;
\t }
\t
\t //build the final path by cutting the longest segment
\t var path = [];
\t var i = longestSegmentEnd;
\t do {
\t \t path.push(cycle[i]);
\t \t i++;
\t \t if(i >= cycle.length)
\t \t \t i = 0;
\t } while(i != longestSegmentStart);
\t path.push(cycle[longestSegmentStart]);
\t return path;
}
function printPath(path) { \t
\t for(var i = 0; i < path.length; ++i)
\t \t if(path[i].passThrough)
\t \t \t console.log("Pass through " + path[i].node.value);
\t \t else
\t \t \t console.log("Visit " + path[i].node.value);
}
var cycle = findCycle(tree, nodesToVisit);
console.log("Cycle:");
printPath(cycle);
var path = removeLongestPassThroughSegment(cycle);
console.log("Final Path:");
printPath(path);あなたは、このコードは、すでに最適解とプリントを見つけることがわかります。
Final Path:
Visit 90
Visit 50
Visit 20
Pass through 50
Visit 75
でも希望のノードのより挑戦的なセットのために、これは、最適なパスを取得します（var nodesToVisit = [92, 111, 166];）：
Final Path:
Visit 92
Path through 95
Visit 111
Pass through 95
Pass through 150
Pass through 175
Visit 166
これで最適な解決策を見つけるために不可欠なことは、最後にカットされたパスセグメントが実際に最長のパスセグメントであることです。これは必ずしも上記のコードでは当てはまりません。サブツリーを処理する順序を自由に選ぶことができ、訪問するノードにいる場合は実際の訪問を自由に入れることができます（パススルー）を参照してください。
これを行うには、目的のノード間の距離を見つけます（ツリー上で効率的に行うことができます）。最大の距離を持つペアが開始ノードと終了ノードになります。したがって、サイクルでの訪問がその後に発生するようにする必要があります（つまり、他のノードが訪問していない）。これは、再帰呼び出しから戻されたパスセグメントの先頭と最後に特定の訪問先ノードを強制することで実行できます。たとえば、サブパスに開始ノードまたは終了ノードが含まれている場合は、再帰呼び出しも戻ります。呼び出し関数では、これらのサブパスを正しい順序で配置します。これにより、最も長いパススルーセグメントが何であるかをすでに知っているので、removeLongestPassThroughSegment()関数を単純化することもできます。
ここでやったことと、提供された画像はデモンストレーションのためのものでした。 –
アルゴリズムはバイナリツリーを想定していません。それはちょうどルートの木を仮定します。任意のノードをルートとして固定することで、任意のツリーをルートツリーにすることができます。 –
ツリーには、任意の2つのノード間のパスが一意であるという利点があります。したがって、実際にはパスの検索アルゴリズムは必要ありません。 Btw、Dijkstraは加重グラフでのみ意味をなす。重み付けされていないグラフの場合、BFSはより簡単で通常は高速です。開始ノードおよび/または終了ノードは固定されていますか？ –
@NicoSchertlerいいえ、開始ノードと終了ノードは最大2つのノード間のパスが一意であることを理解していますが、私の解決策は各ノードを訪れる合計時間を考慮していると考えられますすべての店舗と私は、私が望むどんなノードでも歩くことができる人間であり、各エッジは1分以上歩くことができました）、私のプログラムがいつどのように戻ってくるかを知っていると確信していますエッジ？あなたの時間に感謝します –
私は完全なアルゴリズム、ちょうど観測を持っていません：あなたがいくつかのサブツリーを持つノードにいるとします。サブツリーの1つに移動する場合は、そのサブツリー内のすべてのターゲットノードが訪問された場合にのみ、最初のノードに戻る必要があります。多くの場合、1つのサブツリーは最初のノード（エンドノードを持つサブツリー）に戻ることはできません。したがって、他のサブツリーをどの順序でトラバースするかは関係ありません。だから、分裂克服のアプローチが有効かもしれません。 Btw、これはハミルトニアンのパスです。一般的なグラフではNP困難です。しかし、それは木の上でより簡単かもしれないかのように見えます。 –