偶尔要写写算法,是我平时用来保持感觉的常用的方法.今天看到园子里一面试题,看了一下感觉也能实现,不过过程确实艰的,自认为自己对算法的感觉还不错.不过这题确实我也用了差不多一下午的时间,基本上把工作时间都耗掉了.主要的两个方法已经搞定,下面先说一下思想,代码确实不太重要,因为过一周我自己就会看不懂了,就像我今天也去看以前的代码.因为这里用到一部分深度优先遍历,所以去找以前代码,但是完全没有作用,还是纯写.
interface IPath { /// <summary> /// 增加某条地铁线路 /// </summary> /// <param name="lineNo">地铁线号</param> /// <param name="stationNum">站点数目</param> /// <param name="stationArray">地铁线站台号数组</param> void AddLine(int lineNo, int stationNum, int[] stationArray); /// <summary> /// 计算从超点到终点的最短路线长度 /// </summary> /// <param name="srcStation">起点站</param> /// <param name="desStation">终点站</param> /// <returns>起点站到终点站最短线长度</returns> int CalcMinPathLen(int srcStation, int desStation); /// <summary> /// 输出从起点到终点的最短路线 /// </summary> /// <param name="srcStation">起点</param> /// <param name="desStation">终点</param> /// <param name="pathNum">条数</param> /// <param name="pathLen">长度</param> /// <param name="pathes">结果路线集合</param> /// <returns>0成功 -1出错</returns> int SearchMinPaths(int srcStation, int desStation, out int pathNum, out int pathLen, out int[][] pathes); /// <summary> /// 最优路线 /// </summary> /// <param name="srcStation">起点</param> /// <param name="desStation">终点</param> /// <param name="pathNum">条数</param> /// <param name="pathLen">长度</param> /// <param name="pathes">结果路线集合</param> /// <returns>0成功 -1出错</returns> int SearchBestPathes(int srcStation, int desStation, out int pathNum, out int pathLen, out int[][] pathes); }
其实这个从题目中命名等看出来主要是C++题,本人用C#实现,其实可以改一些参数名称更为方便,但是这里就按题目中接口来吧.AddLine方法就不说了.
int CalcMinPathLen(int srcStation, int desStation);
计算最短路径,这里用的是迪杰斯特拉算法,就是从起点按起点到各各点最短距离来一个一个往集合里面添加,当然这里的距离就是1,如果是其它数字也是可以的.
int SearchMinPaths(int srcStation, int desStation, out int pathNum, out int pathLen, out int[][] pathes);
这个方法其实略坑了,我基本上是重新想的解决办法,同第一个方法没有很大的联系,不知道我这种思考是否是最优的,不过是可以解决的.重点地方就是用到一个变异的深度优先遍历,这个是有环路存在的,所以比树的深度优先遍历要复杂一些,注意一下深度就可以了,用到一个深度变量去控制是不是保留在遍历排除集合中,就是方法中的list.
两个方法代码如下
public class MetroPath : IPath { private readonly List<Tuple<int, int, int[]>> pathes; private int stationCount = 0; private List<int> minStations; public MetroPath() { pathes = new List<Tuple<int, int, int[]>>(); minStations = new List<int>(); } public void AddLine(int lineNo, int stationNum, int[] stationArray) { if (stationNum < 2 || stationArray == null || stationArray.Length != stationNum) Console.WriteLine("站点数目不对"); else pathes.Add(new Tuple<int, int, int[]>(lineNo, stationNum, stationArray)); } public int CalcMinPathLen(int srcStation, int desStation) { //用迪杰斯特拉算法计算 Dictionary<int, int> stationLens = new Dictionary<int, int>(); IEnumerable<int> ct = pathes[0].Item3; //得到所有站数 foreach (var a in pathes) { ct = ct.Union(a.Item3); } stationCount = ct.Distinct().Count(); try { stationLens.Add(srcStation, 0);//初始 while (stationLens.Count < stationCount) { stationLens = FindMinStation(stationLens, srcStation); } //下一题用 minStations = stationLens.Select(x => x.Key).ToList(); //找出起点到终点最短长度 return stationLens[desStation]; } catch { return -1; //出错 } } //找出余下站点中最短的站点及起点到它的长度 private Dictionary<int, int> FindMinStation(Dictionary<int, int> stations, int srcStation) { Dictionary<int, int> lens = new Dictionary<int, int>(); foreach (var p in pathes) { foreach (var station in p.Item3) { if (!stations.ContainsKey(station)) { //计算最小值 var minlen = ReachLen(stations, srcStation, station); if (minlen > 0 && !lens.ContainsKey(station)) lens.Add(station, minlen); } } } //找出lens中最小的(可以多个)加入集合 int min = lens.Min(v => v.Value); return stations.Union(lens.Where(x => x.Value == min)).ToDictionary(k => k.Key, v => v.Value); } //是否是可达的 -1为不可达 private int ReachLen(Dictionary<int, int> stations, int srcStatoin, int station) { List<int> reachStations = new List<int>(); foreach (var p in pathes) { for (int i = 0; i < p.Item3.Length; i++) { if (p.Item3[i] == station) { if (i - 1 >= 0 && !reachStations.Contains(p.Item3[i - 1])) reachStations.Add(p.Item3[i - 1]); if (i + 1 < p.Item3.Length && !reachStations.Contains(p.Item3[i + 1])) reachStations.Add(p.Item3[i + 1]); } } } var q = stations.Where(v => reachStations.Contains(v.Key)); //相邻点不在集合里面 if (q == null || q.Count() <= 0) return -1; else { //找出q中最小的值 return q.OrderByDescending(v => v.Value).First().Value + 1; } } public int SearchMinPaths(int srcStation, int desStation, out int pathNum, out int pathLen, out int[][] pathes) { pathNum = 0; pathLen = 0; pathes = null; try { pathLen = CalcMinPathLen(srcStation, desStation); List<int[]> result = new List<int[]>(); Stack<int> sk1 = new Stack<int>(); List<Tuple<int, int>> list = new List<Tuple<int, int>>(); sk1.Push(srcStation); minStations.Remove(srcStation); int ct = 0; int deepth = 1; while (deepth > 0) { bool flag = false; foreach (var x in minStations) { list.RemoveAll(v => v.Item1 > deepth); if (ExistsRalation(sk1.Peek(), x) && !sk1.Contains(x) && list.Where(v => v.Item2 == x).Count() <= 0) { sk1.Push(x); deepth++; flag = true; break; } } // if (sk1.Peek() == desStation) { //一条完整的路线 result.Add(sk1.Reverse().ToArray()); deepth--; list.Add(new Tuple<int, int>(deepth, sk1.Pop())); ct++; } //没有找到 if (!flag) { deepth--; list.Add(new Tuple<int, int>(deepth, sk1.Pop())); } } pathNum = ct; pathes = result.ToArray(); return 0; } catch { return -1; } } private bool ExistsRalation(int a, int b) { if (a == b) return false; foreach (var p in pathes.Where(x => x.Item3.Contains(a) && x.Item3.Contains(b))) { for (int i = 0; i < p.Item3.Length; i++) { if (p.Item3[i] == a) { if (i - 1 >= 0 && p.Item3[i - 1] == b) return true; if (i + 1 < p.Item3.Length && p.Item3[i + 1] == b) return true; } } } return false; } public int SearchBestPathes(int srcStation, int desStation, out int pathNum, out int pathLen, out int[][] pathes) { throw new NotImplementedException(); } }
最后一个方法还没有实现,不过大思路也还是可以有的,路径找出来了,只要看路径上交乘点多少就可以了,越少越优,这个算简单.没有时间写了.
最后是调用代码和结果
//测试 IPath mp = new MetroPath(); mp.AddLine(1, 5, new int[] { 1, 2, 3, 4, 5 }); mp.AddLine(2, 5, new int[] { 1, 10, 9, 7, 6 }); mp.AddLine(3, 3, new int[] { 5, 7, 8 }); mp.AddLine(4, 2, new int[] { 11, 5 }); var min = mp.CalcMinPathLen(1, 11); Console.WriteLine("从1到11最短路径长度为:{0}", min); int pathNum = 0; int pathLen = 0; int[][] pathes = null; var re = mp.SearchMinPaths(1, 11, out pathNum, out pathLen, out pathes); Console.WriteLine("从1到11最短路径条数为{0},分别是", pathNum); foreach (var x in pathes) { Console.Write(" {"); foreach (var i in x) { Console.Write("{0},", i); } Console.Write("} "); } Console.ReadLine();
对题中的数据来看是正常的.个人觉得本题还是有难度的,特别是要实实在在写出来,并且调通,我看文中评论有些说简单的人请去实践一下再说吧.
插个小插曲,就是代码一写过基本上就看不懂了.刚才我说到我查阅深度优先算法,我自己的代码完全看不懂,不过看起来以前写的还是很简练,不过是对简单图的遍历.
/// <summary> /// 深度优先 /// </summary> static void DFS(int[,] a, int n) { Stack<int> sk1 = new Stack<int>(); Stack<int> sk2 = new Stack<int>(); sk1.Push(0); Console.WriteLine(0); int x = 0;//访问点标记 int ct = 1;//访问节点数 while (ct < n) { int i = 0; bool f = false; for (i = 0; i < n; i++) { if (a[x, i] != 0 && !sk2.Contains(i)) { sk1.Push(i); Console.WriteLine(i); ct++; x = i; f = true; break; } } if (!f) { //没有找到返回 sk2.Push(sk1.Pop()); x = sk1.Peek(); } } }
确实比较短的,不过看不懂.所以主要还是在于思想吧.数据测试
int[,] a = { {0,10,0,30,80} ,{0,0,50,0,0} ,{0,0,0,0,10} ,{0,0,20,0,60} ,{0,0,0,0,0} }; Console.WriteLine("DFS:"); DFS(a, 5); Console.Read();
最后总结:
1.理解迪杰斯特拉算法
2.深度优先遍历,主要用栈,广度优先主要考虑队列.
3.深度优先的冲突处理,考虑用深度变量.