公交车问题 求从一站到另一站站的所有线路给个思路,最好给个实例 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 没明白有无往返?如无;站:ASDFG需:S->F有:S->D,D->F和S->F两种还是只有S->F呀 就是按一般乘车的思维来做!ASDFGS到F如果有路径S到F,S->D,D->F的话,那么要显示S->F也就是说显示所有路径S->D->F 上面发错了就是按一般乘车的思维来做!ASDFGS到F如果有路径S到F,S->D,D->F的话,那么要显示S->FS->D->F也就是说显示所有路径 用递归应该是可以的.我的有错,调错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(松风抚琴) ,你可以从这个世界消失了,这里不是灌水的地方。 没有代码,只有草稿,第一个数据是线路的交汇信息(HashSet<Integer>),第二个是每个站点在某条线路上的长度信息(HashMap<Integer(线路号), HashMap<Integer(站点号),Integer(长度)>>),如果不考虑最优化的话,可以省略。1条线直达,看起点、终点的最大公约数gcd是否非11次转乘,把两个站点的编号(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不知道有没有讲明白,同时有没有把问题都考虑清楚。 请教一个简单的问题 初学 怎么用eclipse查看java jdk 里的内部类 高手指点 如何从控制台输入数据? 菜鸟问一个JBUILDER最基本的问题 请问如何拆分字符串! 有偿转让Java即时通信工具源程序及设计文档 高手进来看看! apache commons logging 缺省使用jdk14logger, 设置jdk14logger的loglevel的问题 一个很弱的applet问题,可是不知道错在何处? 谁能给一个Jsp页面的事件响应的一个简单例子啊! 用下载的Driver连接数据库
站:ASDFG
需:S->F
有:S->D,D->F和S->F两种还是只有S->F呀
也就是说显示所有路径
谁有兴趣可看看
====================
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);
}
}
第二个是每个站点在某条线路上的长度信息(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不知道有没有讲明白,同时有没有把问题都考虑清楚。