алгоритм поиска пути для поиска маршрутов из одного места в другое - PullRequest
Новая
       32

алгоритм поиска пути для поиска маршрутов из одного места в другое

0 голосов
/ 18 ноября 2018

У меня есть 2 таблицы schedules и places.

Моя schedules таблица выглядит следующим образом 

- Id
- From Place Id
- To Place Id
- Departure Time
- Arrival Time

Моя places таблица выглядит следующим образом 

- Id
- Name

Например: когда пользователь ищет маршруты от place_id 5 до place_id 1, система должна вернуть массив маршрутов, который содержит массив расписаний.Это расписание, например, может выглядеть следующим образом: 

[
    {
         from_place_id: 5,
         to_place_id: 3,
         ...
    },
    {
         from_place_id: 3,
         to_place_id: 8,
         ...
    },
    {
         from_place_id: 8,
         to_place_id: 1,
         ...
    },
]

Я знаю, что существует много алгоритмов, таких как поиск в ширину, поиск в глубину и т. Д. Я никогда не делал их с помощью Eloquent Laravel.Пожалуйста, некоторые дают мне советы по достижению результатов.Есть много сайтов, которые рассказывают о различных доступных алгоритмах, но ни один из них не объясняет это.

Ответы [ 2 ]

0 голосов
/ 19 ноября 2018

В соответствии с тем, что я понимаю из вашего вопроса, попробуйте этот код: 

$schedules = Schedule::where('from_place_id', '!=', $from_place_id)->where('to_place_id', '!=', $to_place_id)->get();

$roots = Schedule::where('from_place_id', $from_place_id)->get();
$goals = Schedule::where('to_place_id', $to_place_id)->get();

$stack = ['schedules' => []];

foreach ($roots as $root) {
    $travelTime = date('H:i:s', $this->timeDiff($root->departure_time, $root->arrival_time));
    $root['travel_time'] = $travelTime;
    $child = [$root];

    $requiredTime = $this->timeDiff($departure_time, $root->departure_time);

    if ($requiredTime >= 0) {
        foreach ($schedules as $schedule) {
            $previous = $child[count($child) - 1];

            $timeDiff = $this->timeDiff($previous->arrival_time, $schedule->departure_time);

            if ($schedule->from_place_id == $previous->to_place_id &&
        $timeDiff >= 0 && $timeDiff <= 3600) {
                $travelTime = date('H:i:s', $this->timeDiff($schedule->departure_time, $schedule->arrival_time));
                $schedule['travel_time'] = $travelTime;
                array_push($child, $schedule);

                foreach ($goals as $goal) {
                    $goalTimeDiff = $this->timeDiff($schedule->arrival_time, $goal->departure_time);

                    if ($goal->from_place_id == $schedule->to_place_id &&
                    $goalTimeDiff >= 0 && $goalTimeDiff <= 3600) {
                        $travelTime = date('H:i:s', $this->timeDiff($goal->departure_time, $goal->arrival_time));
                        $goal['travel_time'] = $travelTime;
                        array_push($child, $goal);
                        array_push($stack['schedules'], $child);
                        break 2;
                    }
                }
            }
        }
    }
}

return $stack;

Также вам необходимо создать новую защищенную функцию для timeDiff, которая выглядит следующим образом 

protected function timeDiff($first, $second)
{
    return Carbon::parse($first)->diffInSeconds(Carbon::parse($second), false);
}

Не забудьте импортировать Carbon и Schedule вверху.

0 голосов
/ 19 ноября 2018

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

В этом случае вы можете использовать bfs или dfs.Но IMO, лучше использовать bfs, потому что dfs не применим для поиска кратчайшего пути в графе, основанном на расстоянии.В случае, если в будущем вы будете применять расстояние в таблице расписания.

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

...