高效的算法来找到从A到Z的所有路径？ [英] Efficient algorithm to find all the paths from A to Z?
问题描述
通过一组
A B
üž
B A
A C
Z A
ķž
A Q
D A
üķ
Pü
向上
通过
ÿř
ÿü
C R
R Q
广告
采用Q Z
搜索到Z.从A所有的路径
- 系统 - B - Y - 的R - Q - z
- 系统 - B - Y - ü - z
- 系统 - C - 的R - Q - z
- 系统 - Q - z
- 系统 - B - Y - ü - K - z
一个位置不能在路径中出现多次，因此 A - B - Y - ü - P - U - z 是无效的。
位置被命名为AAA到ZZZ（这里psented为A $ P $ - z为简单起见）且输入是随机的以这样的方式，有可能或可能不是一个位置的ABC，所有位置可以是XXX（不可能）或可能不存在于所有位置分离的的可能路径。
起初我还以为这是不加权最短路径问题的变化，但我觉得很不同而我不知道怎么的算法有适用于此。
我目前的解决办法是这样的：
-
pre-进程列表中，这样我们有一个HashMap指向的位置（左），到位置（右）
列表
-
创建一个HashMap跟踪访问地点。创建一个列表来存储找到路径。
-
商店X（起始位置）的访问地点HashMap中。
-
在第一个HashMap的搜索X，（位置A将带给我们（B，C，Q）在O（1）时间）。
-
有关，每一个发现的位置（B，C，Q），检查它是否是最终的目的地（Z）。如果是存放在找到路径名单。否则，如果它不已经处于到访位置散列映射存在，Recurl到现在步骤3与该位置为X。 （实际$ C $低于C）
通过这个当前的解决方案，它需要的永远地图所有（不是最短的）可能的路线，从BKI到仙了的this提供的数据。
我不知道是否有这样做的更有效的（时间上的）的方式。有谁知道一个更好的算法来寻找到任意位置Z从任意位置的所有路径？
实际code表示目前的解决办法：
进口的java.util。*;
进口java.io. *;
公共类测试{
私有静态HashMap的＆LT;字符串列表与LT;字符串＆GT;＆GT; left_map_rights;
公共静态无效的主要（字符串的args []）抛出异常{
left_map_rights =新的HashMap＆LT;＆GT;（）;
BufferedReader中R =新的BufferedReader（新的FileReader（routes.text））;
串线;
HashMap的＆LT;字符串，太虚＆GT;线=新的HashMap＆LT;＆GT;（）;
而（（行= r.readLine（））！= NULL）{
如果（lines.containsKey（线））{//确保不重复的行
继续;
}
lines.put（线，空）;
INT space_location = line.indexOf（''）;
串左= line.substring（0，space_location）;
字符串右= line.substring（space_location + 1）;
如果（left.equals（右））{//拒绝项即左=右
继续;
}
名单＆LT;字符串＆GT;权= left_map_rights.get（左）;
如果（权利== NULL）{
权=新的ArrayList＆LT;字符串＆GT;（）;
left_map_rights.put（左，权利）;
}
rights.add（右）;
}
r.close（）;
的System.out.println（开始）;
名单＆LT;列表＆LT;字符串＆GT;＆GT;路线= GetAllRoutes（BKI，SIN）;
的System.out.println（结束）;
对于（名单＆LT;字符串＆GT;路线：路线）{
的System.out.println（路线）;
}
}
公共静态列表＆LT;列表＆LT;字符串＆GT;＆GT; GetAllRoutes（字符串的开始，结束的字符串）{
名单＆LT;列表＆LT;字符串＆GT;＆GT;路线=新的ArrayList＆LT;＆GT;（）;
名单＆LT;字符串＆GT;权= left_map_rights.get（开始）;
如果（权利！= NULL）{
对于（字符串右：权）{
名单＆LT;字符串＆GT;路径=新的ArrayList＆LT;＆GT;（）;
route.add（开始）;
route.add（右）;
链（航线，航路，右，年底）;
}
}
返回路线;
}
公共静态无效链（名单＆LT;列表＆LT;字符串＆GT;＆GT;的路线，列表和LT;字符串＆GT;的路线，串right_most_currently，字符串结束）{
如果（right_most_currently.equals（完））{
routes.add（路线）;
返回;
}
名单＆LT;字符串＆GT;权= left_map_rights.get（right_most_currently）;
如果（权利！= NULL）{
对于（字符串右：权）{
如果（！route.contains（右））{
名单＆LT;字符串＆GT; new_route =新的ArrayList＆LT;字符串＆GT;（路线）;
new_route.add（右）;
链（路线，new_route，右，年底）;
}
}
}
}
}
据我了解你的问题，Dijkstras算法不能适用的是，因为根据定义最短路径问题发现在一组的所有可能路径的单一路径。你的任务是找到每本身所有的路径。
在Dijkstras算法许多优化涉及到切断与更高的成本查找树。您将无法切断的部分在你的搜索，因为所有你需要的结果。
和我假定你的意思的所有路径的不包括圆的。
算法：
-
泵网络为布尔/整型的2dim阵列为26x26。 fromTo [I，J]。 设置一个1 /适用于现有的链接。
-
从第一个节点开始跟踪所有后续节点（搜索链接1 /真）。
-
请在一些结构（阵列/列表）访问节点。由于最大 深度好像是26，这应该通过递归是可能的。
-
随着@soulcheck已经写在下面，你可以想想切割你已位于visted路径。你可能会保留路径的列表朝向阵列的每个元素的目的地。相应地调整断裂状态。
-
休息的时候，
- 访问终端节点（存储结果）
- 在访问已前（圈子）被visted节点时
- 访问，而您已经找到了所有的路径到目标，并从该节点的所有现有的合并您的当前路径的一个节点。
性能明智我会投反对票使用包含HashMap和列表和preFER静态结构。
嗯，而重新阅读的问题，我意识到，节点的名称不能仅限于亚利桑那州。你正在写一些关于20K线，有26个字母，一个完全连接AZ网络将需要少得多的联系。也许你跳过递归和静态结构：）
好吧，从AAA有效名称的ZZZ阵列会变得过于庞大。所以你最好创建一个动态结构，网络也是如此。计数器问题：性能方面，什么是最好的数据结构不那么这样就把数组作为我的算法需要？我投给了2暗淡的ArrayList。有人吗？
With a set of random inputs like this (20k lines):
A B
U Z
B A
A C
Z A
K Z
A Q
D A
U K
P U
U P
B Y
Y R
Y U
C R
R Q
A D
Q Z
Find all the paths from A to Z.
- A - B - Y - R - Q - Z
- A - B - Y - U - Z
- A - C - R - Q - Z
- A - Q - Z
- A - B - Y - U - K - Z
A location cannot appear more than once in the path, hence A - B - Y - U - P - U - Z is not valid.
Locations are named AAA to ZZZ (presented here as A - Z for simplicity) and the input is random in such a way that there may or may not be a location ABC, all locations may be XXX (unlikely), or there may not be a possible path at all locations are "isolated".
Initially I'd thought that this is a variation of the unweighted shortest path problem, but I find it rather different and I'm not sure how does the algorithm there apply here.
My current solution goes like this:
Pre-process the list such that we have a hashmap which points a location (left), to a list of locations (right)
Create a hashmap to keep track of "visited locations". Create a list to store "found paths".
Store X (starting-location) to the "visited locations" hashmap.
Search for X in the first hashmap, (Location A will give us (B, C, Q) in O(1) time).
For-each found location (B, C, Q), check if it is the final destination (Z). If so store it in the "found paths" list. Else if it doesn't already exist in "visited locations" hashmap, Recurl to step 3 now with that location as "X". (actual code below)
With this current solution, it takes forever to map all (not shortest) possible routes from "BKI" to "SIN" for this provided data.
I was wondering if there's a more effective (time-wise) way of doing it. Does anyone know of a better algorithm to find all the paths from an arbitrary position A to an arbitrary position Z ?
Actual Code for current solution:
import java.util.*;
import java.io.*;
public class Test {
private static HashMap<String, List<String>> left_map_rights;
public static void main(String args[]) throws Exception {
left_map_rights = new HashMap<>();
BufferedReader r = new BufferedReader(new FileReader("routes.text"));
String line;
HashMap<String, Void> lines = new HashMap<>();
while ((line = r.readLine()) != null) {
if (lines.containsKey(line)) { // ensure no duplicate lines
continue;
}
lines.put(line, null);
int space_location = line.indexOf(' ');
String left = line.substring(0, space_location);
String right = line.substring(space_location + 1);
if(left.equals(right)){ // rejects entries whereby left = right
continue;
}
List<String> rights = left_map_rights.get(left);
if (rights == null) {
rights = new ArrayList<String>();
left_map_rights.put(left, rights);
}
rights.add(right);
}
r.close();
System.out.println("start");
List<List<String>> routes = GetAllRoutes("BKI", "SIN");
System.out.println("end");
for (List<String> route : routes) {
System.out.println(route);
}
}
public static List<List<String>> GetAllRoutes(String start, String end) {
List<List<String>> routes = new ArrayList<>();
List<String> rights = left_map_rights.get(start);
if (rights != null) {
for (String right : rights) {
List<String> route = new ArrayList<>();
route.add(start);
route.add(right);
Chain(routes, route, right, end);
}
}
return routes;
}
public static void Chain(List<List<String>> routes, List<String> route, String right_most_currently, String end) {
if (right_most_currently.equals(end)) {
routes.add(route);
return;
}
List<String> rights = left_map_rights.get(right_most_currently);
if (rights != null) {
for (String right : rights) {
if (!route.contains(right)) {
List<String> new_route = new ArrayList<String>(route);
new_route.add(right);
Chain(routes, new_route, right, end);
}
}
}
}
}
As I understand your question, Dijkstras algorithm cannot be applied as is, since shortest path problem per definition finds a single path in a set of all possible paths. Your task is to find all paths per-se.
Many optimizations on Dijkstras algorithm involve cutting off search trees with higher costs. You won't be able to cut off those parts in your search, as you need all findings.
And I assume you mean all paths excluding circles.
Algorithm:
Pump network into a 2dim array 26x26 of boolean/integer. fromTo[i,j]. Set a 1/true for an existing link.
Starting from the first node trace all following nodes (search links for 1/true).
Keep visited nodes in a some structure (array/list). Since maximal depth seems to be 26, this should be possible via recursion.
And as @soulcheck has written below, you may think about cutting of paths you have aleady visted. You may keep a list of paths towards the destination in each element of the array. Adjust the breaking condition accordingly.
Break when
- visiting the end node (store the result)
- when visiting a node that has been visted before (circle)
- visiting a node for which you have already found all paths to the destination and merge your current path with all the existing ones from that node.
Performance wise I'd vote against using hashmaps and lists and prefer static structures.
Hmm, while re-reading the question, I realized that the name of the nodes cannot be limited to A-Z. You are writing something about 20k lines, with 26 letters, a fully connected A-Z network would require far less links. Maybe you skip recursion and static structures :)
Ok, with valid names from AAA to ZZZ an array would become far too large. So you better create a dynamic structure for the network as well. Counter question: regarding performance, what is the best data structure for a less popuplate array as my algorithm would require? I' vote for an 2 dim ArrayList. Anyone?
这篇关于高效的算法来找到从A到Z的所有路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
