Travelling salesman problem for a tree graph (no hamiltonian path)
Almost broken my head while trying to find algorithm that finds fastest route in graph that pass through ALL graph vertices from start vertex (with no need to return to start edge).
I have checked all the main algorithms for graphs and similar problems on stackoverflow.
Almost all TSP examples I googled was for complete graphs.
TSPLIB not looks like can solve my problem.
Sorry if I missed something.
Input graph (check images):
• Weighted
• Undirected
• Planar
• No hamiltonian path
• No negative edges
• Size: up to 100 vertices (but usually 50-70)
Edge length almost the same in graph, so we can say that this is an unweighted graph and take 1 as a length of edge.
Should solve with "dead end" cases:
Real input graphs looks like this (start from vertex 0):
Big graph:
Expected result:
• Shortest path (a set of vertices indices) through all the edges from start edge.
• No need to return to start edge at the end
Got only one idea:
1) Check all possible combinations of path, measure the distance and find the path with smallest distance.
1a) Use Depth-First Search or Breadth-First Search
1b) If while iterating the current vertex have more than one edge - make a separate combinations for all of them (try all possible ways).
1c) In my case there are a lot of “dead end” in graph, so algorithm should find the way (the fastest ofc) from there and iterate through already passed vertices and not get stuck.
2) Reconstruct the path
Maybe I should use Minimum Spanning Trees algorithm here too…
Or maybe for faster calculation I should split my graph to multiple smallest that are linked only with single edge (like 49-52, 40-41 on screenshot)
Any help will be appreciated.
Prefer C# examples (libs) but I can port code from any language.
I my case this NP-hard problem should be solved fast as possible and not so perfectly, so I used the best solution for me (simplified version) (best case scenario should be O(n+n*m), n - nodes, m - edges):
- Use Breadth-first search (BFS) to find the deepest (far) node from start (let's call it FAR_NODE)
- Use Djkstra algorithm to calculate distance from FAR_NODE to all the other nodes (actually I was using BFS algorithm here too because for euclidian space it is faster and gives the same result)... so just save distance in all nodes from FAR_NODE.
- Start walking through the graph from start node to nearest not passed, prefer nodes with bigger "distance from FAR_NODE"
- If there is no not passed nodes linked to current node- chose the nearest not passed node (preferred with with biggest "distance" value)(can use BFS too).
Algorithm is published and documented here(with animations): https://github.com/Stridemann/TravelShortPathFinder
===================================================
Using Branch&Bound way:
As I mentioned in comment to my question I almost solved this in branch&bound way. The idea is to give a score to each permutation and process only with bigger score.
If someone interesting this is example code:
using System.Collections.Generic;
using System.Linq;
using GraphFastPath.GraphData;
namespace GraphFastPath
{
public class BranchNBound
{
public static BranchNBound Instance;
private readonly Graph _graph;
public bool _ignoreDeadEnds;
public SortedDictionary<float, List<BbIterationStep>> _iterations = new SortedDictionary<float, List<BbIterationStep>>();
public List<BbIterationStep> BestPath = new List<BbIterationStep>();
public int IdCounter;
public int MaxNodesVisited;
public BbIterationStep PathNode;
public BranchNBound(Graph graph, bool ignoreDeadEnds)
{
_graph = graph;
_ignoreDeadEnds = ignoreDeadEnds;
Instance = this;
var nodesCount = ignoreDeadEnds ? _graph.Nodes.Count(x => !x.IsDeadEnd) : _graph.Nodes.Count;
foreach (var edge in _graph.Nodes[0].Edges)
AddStep(new BbIterationStep(edge, nodesCount), 1000);
}
public int IterationsCount => _iterations.Sum(x => x.Value.Count);
public void RegisterGoodPath(BbIterationStep step)
{
if (step._uniqPassedNodesCount < MaxNodesVisited)
return;
if (step._uniqPassedNodesCount > MaxNodesVisited)
{
BestPath.Clear();
MaxNodesVisited = step._uniqPassedNodesCount;
}
BestPath.Add(step);
}
public void DoStep()
{
var min = _iterations.Last();
var list = min.Value;
_iterations.Remove(min.Key);
foreach (var step in list)
step.DoStep();
}
public void AddStep(BbIterationStep step, float cost)
{
step.VariantId = IdCounter++;
if (!_iterations.TryGetValue(cost, out var list))
{
list = new List<BbIterationStep>();
_iterations.Add(cost, list);
}
list.Add(step);
}
}
public class BbIterationStep
{
private readonly int _totalNodesCount;
private readonly Edge _currentEdge;
private int _totalPassedNodesCount;
public int _uniqPassedNodesCount;
public string Debug;
public List<Node> LocalPath = new List<Node>();
public Node Node;
public BbIterationStep Parent;
public float Score;
public int VariantId;
public BbIterationStep(Edge currentEdge, int nodesCount)
{
_currentEdge = currentEdge;
_totalNodesCount = nodesCount;
Node = _currentEdge.From;
_uniqPassedNodesCount++;
_totalPassedNodesCount++;
}
public BbIterationStep(BbIterationStep from, Edge currentEdge, string debug, float score)
{
Parent = from;
Score = score;
_currentEdge = currentEdge;
Debug = debug;
Node = _currentEdge.From;
_uniqPassedNodesCount = from._uniqPassedNodesCount;
_totalPassedNodesCount = from._totalPassedNodesCount;
_totalNodesCount = from._totalNodesCount;
}
public int Id => _currentEdge.From.Id;
public Node NodeTo => _currentEdge.To;
public void DoStep()
{
_currentEdge.Pass(false);
_currentEdge.To.SetProcessed();
var passed = CheckPassed(_currentEdge.To);
if (!passed)
{
_uniqPassedNodesCount++;
if (BranchNBound.Instance.MaxNodesVisited < _uniqPassedNodesCount)
BranchNBound.Instance.RegisterGoodPath(this);
if (_uniqPassedNodesCount == _totalNodesCount)
BranchNBound.Instance.PathNode = this;
}
_totalPassedNodesCount++;
var totalDistFromStartMin = float.MaxValue;
var totalDistFromStartMax = float.MinValue;
foreach (var edge in _currentEdge.To.Edges)
{
var dist = edge.To.DistanceFromStart;
var nextNodePassedCount = CountPassed(edge.To);
if (nextNodePassedCount > 0)
dist *= nextNodePassedCount + 2;
if (totalDistFromStartMin > dist)
totalDistFromStartMin = dist;
if (totalDistFromStartMax < dist)
totalDistFromStartMax = dist;
}
var delta = totalDistFromStartMax - totalDistFromStartMin;
if (delta == 0)
delta = totalDistFromStartMax;
foreach (var edge in _currentEdge.To.Edges)
{
if (BranchNBound.Instance._ignoreDeadEnds && edge.To.IsDeadEnd)
continue;
var deltaGoodFromStart = 1 - (edge.To.DistanceFromStart - totalDistFromStartMin) / delta; // + float.Epsilon;
if (float.IsNaN(deltaGoodFromStart))
{
var test = 1;
}
MoveNextEdge(edge, deltaGoodFromStart);
}
}
private void MoveNextEdge(Edge edge, float deltaGoodFromStart)
{
var nextNodePassedCount = CountPassed(edge.To);
var progressScale = (float) _uniqPassedNodesCount / _totalNodesCount; //weight 200 :Total path search progress (how much it is completed/finished)
var nextNodeScoreScale = 1f / (nextNodePassedCount * nextNodePassedCount + 1); //weight 200 :Lower value if next node was visited more times
var pc = _uniqPassedNodesCount;
if (nextNodePassedCount == 0)
pc++;
var pathNoRepeatedNodesScoreScale = (float) pc / (_totalPassedNodesCount + 1); //weight 400 :Higher value if all nodes was visited less times
var progressScaleValue = progressScale * 1;
var nextNodeScoreValue = nextNodeScoreScale * 300;
var deltaGoodFromStartValue = deltaGoodFromStart * 500 * nextNodeScoreScale;
var pathNoRepeatedNodesScoreValue = pathNoRepeatedNodesScoreScale * 800;
//iterations with bigger score will be processed earlier
var totalScore = progressScaleValue +
nextNodeScoreValue +
deltaGoodFromStartValue +
pathNoRepeatedNodesScoreValue;
var dbg = $"Progress: {progressScaleValue} NextNode({edge.To.Id}): {nextNodeScoreValue} GoodStart: {deltaGoodFromStartValue} NoRepeat: {pathNoRepeatedNodesScoreValue}";
var newStep = new BbIterationStep(this, edge, dbg, totalScore);
BranchNBound.Instance.AddStep(newStep, totalScore);
}
public bool CheckPassed(Node node)
{
var checkStep = this;
do
{
if (checkStep.Node == node)
return true;
checkStep = checkStep.Parent;
} while (checkStep != null);
return false;
}
public void GetPathEdges(List<Edge> result)
{
var checkStep = this;
do
{
result.Add(checkStep._currentEdge);
checkStep = checkStep.Parent;
} while (checkStep != null);
}
private int CountPassed(Node node)
{
var passedCount = 0;
var checkStep = this;
do
{
if (checkStep.Node == node)
passedCount++;
checkStep = checkStep.Parent;
} while (checkStep != null);
return passedCount;
}
public override string ToString()
{
return Parent == null ? Id.ToString() : $"({Score}) ({VariantId}), {Debug}";
}
public string GetPath()
{
return Parent == null ? Id.ToString() : $"{Parent.GetPath()}-{Id}";
}
}
}
Most interesting part is MoveNextEdge function that calculates a score for each permutation.