php - MySQL查询以获取旅行路线

Question

我有下表:

+--------+----------+---------+---------+---------
|  From  |    To    |Departure| Arrival |   ID   | 
+--------+----------+---------+---------+---------
|   A    |    B     |   0900  |   0930  |   1    | 
+--------+----------+---------+---------+---------
|   C    |    D     |   1000  |   1030  |   2    | 
+--------+----------+---------+---------+---------
|   B    |    C     |   1100  |   1130  |   3    | 
+--------+----------+---------+---------+---------
|   D    |    E     |   1200  |   1230  |   4    | 
+--------+----------+---------+---------+---------
|   C    |    D     |   1300  |   1330  |   5    | 
+--------+----------+---------+---------+---------

• 出发/到达时间和ID总是递增的；
  
• C_D可以在B_C之前和之后找到。
  
  

我想从A到D，所以旅行路线应该是ID1，ID3， ID5 或 A_B 、B_C、C_D。

任何帮助表示赞赏。
谢谢。

Answer 1

您可以在存储过程中解决这个问题。但是当由编程语言在内存中执行时，该算法可能会更快。只需确保加载了完整的数据集，这样就不必在每次迭代时都执行查询。

伪代码:

to = 'D'
prev_to = 'A'
array = array();
while (prev_to != 'D') {
  select arrival, to into prev_arrival, prev_to
  from table 
  where departure > prev_arrival 
  and from = prev_to;

  array[] = [arrival => prev_arrival, to => prev_to]
}

return array

编辑:我想我没有更好的事情可做；)

此类将搜索给定开始时间和结束时间之间从 A 到 D 的所有路线。就像公共(public)交通应用程序一样。您可能希望使用自己的数据库连接方法。 (只是不要再使用 mysql_* 函数了)

<?php

class RoutePlanner
{
    /** @var string */
    protected $departureTime;
    /** @var string */
    protected $departureLocation;
    /** @var string */
    protected $arrivalTime;
    /** @var string */
    protected $arrivalLocation;
    /** @var array */
    protected $schedule;
    /** @var mysqli */
    protected $db;

    /**
     * @param string $departureTime
     * @param string $departureLocation
     * @param string $arrivalTime
     * @param string $arrivalLocation
     * @throws InvalidArgumentException
     */
    public function __construct($departureTime, $departureLocation, $arrivalTime, $arrivalLocation)
    {
        $this->departureTime = $departureTime;
        $this->departureLocation = $departureLocation;
        $this->arrivalTime = $arrivalTime;
        $this->arrivalLocation = $arrivalLocation;
    }

    /**
     * @return array
     */
    public function getRoutes()
    {
        $schedule = $this->fetchSchedule();
        $routes = $this->searchRoutes($schedule);
        return $routes;
    }

    /**
     * Search all routes that start and end between given times
     * @param array $schedule - passing as parameter to ensure the order of execution
     * @return array
     */
    protected function searchRoutes(array $schedule)
    {
        $routes = array();

        foreach ($schedule as $i => $row)
        {
            if ($row['from'] == $this->departureLocation)
            {
                $routes[] = $this->getRoute($schedule, $i);
            }
        }

        return $routes;
    }

    /**
     * Get the route when starting at given point and time
     * @param $schedule
     * @param $start
     * @return array
     */
    protected function getRoute($schedule, $start)
    {
        $steps = array();

        $from = $this->departureLocation;
        $time = $this->departureTime;

        for ($i = $start; $i < count($schedule); $i++)
        {
            $row = $schedule[$i];
            if ($row['from'] == $from && $row['departure'] > $time)
            {
                $steps[] = $row;
                $from = $row['to'];
                $time = $row['arrival'];
            }
        }

        return $steps;
    }

    /**
     * @return array
     */
    protected function fetchSchedule()
    {
        if (! empty($this->schedule))
            return $this->schedule;

        $sql = "select * from schedule where departure >= ? and arrival <= ?";

        $db = $this->getDatabase();
        $statement = $db->prepare($sql);
        $statement->bind_param("ss", $this->departureTime, $this->arrivalTime);
        $statement->execute();
        $result = $statement->get_result();

        $this->schedule = $result->fetch_all(MYSQLI_ASSOC);

        $statement->close();
        $result->free();

        return $this->schedule;
    }

    /**
     * @return mysqli
     */
    protected function getDatabase()
    {
        if (empty($this->db))
            $this->db = new mysqli('localhost', 'user', 'pass', 'database');

        return $this->db;
    }

    public function __destroy()
    {
        if (! empty($this->db))
            $this->db->close();
    }
}

像这样使用:

<?php

$planner = new RoutePlanner('Amsterdam', '0300', 'Berlin', '1030');
$routes = $planner->getRoutes();