公交车问题

Question

求从一站到另一站站的所有线路给个思路,最好给个实例

Answer 1

没明白有无往返?如无;
站:ASDFG
需:S->F
有:S->D,D->F和S->F两种还是只有S->F呀

Answer 2

就是按一般乘车的思维来做!ASDFGS到F如果有路径S到F,S->D,D->F的话,那么要显示S->F也就是说显示所有路径S->D->F

Answer 3

上面发错了就是按一般乘车的思维来做!ASDFGS到F如果有路径S到F,S->D,D->F的话,那么要显示S->FS->D->F
也就是说显示所有路径

Answer 4

用递归应该是可以的.我的有错,调错ing
谁有兴趣可看看
====================
public class Test{ public static void func(char a[],int N,int i,int j,boolean flag)
{
   if(i<0||j<0||i>=N||j>=N) {System.out.println("Error!");return ;}
   //if(i==j) {System.out.println(a[i]);return;}    
   if(i==j) 
   System.out.println(a[i]);
   else if(i>j){
      for(int k=i-1;k>=j;k--)
      {
      System.out.print(a[i]+"->");
         func(a,N,k,j,false);         
      }
   }else {
      for(int k=i+1;k<=j;k++)
      {
      System.out.print(a[i]+"->");
         func(a,N,k,j,false);            
      }
   }    
}

public static void main(String[] argus){
char a[]={'A','B','C','D','E'};
func(a,5,0,4,true);
}
}

Answer 5

顶一下，N年来，一看到图我就晕，反正我认为回溯算法可以解决，但是不清楚有没有更优的方式，比如，加入这个公交系统够简单，可以考虑给每个站点取个素数，那么每条线路就是他们的乘积，然后还没想全，先去开会。guileen(松风抚琴) ，你可以从这个世界消失了,这里不是灌水的地方。

Answer 6

没有代码，只有草稿，第一个数据是线路的交汇信息(HashSet<Integer>)，
第二个是每个站点在某条线路上的长度信息(HashMap<Integer(线路号), HashMap<Integer(站点号),Integer(长度)>>)，如果不考虑最优化的话，可以省略。1条线直达，看起点、终点的最大公约数gcd是否非1
1次转乘，把两个站点的编号（N及M个素数之积），质因数分解，两两组合，共有N*M种可能，如果某个组合存在，该组合之积便是换成站点，把所有换乘站点（最多N*M个）的长度信息排序，得到最优线路。如果N*M个都不存在，则需第2次转乘，把刚才N，M个质因数分别乘以某条和起始点都无关的线路号L（即素数L不在那N+M个素数里面），得到的2个结果如果都存在则是2次换乘站。最后考虑优化问题。假设一共有T条线路，则第三种遍历时会有N*M*(T-N-M)种组合（但愿没想错），但是由于是回溯算法，很多组合会中间break，同时考虑到T（不可能超过1000），N,M(极少超过10)不是很大的情况下，貌似可以接受。到实际情况下，可能需要把城市的某个网格，而不是具体某个车站。我想，在一般城市，坐3辆车已经很可以了，所以我这个想法应该可以解决问题吧:P不知道有没有讲明白，同时有没有把问题都考虑清楚。