Блог

Главная - Вопросы по программированию - PHP упражнение самый дешевый рейс

PHP упражнение самый дешевый рейс

#php

#php

Вопрос:

Поэтому я хочу найти самый дешевый рейс с таким количеством остановок, сколько необходимо в функции PHP.

 $flights = [
["departure" => "BRI", "arrival" => "BDS", "price" => 20],
["departure" => "BRI", "arrival" => "ANC", "price" => 5],
["departure" => "ANC", "arrival" => "CRV", "price" => 3],
["departure" => "CRV", "arrival" => "BDS", "price" => 4],
["departure" => "CRV", "arrival" => "BRI", "price" => 2],
["departure" => "CRV", "arrival" => "XLR", "price" => 3],
["departure" => "SUF", "arrival" => "BDS", "price" => 5],
["departure" => "FLR", "arrival" => "NAP", "price" => 10],
["departure" => "FLR", "arrival" => "BDS", "price" => 1],
["departure" => "FLR", "arrival" => "FRA", "price" => 5],
["departure" => "NAP", "arrival" => "CRV", "price" => 12],
["departure" => "NAP", "arrival" => "BDS", "price" => 16],
["departure" => "NAP", "arrival" => "FLR", "price" => 1],
["departure" => "XLR", "arrival" => "BRI", "price" => 3],
["departure" => "BOL", "arrival" => "FRA", "price" => 3],
["departure" => "BOL", "arrival" => "FLR", "price" => 10],
["departure" => "FRA", "arrival" => "NAP", "price" => 3],

Предполагая, что в этой таблице функция с «BRI» —> «BDS» должна дать мне «12» (BRI-> ANC, ANC-> CRV CRV-> BDS)

 function giveMeLower($departure, $arrival) { global $flights; $price = 0;

foreach ($flights as $flight) {
    if (($flight["departure"] == $departure) and ($flight["arrival"] == $arrival)) {
        $price = $flight["price"];
    }
}

foreach ($flights as $volo) {
    if (($volo["departure"] == $departure)) {

        $tempPrice = $volo["price"];
        $scalo = $volo["arrival"];

        foreach ($flights as $volo_int) {
            if (($volo_int["departure"] == $scalo) and $volo_int["arrival"] == $arrival) {
                $tempPrice  = $volo_int["price"];
                if ($tempPrice < $price || $price == 0) {
                    $price = $tempPrice;
                }
            }
        }
    }
}

return $price == 0 ? "No flight found" : $price;
}

Это то, что я пробовал, это работает, но только с одной остановкой.

Какое-нибудь предложение, чтобы оно продолжалось как можно дольше?

Спасибо!

Комментарии:

1. Ваш код проверяет только одну точку остановки. Сначала вы проверяете наличие прямого соединения, затем ищете один подходящий рейс, выбираете пункт назначения, просматриваете и проверяете, соответствует ли второе прибытие вашему пункту назначения, и, если цена работает, оно завершается. Тем не менее, ваш код возвращает «20» для меня, но я подозреваю, что он вернул бы другую цену, если бы у вас была связь между «ANC» и «BDS». Ваша рекурсия должна будет проверить цикл и, конечно, возможность отсутствия альтернативного маршрута. Или вообще никакого маршрута.

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

3. Будет интересно посмотреть, что другие предлагают для этого, теперь я думаю об этом дальше. Если вы сядете и выпишете все возможные варианты от руки, даст ли это вам какие-нибудь подсказки относительно наилучшего способа его кодирования?

4. Я думал о чем-то рекурсивном, например, продолжайте проверять, присутствует ли текущий рейс [«прибытие»] в таблице вылета, и продолжайте проверять, пока текущий рейс [«прибытие»] не будет равен $ arrival, но я не могу заставить его работать

5. Если вам нужен наиболее оптимизированный способ сделать это, вы могли бы взглянуть на алгоритм Беллмана Форда en.wikipedia.org/wiki/Bellman–Ford_algorithm

Ответ №1:

Юя Аратани, я думаю, проделал отличную работу над этим. Адаптация по алгоритму Дейкстры.

Класс «Graph» прост и эффективен. И он выполняет именно ту работу, которую вы хотите!

 require 'src/Graph.php';

$graph = TanikoDijkstraGraph::create();

$graph
    ->add('BRI', 'BDS', 20)
    ->add('BRI', 'ANC', 5)
    ->add('ANC', 'CRV', 3)
    ->add('CRV', 'BDS', 4)
    ->add('CRV', 'BRI', 2, false)
    ->add('CRV', 'XLR', 3)
    ->add('SUF', 'BDS', 5)
    ->add('FLR', 'NAP', 10)
    ->add('FLR', 'BDS', 1)
    ->add('FLR', 'FRA', 5)
    ->add('NAP', 'CRV', 12)
    ->add('NAP', 'BDS', 16)
    ->add('NAP', 'FLR', 1)
    ->add('XLR', 'BRI', 3, false)
    ->add('BOL', 'FRA', 3)
    ->add('BOL', 'FLR', 10)
    ->add('FRA', 'NAP', 3);

$route = $graph->search('BRI', 'BDS');
$cost  = $graph->cost($route);

ВОЗВРАТ

 var_dump($route);//array(4) { [0]=> string(3) "BRI" [1]=> string(3) "ANC" [2]=> string(3) "CRV" [3]=> string(3) "BDS" }
echo $cost;//12