Как отсортировать коллекцию на основе следующего свойства?

Question

Я пытаюсь рассчитать лучший маршрут между всеми остановками с GeoCoordinates в C #.

У меня есть несколько методов, которые получают следующее ближайшее местоположение в списке, но мне нужно иметь возможность сортироватьМой оригинальный список:

start -> next stop -> next stop -> next stop -> finish

---

Вот с чем я сейчас работаю:

Модели

public class DispatchStopModel
{
    public long OrderDispatchID { get; set; }
    public long? NextDispatchID { get; set; }
    public PhysicalAddress PhysicalAddress { get; set; }
    public double Distance { get; set; }
}

Методы

    private static double DistanceTo(double lat1, double lon1, double lat2, double lon2, char unit = 'M')
    {
        double rlat1 = Math.PI * lat1 / 180;
        double rlat2 = Math.PI * lat2 / 180;
        double theta = lon1 - lon2;
        double rtheta = Math.PI * theta / 180;
        double dist =
            Math.Sin(rlat1) * Math.Sin(rlat2) + Math.Cos(rlat1) *
            Math.Cos(rlat2) * Math.Cos(rtheta);
        dist = Math.Acos(dist);
        dist = dist * 180 / Math.PI;
        dist = dist * 60 * 1.1515;

        switch (unit)
        {
            case 'K': //Kilometers -> default
                return dist * 1.609344;
            case 'N': //Nautical Miles 
                return dist * 0.8684;
            case 'M': //Miles
                return dist;
        }

        return dist;
    }

    private void FindClosestStop(DispatchStopModel start, ICollection<DispatchStopModel> stops)
    {
        if(start.PhysicalAddress?.HasGeocode ?? false)
        {
            foreach(var stop in stops.Where(s => s.OrderDispatchID != start.OrderDispatchID))
            {
                if(stop.PhysicalAddress?.HasGeocode ?? false)
                {
                    double distanceTo = DistanceTo((double)start.PhysicalAddress.Latitude, (double)start.PhysicalAddress.Longitude, (double)stop.PhysicalAddress.Latitude, (double)stop.PhysicalAddress.Longitude);

                    if (distanceTo < start.Distance)
                    {
                        start.Distance = distanceTo;
                        start.NextDispatchID = stop.OrderDispatchID;
                    }
                }
            }
        }
    }

---

Теперь вот мое действие контроллера:

public IActionResult GetDeliveries()
{
    var deliveries = deliveryService.GetYourDeliveries();

    var Stops = Deliveries.Select(d => new DispatchStopModel
    {
        OrderDispatchID = d.OrderDispatchID,
        NextDispatchID = null,
        PhysicalAddress = d.Order.OrderAddress?.PhysicalAddress,
        Distance = double.MaxValue
    })
    .ToArray();


    foreach(var stop in Stops)
    {
        FindClosestStop(stop, Stops);
    }

    //How can I sort on deliveries using the "NextDispatchID" from the collection I just generated?
}

---

Я думал, что могу настроить новый список,и вручную вставьте каждую поставку, где OrderDispatchID равен OrderDispatchID остановки.Я чувствую, что это было бы неэффективно.

Мысли о правильном способе сделать это?

Заранее спасибо,

Answer 1

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

Если это так, один из способовустановить «следующий» элемент для каждого элемента: сделать копию всех остановок, пройтись по исходному списку остановок, назначить ближайший экземпляр в списке на каждой итерации, а затем удалить этот элемент из списка, чтобыбольше не назначается:

List<DispatchStopModel> deliveries = deliveryService.GetYourDeliveries();
List<DispatchStopModel> temp = deliveries.ToList();

// Assuming you have a start location
DispatchStopModel start = GetStartingPoint();

// Assign the closest stop to it
FindClosestStop(start, deliveries);

// Now assign the closest delivery for each of the rest
// of the items, removing the closest item on each
// iteration, so it doesn't get assigned more than once.
foreach (var delivery in deliveries)
{
    var closest = FindClosestStop(delivery, temp);
    temp.Remove(closest);
}

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

Обратите внимание, что я сделалнебольшое изменение на FindClosestStop, чтобы он возвращал ближайший найденный стоп:

private DispatchStopModel FindClosestStop(DispatchStopModel start, 
    ICollection<DispatchStopModel> stops)
{
    DispatchStopModel closest = null;

    // other code ommitted for brevity

    if (distanceTo < start.Distance)
    {
        start.Distance = distanceTo;
        start.NextDispatchID = stop.OrderDispatchID;
        closest = stop;
    }

    // other code ommitted for brevity

    return closest;
}

Также обратите внимание, что Equals и GetHashCode должны быть переопределены в классе DispatchStopModel для метода Remove дляработай.Если вы не хотите этого делать, вам нужно найти элемент с соответствующим значением OrderDispatchID и удалить его таким образом.