树图的旅行商问题（无哈密顿路径）

Question

在试图找到算法时几乎打破了我的头，该算法在图中找到最快的路线，从起始顶点穿过所有图形顶点（无需返回到起始边）。

我在stackoverflow上查了图的所有主要算法和类似的问题。

我用谷歌搜索的几乎所有 TSP 示例都是完整的图表。

TSPLIB 貌似不能解决我的问题

对不起，如果我错过了什么。

输入图（检查图像）：

• 加权

• 无向

• 平面

• 没有汉密尔顿路径

• 无负边缘

• 大小：最多 100 个顶点（但通常为 50-70）

图中的边长几乎相同，所以我们可以说这是一个未加权的图，边长为1。

应该解决“死胡同”的情况：

真实的输入图看起来像这样（从顶点 0 开始）：

大图：

预期结果：

• 从起始边开始通过所有边的最短路径（一组顶点索引）。

• 结束时无需返回起始边

只有一个想法：

1）检查所有可能的路径组合，测量距离并找到距离最小的路径。

1a) 使用深度优先搜索或广度优先搜索

1b) 如果在迭代时当前顶点有多个边 - 对所有边进行单独组合（尝试所有可能的方法）。

1c) 在我的例子中，图中有很多“死胡同”，所以算法应该从那里找到方法（最快的 ofc）并迭代已经通过的顶点而不会卡住。

2) 重构路径

也许我也应该在这里使用最小生成树算法……

或者也许为了更快的计算，我应该将我的图形拆分为多个最小的，仅与单边链接（如屏幕截图中的 49-52、40-41）

任何帮助将不胜感激。

更喜欢 C# 示例（库），但我可以从任何语言移植代码。

Answer 1

我的情况是这个 NP-hard 问题应该尽快解决而不是那么完美，所以我使用了对我来说最好的解决方案（简化版）（最好的情况应该是 O(n+n*m)，n - 节点, m - 边):

• 使用广度优先搜索 (BFS) 从一开始就找到最深（远）的节点（我们称之为 FAR_NODE）
• 使用 Djkstra 算法计算从 FAR_NODE 到所有其他节点的距离（实际上我在这里也使用 BFS 算法，因为对于欧几里得空间它更快并且给出相同的结果）......所以只需保存所有节点从 FAR_NODE 的距离。
• 开始遍历图表，从起始节点到最近未通过的节点，更喜欢“与 FAR_NODE 的距离”较大的节点
• 如果没有链接到当前节点的未通过节点 - 选择最近的未通过节点（首选具有最大“距离”值）（也可以使用 BFS）。

算法在这里发布和记录（带动画）：https://github.com/Stridemann/TravelShortPathFinder

================================================= ==

使用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 函数，它计算每个排列的分数。