当前页面: 开发资料首页 → J2SE 专题 → 公交车问题

公交车问题

摘要: 公交车问题

求从一站到另一站站的所有线路

给个思路,最好给个实例

---

没明白

有无往返?

如无;
站:ASDFG
需:S->F
有:S->D,D->F和S->F两种还是只有S->F呀

---

建有向图,遍历就可以了啊

---

狂顶上了

---

就是按一般乘车的思维来做!

ASDFG

S到F

如果有路径S到F,S->D,D->F的话,那么要显示

S->F

也就是说显示所有路径

S->D->F

---

上面发错了

就是按一般乘车的思维来做!

ASDFG

S到F

如果有路径S到F,S->D,D->F的话,那么要显示

S->F

S->D->F
也就是说显示所有路径

---

这不是有向图么？

---

是有向图,希望给我个例子看看,我不会...

---

up,学习ing

---

用递归应该是可以的.我的有错,调错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);
}
}

---

各种数据结构及算法的书上有大量的介绍，自己学去。看来上大学时学的东西都忘光光了，起码还知道在哪儿找吧？

---

再问一次,我顶...

---

楼主我支持你
-----------------
松自萧萧云自飘
风中独酌亦逍遥
抚却凡愁与尘念
琴韵未解恨已销

---

有向图
找本数据结构吧
大学的都还给老师了

---

顶一下，N年来，一看到图我就晕，反正我认为回溯算法可以解决，但是不清楚有没有更优的方式，

比如，加入这个公交系统够简单，可以考虑给每个站点取个素数，那么每条线路就是他们的乘积，然后还没想全，先去开会。

guileen(松风抚琴) ，你可以从这个世界消失了,这里不是灌水的地方。

---

此问题挺复杂，用存储过程的递归调用可以实现，但是有最佳路线的优化及换车次数等问题，应该涉及到公交查询系统中的核心算法

---

算上转车就麻烦了。

---

玩了一会儿我的素数算法，貌似10条以内线路，最多乘3次车子的情况下还是可行的。

---

但是上午说的每个车站一个素数正好相反，应该是每条线路一个素数，车站是该站所有线路的乘积。

---

可以把代码发上来看看吗,最好有注释

---

没有代码，只有草稿，

第一个数据是线路的交汇信息(HashSet)，
第二个是每个站点在某条线路上的长度信息(HashMap>)，如果不考虑最优化的话，可以省略。

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

不知道有没有讲明白，同时有没有把问题都考虑清楚。

---