Reisender Verkäufer auf einem Baum - Algorithmus, Baum, Diagrammalgorithmus

Also, ich habe N Knoten und N-1 Kanten. Daher kann der Graph als ein Baum dargestellt werden. Jetzt muss ich die minimale Entfernung finden, die es braucht, um jeden Knoten mindestens einmal zu erreichen. N hat eine obere Grenze von 10 ^ 5.

Gibt es eine Möglichkeit, dies in einer angemessenen Zeit zu tun? Es mag einen Namen für dieses Problem geben, aber wenn es so ist, kann ich es nicht finden.

Ich bin mir bewusst, dass TSP NP-vollständig ist. Da es sich bei diesem Diagramm jedoch um einen Baum handelt, habe ich mich gefragt, ob es tatsächlich eine Lösung für dieses Problem gibt.

Vielen Dank.

Antworten:

Wenn dies ein Baum ist, dann eine Tiefe zuerst oder Breite zuerst Baumdurchquerung ist eine einfache Möglichkeit, jeden Knoten zu besuchen. Dies ist eine O (N) -Operation.

Wenn es für Sie keinen Unterschied macht, verwenden Sie die Tiefe-zuerst-Traversierung, da sie weniger Speicher benötigt und IMO einfacher zu implementieren ist.

Was Sie tun können, ist Zyklen innerhalb der zu isolierengraphieren und gruppieren sie als einen riesigen Knoten. Wenn Sie dies tun, sollten Sie eine gerichtete azyklische Grafik von Gruppen haben, die Zyklen sind, die aus Ihren Knoten bestehen. Den kürzesten Pfad zu finden, der jeden Pfad in einem dag erreicht, ist einfach zu machen. An diesem Punkt wäre nur sicherzustellen, dass Ihre Endpunkte jeder Gruppe mit dem richtigen Knoten in der Gruppe verbunden sind, die Sie als nächstes durchqueren möchten.

Nun, ich habe dieses Problem alleine gelöst. Grundsätzlich wird der kürzeste Pfad, der jeden Baum im Knoten besucht, jede Kante zweimal durchlaufen, mit Ausnahme des Pfads vom Ursprung zum Knoten, der am weitesten vom Ursprung entfernt ist. Sie verwenden also ein dfs und speichern den längsten Pfad. Hier ist mein Code.

long long dfs(int a, int b){ //a is the current node, b is the node you reached the current node from.
ll ans=0;
for(int i=0;i<elist[a].size();i++){ //elist is just a vector of all the edges.
int x=elist[a][i];
if(x==b) continue;          //this checks to make sure you aren"t going straight back to the previous node you visited.
ans=max(ans,cost[a][i]+dfs(elist[a][i],a)); //ans is the longest distance. Cost is an array of all the edge costs.
}
return ans;

}