С набором случайных входов, как это (20k строк):
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
Найдите все пути от A до 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 - B - Y - U - P - U - Z недействителен.
Местоположения называются AAA для ZZZ (для простоты представлены здесь как A - Z), и вход случайен таким образом, что может быть или не быть местоположение ABC, все местоположения могут быть XXX (маловероятными), или там не может быть возможным путем во всех местах "изолированы".
Изначально я думал, что это вариация невзвешенной кратчайшего пути, но я нахожу ее совсем другой, и я не знаю, как здесь применяется алгоритм.
Мое текущее решение выглядит следующим образом:
-
Предварительно обработайте список таким образом, чтобы мы имели хэш-карту, которая указывает местоположение (слева), на список местоположений (справа)
-
Создайте хэш-карту, чтобы отслеживать "посещенные местоположения". Создайте список для хранения найденных путей.
-
Хранить X (начальное местоположение) в hashmap "посещенных мест".
-
Найдите X в первом хэшмапе, (местоположение A даст нам (B, C, Q) в O (1) раз).
-
Для каждого найденного местоположения (B, C, Q) проверьте, является ли он конечным пунктом назначения (Z). Если это сохранить его в списке "найденные пути". Иначе, если он еще не существует в hashmap "посещенных мест", Recurl до шага 3 теперь с этим местом как "X". (фактический код ниже)
В этом текущем решении требуется навсегда сопоставить все (не кратчайшие) возможные маршруты от "BKI" до "SIN" для это предоставило данные.
Мне было интересно, есть ли более эффективный (временный) способ сделать это. Кто-нибудь знает лучший алгоритм, чтобы найти все пути от произвольной позиции A до произвольной позиции Z?
Фактический код для текущего решения:
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);
}
}
}
}
}
