Поиск в ширину, чтобы найти маршрут между двумя станциями метро

Question

Привет. Я создаю программу для поиска маршрута между двумя станциями лондонского метро.Я использую связанные объекты для представления сети.Таким образом, объект станции содержит: имя, список линий, в которых находится станция, список станций, к которым она примыкает.У меня также есть линейные объекты, которые содержат: название, список станций линии.А также сетевой объект, который содержит список всех станций и список всех линий.

Я думал об использовании поиска в ширину, но не понимаю, как реализовать алгоритм в моей структуре данных.Буду признателен за любую помощь.

Я также использовал другой метод для поиска маршрута, поиска строк источника, если он содержит пункт назначения.Если это не так, то смотрите на соединения в линиях, т.е. на станциях с более чем 1 линией.и глядя на их линии и посмотреть, есть ли пункт назначения в тех.Но после 1 изменения я запутался в том, как сделать больше, чем одно изменение.вот код, который я использовал:

public void finder(String from, String to)
{

    Station source = network.searchStation(from);
    Station destination = network.searchStation(to);
    ArrayList<Line> sourceLines = source.getLines();
    ArrayList<String> routes = new ArrayList<String>();

    for(Line line:sourceLines)
    {
        ArrayList<Station> stations = line.getStations();
        if(stations.contains(destination))
        {
            Station endStart;
            if(stations.indexOf(destination) > stations.indexOf(source))
            {
                endStart = stations.get(stations.size()-1);
            }
            else{
                endStart = stations.get(0);
            }
            routes.add(endStart.getName());
            routes.add(line.getName());
            break;
        }
    }
    if(routes.size() != 0)
    {
        System.out.println("Start: " + from);
        System.out.println("Take the " + routes.get(1) + " line towards " + routes.get(0));
        System.out.println("End: " + to);
    }
    else{
        routes = search(source, destination, routes);
        System.out.println("Start: " + from);
        for(int n = 0; n < (routes.size() / 6);n++)
        {
            System.out.println("Take the " + routes.get(n + 1) + " line towards " + routes.get(n));
            System.out.println("Change at: " + routes.get(n + 2) + " to the " + routes.get(n + 3) + " line");
            System.out.println("Take the " + routes.get(n + 5) + " line towards " + routes.get(n + 4));
        }
        System.out.println("End: " + to);
    }
}

public ArrayList<String> search(Station source, Station destination, ArrayList routes)
{
    ArrayList<Line> sourceLines = source.getLines();
    for(Line line:sourceLines)
    {
        ArrayList<Station> searchList = new ArrayList<Station>();
        ArrayList<Station> lineStations = line.getStations();
        if(line.getVisited() == false)
        {
            for(Station station: lineStations)
            {
                if(station.getLines().size() > 1)
                {
                    searchList.add(station);
                }
            }
        }

        for(Station station:searchList)
        {
            ArrayList<String> stationChanges = new ArrayList<String>();
            ArrayList<Line> lines = station.getLines();
            Station endLine;
            if(lineStations.indexOf(station) > lineStations.indexOf(source))
            {
                endLine = lineStations.get(lineStations.size()-1);
            }
            else{
                endLine = lineStations.get(0);
            }
            stationChanges.add(endLine.getName());
            stationChanges.add(line.getName());
            for(Line stationLine:lines)
            {
                ArrayList<Station> stations = stationLine.getStations();
                if(stations.contains(destination))
                {
                    stationChanges.add(station.getName());
                    stationChanges.add(stationLine.getName());
                    Station endStart;
                    if(stations.indexOf(destination) > stations.indexOf(station))
                    {
                        endStart = stations.get(stations.size()-1);
                    }
                    else{
                        endStart = stations.get(0);
                    }
                    stationChanges.add(endStart.getName());
                    stationChanges.add(stationLine.getName());
                    for(String str:stationChanges)
                    {
                        routes.add(str);
                    }
                    return routes;
                }
                else
                {
                    stationLine.markVisited();
                    search(station,destination,stationChanges);
                }
            }

        }
    }
    return routes;
}

Спасибо

Answer 1

Маршрутизация - это совсем другая проблема.Вам нужно использовать алгоритм Дейкстры или его варианты, простые алгоритмы BFS или алгоритмы обратного отслеживания без особых размышлений могут сбить вас с пути!

Answer 2

Звучит так, как будто у вас нет данных о расходах, поэтому вы должны просто использовать BFS.

Этот пост может дать вам несколько советов: Поиск маршрута в Метрополитене с использованием чистого кода Java

Answer 3

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

Answer 4

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

В конце концов, если вы путешествуете по центральной линии и переходите на северную сторону кСокращая на несколько минут время в пути, вы, скорее всего, потратите больше времени на то, чтобы добраться до платформы северной линии и подождать, пока туда прибудет следующий поезд.Невозможно включить эти затраты в стоимость узла, так как это применимо только к некоторым комбинациям входящих / исходящих вершин на этом узле (и штраф может даже отличаться для разных комбинаций, если вы хотите получить реальную фантазию и оценкуфактическое время, необходимое для смены строк в трубе).

Answer 5

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

Например, если вы идете от соседних станций на одной линии, весит 1, переходя на другую линиювес 2. Если вы хотите перейти от Notthing Hill Gate к Холланд-парку, то общий вес равен 1. Если вы хотите перейти из Бейсуотера в Холланд-парк, то вес равен 4 (1 для станции, 2 для смены линии, 1 длястанция)

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