树图的旅行商问题(无汉密尔顿路径)
Travelling salesman problem for a tree graph (no hamiltonian path)
在试图找到算法时我几乎要崩溃了图形中从起始顶点穿过所有图形顶点的最快路线(不需要return开始边)。
我在Whosebug上检查了所有主要的图形算法和类似问题。
我用谷歌搜索的几乎所有 TSP 示例都是完整的图表。
TSPLIB 貌似不能解决我的问题
抱歉,如果我遗漏了什么。
输入图表(检查图像):
• 加权
• 未定向
• 平面
• 无汉密尔顿路径
• 无负边缘
• 大小:最多 100 个顶点(但通常为 50-70)
图中的边长几乎相同,所以我们可以说这是一个未加权的图,边长取1。
应该解决"dead end"个案例:
实际输入图如下所示(从顶点 0 开始):
大图:
预期结果:
• 从起始边开始通过所有边的最短路径(一组顶点索引)。
• 无需 return 在末尾开始边缘
只有一个想法:
1) 检查所有可能的路径组合,测量距离,找到距离最小的路径。
1a) 使用深度优先搜索或广度优先搜索
1b) 如果在迭代时当前顶点有不止一条边 - 对所有边进行单独组合(尝试所有可能的方法)。
1c) 在我的例子中,图中有很多“死胡同”,所以算法应该从那里找到路径(最快的ofc)并迭代已经通过的顶点而不会卡住。
2) 重构路径
也许我也应该在这里使用最小生成树算法……
或者为了更快的计算,我应该将我的图拆分为多个最小的,只与单边链接(如屏幕截图中的 49-52、40-41)
任何帮助将不胜感激。
更喜欢 C# 示例 (libs),但我可以从任何语言移植代码。
我的情况是这个 NP-hard 问题应该尽快解决而不是那么完美,所以我使用了对我来说最好的解决方案(简化版)(最好的情况应该是 O(n+n* m), n - 节点, m - 边):
- 使用 Breadth-first 搜索 (BFS) 从头开始找到最深(远)的节点(我们称之为 FAR_NODE)
- 使用 Djkstra 算法计算从 FAR_NODE 到所有其他节点的距离(实际上我在这里也使用 BFS 算法,因为对于欧几里德 space 它更快并且给出相同的结果)。 . 所以只需保存所有节点中距 FAR_NODE.
的距离
- 从开始节点到最近未通过的节点开始遍历图形,首选更大的节点 "distance from FAR_NODE"
- 如果没有未通过的节点链接到当前节点-选择最近的未通过节点(最好具有最大 "distance" 值)(也可以使用 BFS)。
============================================= ======
使用 Branch&Bound 方式:
正如我在对我的问题的评论中提到的,我几乎以分支绑定的方式解决了这个问题。这个想法是给每个排列和过程一个分数,只有更高的分数。
如果有人感兴趣,这是示例代码:
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}";
}
}
}
最有趣的部分是 MoveNextEdge 函数,它计算每个排列的分数。
在试图找到算法时我几乎要崩溃了图形中从起始顶点穿过所有图形顶点的最快路线(不需要return开始边)。
我在Whosebug上检查了所有主要的图形算法和类似问题。
我用谷歌搜索的几乎所有 TSP 示例都是完整的图表。
TSPLIB 貌似不能解决我的问题
抱歉,如果我遗漏了什么。
输入图表(检查图像):
• 加权
• 未定向
• 平面
• 无汉密尔顿路径
• 无负边缘
• 大小:最多 100 个顶点(但通常为 50-70)
图中的边长几乎相同,所以我们可以说这是一个未加权的图,边长取1。
应该解决"dead end"个案例:
实际输入图如下所示(从顶点 0 开始):
大图:
预期结果:
• 从起始边开始通过所有边的最短路径(一组顶点索引)。
• 无需 return 在末尾开始边缘
只有一个想法:
1) 检查所有可能的路径组合,测量距离,找到距离最小的路径。
1a) 使用深度优先搜索或广度优先搜索
1b) 如果在迭代时当前顶点有不止一条边 - 对所有边进行单独组合(尝试所有可能的方法)。
1c) 在我的例子中,图中有很多“死胡同”,所以算法应该从那里找到路径(最快的ofc)并迭代已经通过的顶点而不会卡住。
2) 重构路径
也许我也应该在这里使用最小生成树算法……
或者为了更快的计算,我应该将我的图拆分为多个最小的,只与单边链接(如屏幕截图中的 49-52、40-41)
任何帮助将不胜感激。
更喜欢 C# 示例 (libs),但我可以从任何语言移植代码。
我的情况是这个 NP-hard 问题应该尽快解决而不是那么完美,所以我使用了对我来说最好的解决方案(简化版)(最好的情况应该是 O(n+n* m), n - 节点, m - 边):
- 使用 Breadth-first 搜索 (BFS) 从头开始找到最深(远)的节点(我们称之为 FAR_NODE)
- 使用 Djkstra 算法计算从 FAR_NODE 到所有其他节点的距离(实际上我在这里也使用 BFS 算法,因为对于欧几里德 space 它更快并且给出相同的结果)。 . 所以只需保存所有节点中距 FAR_NODE. 的距离
- 从开始节点到最近未通过的节点开始遍历图形,首选更大的节点 "distance from FAR_NODE"
- 如果没有未通过的节点链接到当前节点-选择最近的未通过节点(最好具有最大 "distance" 值)(也可以使用 BFS)。
============================================= ======
使用 Branch&Bound 方式:
正如我在对我的问题的评论中提到的,我几乎以分支绑定的方式解决了这个问题。这个想法是给每个排列和过程一个分数,只有更高的分数。
如果有人感兴趣,这是示例代码:
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}";
}
}
}
最有趣的部分是 MoveNextEdge 函数,它计算每个排列的分数。