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

Question

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

У меня 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,
...
},
]

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

1

algorithm laravel mysql path-finding php

Решение

Другие решения

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

$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 на вершине.

1

Источник

Accepted Answer

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

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

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

1