Получение списка номеров рейсов из траектории полета


Ниже \$o(П^3)\$. Я уверен, что есть способ улучшить это..

//vector<string> flight_path; given as parameter
//vector<int> flight_number; need to fill
//vector<segment> flight_segments; known, contains segments (dep, arr, flightnum)

//Purpose of the function is to take in a flight_path and give back a list of
// flight numbers for each segment
//
// Input: New York, London, Kolkata
// Output: 101 201 301, 102 939

vector<string> get_flight_numbers (vector<string> flight_path) {

    vector<int> flight_number;

    for (int i = 0; i < flight_path.size() - 1; i++) {

        string dep = flight_path.at(i);
        string arr = flight_path.at(i+1);

        for (int j = 0; j < flight_segments.size(); j ++) {
            if (flight_segments.at(j).departure == dep && flight_segments.at(j).arrival == arr) {
                for (int k = 0; k < flight_segments.at(j).segment_numbers.size(); k++) {
                    flight_numbers.push_back(atoi(flight_segments.at(j).segment_numbers.at(k).c_str()));
                }
            }
        }

    }
}


549
13
задан 16 февраля 2011 в 04:02 Источник Поделиться
Комментарии
1 ответ

Если я все правильно понимаю, у вас есть направленный граф, который состоит из серии сегментов полета. Вы получаете ряд сегментов полета, скажем, А -> Б -> С, что делает путь полета.

Кроме того, у вас есть группа из числа полета. Номера рейсов соответствовать пути. Количество полетов 1 будут помечены как [А,B,1], например. Время не является проблемой, все рейсы, как предполагается, будут доступны в любое время.

Вы можете, в менее \$o(П^3)\$ время, выяснить, что номера рейсов можно добраться от одного этапа к следующему?

Ну, на подходе может быть, чтобы пройти через массив только один раз для того, чтобы отделить все рейсы, которые вылетают из вашего первого выхода на посадку, вторые врата вылета, и так далее. Это Порядка N.

Затем пройти через каждый из этих списков (один раз) и удалить все полеты, которые не имеют право ворота назначения. Это приказ N раз.

В этот момент, ты очень много сделал.

Так что думаю, что ваша большая ошибка здесь проходит свой большой цикл (полеты) внутри маленькая петля (пути полета). Вы будете гораздо лучше, пройдя через маленькую петлю внутри Большой петли и ломать, если вы найдете совпадение. Этот цикл гнездится только один раз, также, вместо двух раз. Если вы действительно хотели, вы могли бы проверить каждый отъезд, Как вы найдете его, чтобы увидеть, если он совпадает с приходом.

В псевдо-код:

for (i in each flight) do
for (j in each pathpoint except the last one) do
if flight[i][departure][i] == pathpoint[j] then
if flight[j][arrival] == pathpoint[j+1]
put flight in the good flights vector
end if
end if
end for
end for

Это \$О(Н*м)\$, где \$М$ - это длина пути, N-количество рейсов. Это должно быть, в любом разумном мире, \$О(П)\$.

9
ответ дан 16 февраля 2011 в 07:02 Источник Поделиться