Как определить долгий авиамаршрут?

Question

[Иван Веков]

Допустим есть цель полетать на самолете и потратить наибольшее кол-во времени. И для большей простоты картины забудем про время, имеем только даты и предположим что каждый самолет летит 1 день.
Например есть у нас информация, что имеются следующие аэропорты:

• SVO
  
• MAD
  
• DME
  
• BAR
  
• LON
  

И следующие перелеты:

• SVO -> MAD 2018-06-10
  
• SVO -> BAR 2018-06-12
  
• MAD-> DME 2018-06-16
  
• MAD-> BAR 2018-06-17
  
• BAR -> LON 2018-06-18
  
• DME -> LON 2018-06-19
  

Answer 1

[Иван Веков]

Вдруг кому то пригодится. В итоге красивого решения не обнаружил, похоже его и нет. Сделал следующим образом:

$Longest_Path = new CLongestPathBuilder($routes); // создаем экземпляр класса
$Longest_Path -> printLongestPath(); // выводим информацию о самом долгом маршруте



Class CLongestPathBuilder
{
	protected $arResult = [];
	protected $iterator = 0;

	function __construct($routes)
	{
		// Sorting routes array by date (dt_start field)
		try
		{
			$this->arResult['routes'] = CExtraTools::sortArrayByDate($routes);
		}
		catch(Exception $e)
		{
			echo $e->GetMessage();
			exit(1);
		}

		foreach($this->arResult['routes'] as $route)
		{
			$this->arResult['path'][$this->iterator]['full_path'] .= $route['start'].' -> '.$route['finish'];
			$this->arResult['path'][$this->iterator]['routes_count'] = 1; 
			// Trying to find all available routes from last destination ($route['finish'])
			$this->getRoutes($route);
			$this->iterator++;
		}
	}

	protected function getRoutes($route1)
	{
		// Get available routes from last destination
		if(!$this->arResult['path'][$this->iterator]['prev_date'])
		{
			$this->arResult['path'][$this->iterator]['prev_date'] = $route1['dt_start'];
		}
		foreach($this->arResult['routes'] as $route2) 
		{
			if( ($route1['start'] != $route2['start']) && ($route1['finish'] == $route2['start']) && ($this->arResult['path'][$this->iterator]['prev_date'] < $route2['dt_start']) )
			{
				$this->arResult['path'][$this->iterator]['full_path'] .= ' -> '.$route2['finish'];
				$this->arResult['path'][$this->iterator]['days'] += CExtraTools::diffDates($route1['dt_start'], $route2['dt_start']);
				$this->arResult['path'][$this->iterator]['dates'][] = $route1['dt_start'].' - '.$route2['dt_start'];
				$this->arResult['path'][$this->iterator]['prev_date'] = $route2['dt_start'];
				$this->arResult['path'][$this->iterator]['routes_count']++; // Number of routes in the path
				$this->setLongest($this->arResult['path'][$this->iterator]['days']); // Setting current path as the longest one
				$this->getRoutes($route2);
			}
		}
	}

	protected function setLongest($duration)
	{
		// a function used to set longest path
		if($duration > $this->arResult['longest_path']['days'])
		{
			$this->arResult['longest_path'] = $this->arResult['path'][$this->iterator];
		}
	}

	public function getLongest()
	{
		// a function used to get longest path
		return $this->arResult['longest_path'];
	}

	public function getPaths()
	{
		// a function used to get longest path
		return $this->arResult['path'];
	}

	public function printAllPaths()
	{
		CExtraTools::pre($this->arResult['path']);
	}

	public function printLongestPath()
	{
		CExtraTools::pre($this->arResult['longest_path']);
	}
}



Class CExtraTools
{
	public static function diffDates($date1, $date2)
	{
		// The function to count the difference between two dates
		try
		{
			$datetime1 = new DateTime($date1);
			$datetime2 = new DateTime($date2);
		}
		catch (Exception $e) {
			echo $e->getMessage();
			exit(1);
		}
		$interval = $datetime1->diff($datetime2);
		return $interval->invert ? $interval->days*(-1) : $interval->days;
	}

	public static function pre($var)
	{
		// modification of print_r method
		echo '<pre>';
		print_r($var);
		echo '</pre>';
	}

	protected static function cmp($a, $b)
	{
		// only to sort array in sortArrayByDate() function
		if ($a['dt_start'] == $b['dt_start']) {
			return 0;
		}
		return ($a['dt_start'] < $b['dt_start']) ? -1 : 1;
	}

	public static function sortArrayByDate($array)
	{
		// Sort array by date (dt_start field)
		if(!is_array($array))
		{
			throw new Exception('Должен быть передан массив');
		}
		usort($array, "self::cmp");
		return $array;
	}
}

Answer 2

[sim3x]

https://ru.wikipedia.org/wiki/Задача_о_самом_длинн...

Answer 3

[Сергей]

Рискну предположить, я вижу это так:

0. Берем данные в массив, сортируем массив по дате.
1. Берем самую малую дату - аэропорт вылета (SVO), запоминаем в переменную
2. Берем самую большую дату - аэропорт прелета. (DME), запоминаем в переменную
3. Далее (понимаем, что оба аэропорта в Москве, и бомжуем 9 дней.) - т.е. break; (если мы берем под "долгий" - время, а не "время полетов") Если нет, то:
4. Первый элемент массива = первый рейс в любом случае, берем аэропорт прилета.
5. Перебор массива по порядку со второго элемента (key = 1, а не 0), проверяем все элементы на условие "если аэропорт вылета = последнему аэропорту прилета", если таких несколько, то рекурсия этой же функции (строим несколько маршрутов в этом случае) и так до конца, пока не выполнятся все рекурсии.
6. после Берем все собранные маршруты, смотрим, если последний аэропорт не соответствует данным из пункта 2 (аэропорт прилета - DME) - то удаляем эти маршруты.
7. Из оставшихся смотрим, какой из маршрутов имеет больше рейсов и\или чья дата последнего рейса больше (зависит от того, что мы берем под "долгий" - время полета или количество рейсов)

Не претендую на самое оптимальное решение, наверное, если включить какую математику, то, возможно, можно сделать анализ быстрее\лучше\красивее.