Задача коммивояжера для графа дерева (без гамильтонова пути)

Question

Почти сломал голову, пытаясь найти алгоритм, который находит самый быстрый маршрут в графе, который проходит через ВСЕ вершины графа из начальной вершины (без необходимости возврата к начальному ребру).

Я проверил все основные алгоритмы для графиков и аналогичных задач на stackoverflow.

Почти все примеры TSP, которые я гуглил, были для полных графиков.

TSPLIB не похоже, может решить мою проблему.

Извините, если что-то пропустил.

График ввода (проверьте изображения):

• Взвешенный

• Ненаправленный

• Планарный

• Нет гамильтонова траектории

• Нет отрицательных ребер

• Размер: до 100 вершин (но обычно50-70)

Длина грани на графике почти одинакова, поэтому мы можем сказать, что это невзвешенный граф, и взять длину 1 равной.

Должен быть решен с помощью "тупика"случаи:

Реальные входные графики выглядят так (начиная с вершины 0):

Большой график:

Ожидаемый результат:

• Кратчайший путь (набор индексов вершин) через все ребра от начального ребра.

• Нет необходимости возвращаться к начальному ребру в конце

Получил только одну идею:

1) Проверьте все возможные комбинации пути, измерьте расстояние и найдите путь с наименьшим расстоянием.

1a) Use Поиск в глубину или поиск в ширину

1b) Если при выполнении итерации у текущей вершины более одного ребра - создайте отдельные комбинации для всех из них (попробуйте все возможные способы).

1c) В моем случае существует много «тупиков» в графе, поэтому алгоритм должен найти путь (самый быстрый из них) оттуда и перебрать уже пройденные вершины и не застрять.

2)Восстановите путь

Может быть, я должен использовать здесь алгоритм Minimum Spanning Trees…

Или, возможно, для более быстрого вычисления я должен разделить мой график на несколько наименьших, которые связаны только с одним ребром (например, 49-52, 40-41 на скриншоте)

Буду признателен за любую помощь.

Предпочитаю примеры C # (libs), но я могу переносить код с любого языка.

Answer 1

В моем случае эта NP-трудная задача должна решаться как можно быстрее, а не так идеально, поэтому я использовал для меня лучшее решение (упрощенная версия) (лучший сценарий должен быть O (n + n * m), n- узлов, m - ребер):

• Используйте поиск в ширину (BFS), чтобы найти самый глубокий (дальний) узел от начала (давайте назовем его FAR_NODE) ​​
• Использовать алгоритм Djkstraрассчитать расстояние от FAR_NODE до всех остальных узлов (на самом деле я тоже использовал алгоритм BFS, потому что для евклидова пространства это быстрее и дает тот же результат) ... так что просто сохраните расстояние во всех узлах из FAR_NODE.
• Начните проходить по графику от начального узла до ближайшего не пройденного, предпочитайте узлы с большим «расстоянием от FAR_NODE»
• Если нет не пройденных узлов, связанных с текущим узлом - выберите ближайший непроходный узел (предпочтительно сс наибольшим значением «расстояние») (также можно использовать 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, которая вычисляет оценку для каждой перестановки.