Вопрос по c#, 2d, geometry, math – Кратчайший маршрут между несколькими точками

-3

Мне нужно найти кратчайший маршрут между несколькими точками. Допустим, у меня есть следующие четыре пункта:

var startPoint = new Point(1, 1);
var pointsToGoPast = new List<Point> { new Point(3,1); new Point(2,4); };
var endPoint = new Point(10, 10);

Итак, я хочу выяснить, какие точки нужно пройти в первую очередь, чтобы получить кратчайший путь от начальной точки до конечной точки.

Может кто-нибудь мне помочь?

Обновление: он должен пройти мимо каждой из точек в списке pointsToGoPast. Стоимость указана даже для каждого маршрута.

Хотите посетить каждую точку или просто найти кратчайший путь? Кратчайший путь легче, посетить каждую точку намного сложнее. Поиск проблемы коммивояжера для обзора сложности. TheEvilPenguin
Возможный дубликатCalculating the shortest route between two points Alex Filatov
Вы можете двигаться из любой точки в любую точку напрямую? Сколько стоит 2 балла? Я бы пошел сen.wikipedia.org/wiki/Dijkstra's_algorithm Imre L
Дейкстра решил эту проблему еще в шестидесятых. Он ушел, вам придется применить его алгоритм самостоятельно:en.wikipedia.org/wiki/Dijkstra%27s_algorithm Hans Passant

Ваш Ответ

4   ответа
3

неясно, какова стоимость перехода из одной точки в другую. Это просто расстояние между этими точками? В любом случае, несмотря на это, такую проблему можно решить с помощью обычного линейного программирования. Я только что закончил создание библиотеки C #, чтобы упростить проблемы кратчайшего пути. ЗагружаемыеВот.

Над этой библиотекой еще много работы, но она должна дать вам то, что вы хотите, очень простым способом.

С Уважением,

Брюс.

6

Пример проекта с кодом здесь

Единственное, что нужно изменить, - это вес в проекте, поскольку вес основан на расстоянии между двумя точками. (Так что вам нужно изменитьLocation хранитьPoint иConnection рассчитать вес (расстояние) в конструкторе.

В Википедии есть очень хорошая статья об алгоритме

2

Алгоритм Дейкстры

{        
        private int rank = 0;
        private int[,] L;
        private int[] C; 
        public int[] D;
        private int trank = 0;
        public Dijkstra(int paramRank,int [,]paramArray)
        {
            L = new int[paramRank, paramRank];
            C = new int[paramRank];
            D = new int[paramRank];
            rank = paramRank;
            for (int i = 0; i < rank; i++)
            {
                for (int j = 0; j < rank; j++) {
                    L[i, j] = paramArray[i, j];
                }
            }

            for (int i = 0; i < rank; i++)
            {
                C[i] = i;
            }
            C[0] = -1;          
            for (int i = 1; i < rank; i++)
                D[i] = L[0, i];
        }
        public void DijkstraSolving()
        {            
            int minValue = Int32.MaxValue;
            int minNode = 0;
            for (int i = 0; i < rank; i++)
            {
                if (C[i] == -1)
                    continue;
                if (D[i] > 0 && D[i] < minValue)
                {
                    minValue = D[i];
                    minNode = i;
                }
            }
            C[minNode] = -1;
            for (int i = 0; i < rank; i++)
            { 
                if (L[minNode, i] < 0)
                    continue;
                if (D[i] < 0) {
                    D[i] = minValue + L[minNode, i];
                    continue;
                }
                if ((D[minNode] + L[minNode, i]) < D[i])
                    D[i] = minValue+ L[minNode, i];
            }
        }
        public void Run()
        {
            for (trank = 1; trank >rank; trank++)
            {
                DijkstraSolving();
                Console.WriteLine("iteration" + trank);
                for (int i = 0; i < rank; i++)
                    Console.Write(D[i] + " ");
                Console.WriteLine("");
                for (int i = 0; i < rank; i++)
                    Console.Write(C[i] + " ");
                Console.WriteLine("");                
            }
        }
 }
2

select geography :: Point(@PointALatitude, @PointALongitude, 4326).STDistance(geography::Point(@PointBLatitude, @PointBLongitude, 4326))

Результат возвращается в метрах, поэтому просто разделите на 1000 для Км или 1609.344 для Миль

Похожие вопросы