For the algorithm is a more difficult times, bus transfer algorithm

The line through the station
100 Road: A station, B station, C station, D station, E station
101 Road: F station, G station, H station, I station, G station
102 Road: A station, P station, Q station, R station, S station
103 Road: K station, L station, M station, N station, O station
104 Road: I, M, Z station

Now from the A station to Z station, and the shortest path algorithm to how to write it, please give ideas and detailed code

Started by Samantha at February 10, 2016 - 3:42 AM

Really interesting, look at.

Posted by Myron at February 11, 2016 - 3:52 AM

Can't seem to reach...
A: 100, 102
Z: 104

104 and 101103 have the intersection, but the 100102 and 101103 have no intersection

Posted by Angus at February 14, 2016 - 4:35 AM

No, no intersection

Posted by Ishara at February 24, 2016 - 4:49 AM

If the intersection is the shortest distance algorithm, can't write...... But should be able to search to the previous works

Posted by Angus at March 06, 2016 - 4:54 AM

Wrong, sweat

The line through the station
100 Road: A station, B station, C station, D station, E station
101 Road: F station, E station, H station, I station, G station
102 Road: A station, P station, G station, R station, S station
103 Road: K station, I station, M station, G station, O station
104 Road: I, M, Z station

Now from the A station to Z station, and the shortest path algorithm to how to write it, please give ideas and detailed code

Posted by Samantha at March 16, 2016 - 5:35 AM

The 5 floor is right the wrong

Posted by Samantha at March 24, 2016 - 6:30 AM

Exhaustive method, the most stupid, is the permutation and combination, and then find the minimum number of nodes. Ignore each station distance is different

Posted by Drew at April 04, 2016 - 7:02 AM

Please write down the code

Posted by Samantha at April 19, 2016 - 7:57 AM

php - Dijkstra's algorithm
[url=http://www.phpclasses.org/search.html?words=Dijkstra+algorithm&restrict[0]=C&restrict[1]=B&restrict[2]=D&forums=F&go_search=1&advanced=1]http://www.phpclasses.org/search.html?words=Dijkstra+algorithm&restrict[0]=C&restrict[1]=B&restrict[2]=D&forums=F&go_search=1&advanced=1[/url]

Posted by Angus at April 29, 2016 - 8:51 AM

Cut, CSDN still does not recognize...

;restrict[0]=C&restrict[1]=B&restrict[2]=D&forums=F&go_search=1&advanced=1

Posted by Angus at April 30, 2016 - 8:59 AM

The three table (the most simple, does not consider the fuzzy query, single line and other things):
1, The site table stop(stop_id,stop_name)
2, Route table line(line_id,line_name)
3, Route the site table (point line relation table) linestops (line_id, stop_id, SEQ) where SEQ refers to a site in a line in the order.


Now the analysis algorithm:
1, Direct line
According to the two site gets two sites of the ID, defined here as Id1,id2
Then the query
select line_id from
(select line_id from linestops where stop_id = id1) A,
(select line_id from linestops where stop_id = id2) B
where A.line_id = B.line_id
Get to the line list

2,A transfer
According to the two site gets two sites of the ID, defined here as Id1,id2
And then search for the two site through direct way to arrive at the respective site collection, the last of their intersection is what we need the transfer station.
select stop_id from
(
select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id1)
)A,
(
select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id1)
)B
where A.stop_id= B.stop_id
Get the transfer station (there may be more than one or 0), is the display line on both sides to reach the rest of the transfer station, through direct inquiry front.

3, The two transfer
According to the two site gets two sites of the ID, defined here as Id1,id2
The central idea is: site 1 algorithms can all through the site to reach the set A, site 2 to site to reach all the set B, there is a direct line between A and B.
One step at a time.:
Site 1 to site to reach all the set A:
select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id1)
Site 2 to site to reach all the set B:
select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id2)
The direct query is
select line_id from
(select line_id from linestops where stop_id = id1) C,
(select line_id from linestops where stop_id = id2) D
where C.line_id = D.line_id

We use =id1 and =id2 into in (select... A and in.)(select ...)B

So finally we query is
select line_id from
(select distinct line_id from linestops where stop_id in [A]) C,
(select distinct line_id from linestops where stop_id in [B]) D
where C.line_id = D.line_id
The [A] is
(select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id1))
The [B] is
(select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id2))
So we found as intermediate transfer line (may have more than one or 0), the list of each hypothesis named X-ray, the next step is to find out from site 1 to X any direct line, a site and from the site from 2 to X any direct line a site can.
Then with the previous algorithms, we seek and line X intersects the site in site 1 all can arrive at the site, and then go to the two point line
select stop_id from
(select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id1))A,
(select stop_id from linestops where line_id = X ) B
where A.stop_id = B.stop_id
To find the site, below is based on direct query has been solved for the line.
2 similar sites.


The above algorithm has an advantage, all is SQL complete ASP code search, so only a few lines of circular.
But the drawback is: slow, after all, may involve hundreds of SQL query. And just use the SQL method is the most simple to calculate all can transfer scheme, does not involve the optimal / shortest algorithm. If it is the shortest path, it must use the special structure and algorithm.



In addition:

According to the beginning and the end of Walker input, determine trip to choose the starting bus station and bus station B A. Search database, query between site A and site B have the same car after, if one or several direct line, by comparing and choosing the shortest distance bus lines are recommended. If not, then calculate the between site A and site B does not have a public C site, from site to site B C can transfer. It is of two kinds: (1) if have, belong to a transfer. Between computing site A and public site C have the same bus through the X and stored in the collection; similarly, between computing site B and public site C have the same bus through the Y and stored in the collection. The two set after the comparison can get from the site after site at C A public bus line site B, compare with these lines, are recommended to choose the shortest distance. (2) if there is no public site C, appeared to transfer two times. After all the site each bus line site A in the set O; also, after all the site each line of site B in the set P. A comparison of the two set, first by the site A a road car at a site D, calculation between site D and site B has no public site E, if there is the site D, E to the transfer station. This scheme may have multiple, choose the shortest distance are recommended. If there is no public site E, that after the two transfer from site A to site cannot be B, stop the search computation.

Public transit route specific algorithm:

1) Enter the start site A and site B,

2) Database search system, through the bus line start site of A to X (I) (i=1,2,3... , m, M is a positive integer), after the bus lines to site B saved as Y (J) (j=1,2,3,... N,.N is a positive integer),

3) To determine whether X (I) =Y (J), will meet the Z deposited conditions. If Z = 1, the bus line X (I) Y (J) to direct the optimal line from site A to site B, output results and conclusion of operation. Z ≥ 1, each line in the calculation of Z distance, a distance of the shortest circuit, output and the end of operation,

4) Database search system, bus line X (I) contains the site to save as O (I, U) (u=1,2,3... , G, G is a positive integer) bus line Y (J) contains the site to save as P (J, V) (v=1,2,3... , h, h is a positive integer),

5) To determine whether O (I, U) = P (J, V), will meet in the condition of W. If W = 1, the site of O (I, U) P (J, V) as a transfer from site A to site B, bus line X (I), Y (J) is the optimal route transfer time, output results and conclusion of operation. If W ≥ 1, calculate each transfer route distance, a distance of the shortest circuit, output and the end of operation,

6) Search database, through the O site (I, U) bus lines to save as R (k) (k=1,2,3... , P, P is a positive integer), bus line R (k) contains the site to save as G (k, t) (t=1,2,3... , Q, q is a positive integer),

7)To determine whether G (k, t) =P (J, V), will meet the conditions of the deposited S. If S = 1, the site of G (k, t) P (J, V) from two times the transfer site site A to site B, bus line X (I), R (k), Y (J) is the best route to take two, the output results and conclusion of operation. If S ≥ 1, calculate each take two line distance, a distance of the shortest circuit, output and the end of operation,

8) The above steps did not find a suitable bus lines, output "no transfer number no more than two times the optimal bus route", end of operation.

Posted by Winston at May 15, 2016 - 9:14 AM

The theory is very complicated, mathematical derivation can hardly understand
But in fact very simple, especially with PHP
class bus {
  var $d = array(
    100 => array('A', 'B', 'C', 'D', 'E'),
    101 => array('F', 'E', 'H', 'I', 'G'),
    102 => array('A', 'P', 'G', 'R', 'S'),
    103 => array('K', 'I', 'M', 'G', 'O'),
    104 => array('I', 'M', 'Z'),
  );
  var $ex = array();

  function find($s, $e) {
    $res = $this->find_back($s, $e);
    if($res) $res = array($s => $res);
    return $this->format($res);
  }
  function format($ar) {
    $res = array();
    foreach($ar as $p=>$r) {
      if(! is_array($r)) return array($p); 
      foreach($r as $l=>$c) {
        foreach($this->format($c) as $v) {
          $res[] = "$p - [$l] - $v";
        }
      }
    }
    return $res;
  }
  function find_back($s, $e, $ex=array()) {
    $res = array();
    $d = $this->filter($s, $ex);
    $ex = array_merge($ex, array_keys($d));
    foreach($d as $k=>$r) {
      if(in_array($e, $r)) {
        $res[$k] = array($e => $k);
      }
      foreach($r as $v) {
        $t = $this->find_back($v, $e, $ex);
        if($t) $res[$k][$v] = $t;
      }
    }
    return $res;
  }
  function filter($a, $ex) {
    $res = array();
    foreach($this->d as $k=>$r) {
      if(in_array($k, $ex)) continue;
      if(in_array($a, $r)) $res[$k] = $r;
    }
    return $res;
  }
}
$p = new bus;
print_r($p->find('A', 'Z'));
Array
(
[0] => A - [100] - E - [101] - I - [104] - Z
[1] => A - [100] - E - [101] - G - [103] - I - [104] - Z
[2] => A - [100] - E - [101] - G - [103] - M - [104] - Z
[3] => A - [102] - G - [101] - I - [104] - Z
[4] => A - [102] - G - [103] - I - [104] - Z
[5] => A - [102] - G - [103] - M - [104] - Z
)

Posted by dream at October 30, 2016 - 10:25 PM

Do you want a bus line app? It feels good to do ah!

Posted by Kim at November 02, 2016 - 10:35 PM

This collection

Posted by Angus at November 12, 2016 - 11:05 PM

Collection!

Posted by Ricky at November 15, 2016 - 12:00 AM

The moderator said that under the principle of the algorithm, only the code more difficult to understand

Posted by Samantha at November 22, 2016 - 12:24 AM

Upstairs are all empty talk ah, only thought of logical thinking.

100 Road: A station, B station, C station, D station, E station
101 Road: F station, G station, H station, I station, G station
102 Road: A station, P station, Q station, R station, S station
103 Road: K station, L station, M station, N station, O station
104 Road: I, M, Z station
Obviously A to B, B to C, F to G distance can not be the same length, then the time cannot be the same, what is the shortest route, you write is "station at least", not to. . .

The first to have the distance between two stations, with distance as data, for computing query.

And the said algorithm, the introduction to algorithms university learned, will.. This is a simple shortest path problem.

Posted by Glenn at November 23, 2016 - 12:51 AM

Xu boss, this should be and distance. Not any two stations distance to etc.

Posted by Glenn at November 28, 2016 - 12:53 AM

First, access, and distance
Can not reach, and short distance has no meaning

The path I only responsible for the given access, distance from your computer
Besides the bus, take a 2 yuan, and the distance (number) not much

Posted by dream at November 29, 2016 - 12:59 AM

Selected after a specified site line, can be specified does not check the line
This should be easy to understand.
  function filter($a, $ex) {
    $res = array();
    foreach($this->d as $k=>$r) {
      if(in_array($k, $ex)) continue;
      if(in_array($a, $r)) $res[$k] = $r;
    }
    return $res;
  }

Recursive function, used to find the path to the target site
  function find_back($s, $e, $ex=array()) {
    $res = array();
    $d = $this->filter($s, $ex);//Find station through $s line
    $ex = array_merge($ex, array_keys($d));
    foreach($d as $k=>$r) { //For each line
      if(in_array($e, $r)) {
        $res[$k] = array($e => $k); //Find the target site
      }
      foreach($r as $v) { //For each site
        $t = $this->find_back($v, $e, $ex); //Recursive check whether can reach the goal
        if($t) $res[$k][$v] = $t; //To preserve
      }
    }
    return $res;
  }

The algorithm is very simple, is a depth first traversal graph
Personally think that the return data structure is very clever, you look at the know
The structure of the returning, I am trying for a long time

Posted by dream at December 03, 2016 - 1:06 AM

I also have a try, do not know the landlord provisions single line or double line, write the realized, I this is a double line.

<?php
$lines = array(
	100 => array( 'A' , 'B' , 'C' , 'D' , 'E' ) ,
    101 => array( 'F' , 'E' , 'H' , 'I' , 'G' ) ,
    102 => array( 'A' , 'P' , 'G' , 'R' , 'S' ) ,
    103 => array( 'K' , 'I' , 'M' , 'G' , 'O' ) ,
    104 => array( 'I' , 'M' , 'Z')
);

function get_line( $position1 , $position2 , $lines )
{
	$collection = array();
	foreach( $lines as $k => $v )
	{
		if( in_array( $position1 , $v ) )
		{
			foreach( $v as $kk => $vv )
			{
				if( $position1 == $vv )
				{
					continue ;
				}

				if( $vv == $position2 )
				{
					return array( $k => $vv ) ;
				}
				else
				{
					unset( $lines[$k] );
					$sub_collection = get_line( $vv , $position2 , $lines );
					if( !empty( $sub_collection ) )
					{
						$collection[$k] = array( $vv , $sub_collection );
					}
				}
			}
		}
		else
		{
			continue ;
		}
	}
	return $collection ;
}

$line = get_line( 'A' , 'Z' , $lines );
print_r( $line );
?>

Posted by Sidney at December 17, 2016 - 1:15 AM

The result is an array, to extract the array

Array
(
[100] => Array
(
[0] => E
[1] => Array
(
[101] => Array
(
[0] => G
[1] => Array
(
[103] => Array
(
[0] => M
[1] => Array
(
[104] => Z
)

)

)

)

)

)

[102] => Array
(
[0] => G
[1] => Array
(
[101] => Array
(
[0] => I
[1] => Array
(
[104] => Z
)

)

[103] => Array
(
[0] => M
[1] => Array
(
[104] => Z
)

)

)

)

)

Posted by Sidney at December 25, 2016 - 1:19 AM

Strategic mark thanks for sharing

Posted by Bertram at December 28, 2016 - 1:26 AM

Bug, modification,
<?php
$lines = array(
	100 => array( 'A' , 'B' , 'C' , 'D' , 'E' ) ,
    101 => array( 'F' , 'E' , 'H' , 'I' , 'G' ) ,
    102 => array( 'A' , 'P' , 'G' , 'R' , 'S' ) ,
    103 => array( 'K' , 'I' , 'M' , 'G' , 'O' ) ,
    104 => array( 'I' , 'M' , 'Z')
);


//aeimz
//aeiz
//aegiz
//aegmz
//agimz
//agiz
//agiz
//agmz
function get_line( $position1 , $position2 , $lines )
{
	$collection = array();
	foreach( $lines as $k => $v )
	{
		if( in_array( $position1 , $v ) )
		{
			foreach( $v as $kk => $vv )
			{
				if( $position1 == $vv )
				{
					continue ;
				}
				if( $vv == $position2 )
				{
					$collection[$k][] = array( $k => $vv ) ;
				}
				else
				{
					unset( $lines[$k] );
					$sub_collection = get_line( $vv , $position2 , $lines );
					if( !empty( $sub_collection ) )
					{
						$collection[$k][] = array( $vv , $sub_collection );
					}
				}
			}
		}
		else
		{
			continue ;
		}
	}
	return $collection ;
}

$line = get_line( 'A' , 'Z' , $lines );
print_r( $line );
?>

Posted by Sidney at January 04, 2017 - 1:49 AM

I think that with the word frequency statistics.,
With a trie tree

Posted by Cosmo at January 08, 2017 - 1:38 AM

The trouble that principle, only the code, not too well understood

Posted by Samantha at January 09, 2017 - 2:42 AM