(以下大部分内容翻译自 eloquent Javascript 第7章)
来看一个寻路算法的例子&＃xff1a;
如图所示&＃xff0c;连线上的数字表示这两点之间的距离&＃xff0c;现在要写一个算法能够计算出两点间的最短路径。
别急着往下看&＃xff0c;认真地想一下有哪几种可行方案&＃xff0c;有哪些可能会碰到的问题。在阅读技术文章时&＃xff0c;经常是快速翻阅一遍内容&＃xff0c;若有所悟地点点头&＃xff0c;然后马上就忘了。如果你真正努力地去解决某个问题&＃xff0c;那它就会变成你的问题&＃xff0c;它的解决方案也更有意义。
首先&＃xff0c;用数据来描述这个地图&＃xff0c;我们使用一个object&＃xff1a;
roads &＃61; { "Point Kiukiu": [ { "to": "Taaoa", "distance": 15 }, { "to": "Hanaiapa", "distance": 19 }, { "to": "Mt Feani", "distance": 15 } ], "Taaoa": [ { "to": "Point Kiukiu", "distance": 15 }, { "to": "Mt Temetiu", "distance": 4 }, { "to": "Atuona", "distance": 3 } ], "Hanaiapa": [ { "to": "Point Kiukiu", "distance": 19 }, { "to": "Airport", "distance": 6 } ], "Mt Feani": [ { "to": "Point Kiukiu", "distance": 15 }, { "to": "Mt Temetiu", "distance": 8 }, { "to": "Airport", "distance": 5 } ], "Mt Temetiu": [ { "to": "Taaoa", "distance": 4 }, { "to": "Mt Feani", "distance": 8 } ], "Atuona": [ { "to": "Taaoa", "distance": 3 }, { "to": "Airport", "distance": 4 }, { "to": "Hanakee pearl lodge", "distance": 1 } ], "Airport": [ { "to": "Mt Feani", "distance": 5 }, { "to": "Atuona", "distance": 4 }, { "to": "Hanaiapa", "distance": 6 }, { "to": "Mt Ootua", "distance": 11 } ], "Hanakee pearl lodge": [ { "to": "Atuona", "distance": 1 }, { "to": "Cemetary", "distance": 6 } ], "Mt Ootua": [ { "to": "Airport", "distance": 11 }, { "to": "Cemetary", "distance": 5 }, { "to": "Hanapaoa", "distance": 3 }, { "to": "Puamua", "distance": 13 } ], "Cemetary": [ { "to": "Hanakee pearl lodge", "distance": 6 }, { "to": "Mt Ootua", "distance": 5 } ], "Hanapaoa": [ { "to": "Mt Ootua", "distance": 3 } ], "Puamua": [ { "to": "Mt Ootua", "distance": 13 }, { "to": "Point Teohotepapapa", "distance": 14 } ], "Point Teohotepapapa": [ { "to": "Puamua", "distance": 14 } ] };
这个roads包含了小岛上所有的路径信息&＃xff0c;当我们从某处出发&＃xff0c;想要知道有哪些路时&＃xff0c;用roads[place]就可以得到&＃xff0c;但如果万一打错地名&＃xff0c;把place拼错了&＃xff0c;就可能意外地返回一个undefined&＃xff0c;这可能造成一些很隐蔽的奇怪错误&＃xff0c;所以我们用一个函数来获取它
function roadsFrom(place) { var found &＃61; roads[place]; if (found &＃61;&＃61; undefined) throw new Error("No place named &＃39;" &＃43; place &＃43; "&＃39; found."); else return found;
}
show(roadsFrom("Puamua"));
现在开始尝试一种老老实实的做法&＃xff0c;"生成&＃xff0c;测试"&＃xff0c;就像这样&＃xff1a;
1. 生成所有可行的路径。
2. 在其中找出最短的路径。
对于一个小型的地图来说&＃xff0c;生成所有路径的做法是可行的。
在这之前&＃xff0c;我们需要一些新的工具函数&＃xff0c;第一个是member&＃xff0c;用来检查一个数组中是否包含某个元素。路径是由很多地名组成的数组&＃xff0c;当我们到达一个新地方时&＃xff0c;我们会调用member来检查这个地方是否已经到过&＃xff0c;像这样&＃xff1a;
function member(array, value) { var found &＃61; false; forEach(array, function(element) { if (element &＃61;&＃61;&＃61; value) found &＃61; true; }); return found;
}
print(member([6, 7, "Bordeaux"], 7)); // true
然而&＃xff0c;即使我们要找的值出现在数组的第一项&＃xff0c;它也会继续遍历完整个数组&＃xff0c;这是没有必要的。当使用for循环时候&＃xff0c;我们可以用break来跳出循环&＃xff0c;但在forEach中这将不管用&＃xff0c;因为循环体是一个函数&＃xff0c;break不能跳出函数。解决方法是把forEach改造成能够知道什么时候该停止遍历。
function forEach(array, action) { for (var i &＃61; 0; i
现在&＃xff0c;一旦action函数返回false&＃xff0c;forEach就会停止遍历。即使member函数使用了forEach&＃xff0c;还是显得臃肿且不够通用&＃xff0c;它需要在内部维护一个found&＃xff0c;最终还要返回它&＃xff0c;使得这个函数显得太有针对性和过于麻烦。member实现的是&＃xff1a;判断在一组数据中是否有任何满足条件的元素&＃xff0c;这个任何可以被抽象出来&＃xff0c;成为any函数
function any(test, array) { for (var i &＃61; 0; i
function member(array, value) { return any(partial(op["&＃61;&＃61;&＃61;"], value), array);
}
print(member(["Fear", "Loathing"], "Denial"));
any遍历整个数组&＃xff0c;对每个元素应用test函数&＃xff0c;一旦有测试结果为真值&＃xff0c;就返回那一项&＃xff0c;如果都不满足&＃xff0c;返回false。使用any(test, array)就相当于test(array[0]) || test(array[1]) || ...
就像&&有个||为伴&＃xff0c; any也有一个与之对应的every&＃xff1a;
function every(test, array) { for (var i &＃61; 0; i
show(every(partial(op["!&＃61;"], 0), [1, 2, - 1]));
我们还需要另一个函数flatten&＃xff0c;它接受一个二维数组&＃xff0c;将其合并到一个一维数组中&＃xff1a;
function flatten(arrays) { var result &＃61; []; forEach(arrays, function(array) { forEach(array, function(element) { result.push(element); }); }); return result;
}
当然flattern也可以这样实现&＃xff1a;
function flattern2(arrays) { return reduce(function(base, array) { return base.concat(array); }, [], arrays);
}
console.info(flattern2([[1, 3, 5], [2, 4]]));
// 结果为&＃xff1a; [1, 3, 5, 2, 4]
但这种做法效率较低&＃xff0c;就像反复连接字符串&＃xff0c;不如把字符串都加入到数组中然后join起来更高效一样&＃xff0c;重复地concat数组会产生很多没必要的临时数组。
在生成路径之前&＃xff0c;我们还需要一个函数filter&＃xff0c;就像map一样&＃xff0c;它接收2个参数&＃xff0c;test函数和一个数组array&＃xff0c;用于过滤掉array中不满足test的元素。
function filter(test, array) { var result &＃61; []; forEach(array, function(element) { if (test(element)) result.push(element); }); return result;
}
show(filter(partial(op[">"], 5), [0, 4, 8, 12]));
// 结果为: [0, 4]
(上面的例子中filter的返回值是否令人不解&＃xff1f;记住传给partial的参数&＃xff0c;将被用在函数的第一个参数&＃xff0c;这里传给partial的5&＃xff0c;将被作用在op[">"]的第一个参数&＃xff0c;所以上面的表达式意思并不是 "所有大于5的值"&＃xff0c;而是 "5大于的值"&＃xff0c;即 "比5小的值")
现在&＃xff0c;整个生成路径的算法看上去应该是这样 -- 从出发点开始&＃xff0c;对每一条离开那里的路生成路径&＃xff0c;我们使用递归来做&＃xff1a;
function possibleRoutes(from, to) { function findRoutes(route) { function notVisited(road) { return ! member(route.places, road.to); } function continueRoute(road) { return findRoutes({ places: route.places.concat([road.to]), length: route.length &＃43; road.distance }); } var end &＃61; route.places[route.places.length - 1]; if (end &＃61;&＃61; to) return [route]; else return flatten(map(continueRoute, filter(notVisited, roadsFrom(end)))); } return findRoutes({ places: [from], length: 0 });
}
show(possibleRoutes("Point Teohotepapapa", "Point Kiukiu").length); // 11
show(possibleRoutes("Hanapaoa", "Mt Ootua")); // [{ places: ["Hanapaoa", "Mt Ootua"], length: 3 }]
这个函数返回一个路径数组&＃xff0c;每一条路径都包含一个所通过节点的数组&＃xff0c;和一个总长度。findRoutes递归循环一条路径&＃xff0c;返回一个路径的所有延伸。当一条路径的末尾地点是我们的目的地时&＃xff0c;它将返回那条路径&＃xff0c;因为继续在那条路径上走是没有意义的。如果末尾是其他的地点&＃xff0c;我们就继续。包含了flatten/map/filter的那行可能是最难读的&＃xff0c;它描述的是&＃xff1a;得到所有从当前节点出发的临近节点&＃xff0c;从其中过滤掉那些已经访问过的&＃xff0c;然后对每一个节点继续进行continueRoute&＃xff0c;由于每一个节点都将返回一个路径数组&＃xff0c;多个节点map后将返回一个二维数组(第一维对应应节点,第二维对应该节点的路径数组)&＃xff0c;所以需要用flatten把这二维数组并成一维数组(因为我们并不关心节点&＃xff0c;只需要所有的路径数组)。
这一行做了很多事&＃xff0c;这就是抽象带来的好处&＃xff1a;不用打满屏幕的代码就能做很复杂的事。
现在我们有了所有可行的路径&＃xff0c;开始尝试找出其中最短的那条。需要一个函数shortestRoute&＃xff1a;
function shortestRoute(from, to) { var currentShortest &＃61; null; forEach(possibleRoutes(from, to), function(route) { if (!currentShortest || currentShortest.length > route.length) currentShortest &＃61; route; }); return currentShortest;
}
也许你已经想到了&＃xff0c;最短的可以被抽象出来
function minimise(func, array) { var minScore &＃61; null; var found &＃61; null; forEach(array, function(element) { var score &＃61; func(element); if (minScore &＃61;&＃61; null || score
function getProperty(propName) { return function(object) { return object[propName]; };
}
function shortestRoute(from, to) { return minimise(getProperty("length"), possibleRoutes(from, to));
}
这种最xx的形式还可以抽象出most函数&＃xff1a;
function most(arr, comp) { var min &＃61; arr[0]; forEach(arr, function(a) { if(comp(min, a)) { min &＃61; a; } }); return min;
}
function getProperty(p) { return function(o) { return o[p]; };
}
function minimal(arr, getter) { return most(arr, function(a, b) { return getter(b)
}
console.info(shortestRoute("Point Teohotepapapa", "Point Kiukiu"));
看上去为一个shortestRoute写了这么多行代码&＃xff0c;比起第一个版本长了3倍&＃xff0c;但这些代码是可重用的。
注意其中的getProperty&＃xff0c;这种做法在函数式编程里经常是很有用的。
京公网安备 11010802041100号