通过递归创建有效路径的完整列表
Creating a complete list of valid paths via recursion
我有一个 table 和它们的邻居，需要创建一个递归函数来找到 所有可能的路径 从开始 ID 到结束 ID 没有两次穿越相同的点。假设起始 ID 为 1，结束 ID 为 3。
{1 | 2,5}
{2 | 1,3,4,5}
{3 | 2,5}
{4 | 2}
{5 | 1,2,3}
当前由 @Jeffrey Phillips Freeman 编写的代码片段运行良好，只是它只有 returns 一个可能的路径，而不是所有可能的路径，即 (1,2,3) & (1 ,5,3).我被告知 A* 算法最适合这种情况，但我仍然想创建有效路径列表，这些路径将我从 A 点带到 B 点而不走那条路线。新代码片段需要简单地将 all 有效路径放入 ArrayList 中。我打算使用 ArrayList 通过考虑路径长度和其他因素来确定最佳路径。因此，按路径距离排序的 ArrayList 将是一个奖励。作为补充说明，实际问题中的节点附有空间坐标，但节点之间的路径并不总是直线。
List<Integer> searchHops(int from, int to, List<Integer> seen) {
seen.add(from);
if (from == to)
return new ArrayList<Integer>(Arrays.asList(from));
for (int neighbor : getNeighbors(from))
if (!seen.contains(neighbor)) {
List<Integer> result = searchHops(neighbor, to, seen);
if (result != null) {
result.add(0, from);
return result;
}
}
return null;
}
我有大约 200 分，在目前的状态下，从 A 点到 B 点（仅相距一个点）的简单测试让我踏上了 22 跳的旅程。
根本没有理由使用 A*。它旨在尽可能高效地找到最短路径。如果您想找到所有路径而不管长度，A* 将是开销，没有任何好处。
在伪代码中，您的算法应该类似于：
findPaths for path:
if path is complete
add to solution set
else
for each link from last step that is not in path
add next step to path
call findPaths
remove next step from path
目前您正在返回路径。如果要查找所有路径，则需要将其存储在路径列表中。
这是一个示例实现：
public class FindPath {
private final Stack<Integer> path = new Stack<>();
private final Map<Integer, Set<Integer>> links = new HashMap<>();
public void addLink(int from, int to) {
links.putIfAbsent(from, new HashSet<>());
links.get(from).add(to);
}
public void find(int from, int to, Consumer<Stack<Integer>> action) {
path.push(from);
if (from == to)
action.accept(path);
else
links.getOrDefault(from, Set.of()).stream()
.filter(s -> !path.contains(s))
.forEach(s -> find(s, to, action));
path.pop();
}
public static void main(String[] args) {
FindPath finder = new FindPath();
Random rand = new Random();
IntStream.range(0, 20).forEach(n -> rand.ints(7, 0, 20).forEach(t -> finder.addLink(n, t)));
finder.find(0, 19, System.out::println);
}
}
您可以将我的原始代码修改为return所有路径作为列表，就像您所要求的那样。只是没有提早获得代码 return。这不会按路径长度排序，但是，如果需要，则需要 A*.
public List<List<Integer>> searchHops(int from, int to, Set<Integer> seen) {
seen.add(from);
if (from == to) {
final List<List<Integer>> newList = new ArrayList<>();
newList.add(new ArrayList<>(Arrays.asList(from)));
return newList;
}
List<List<Integer>> allPaths = null;
for (int neighbor : getNeighbors(from)) {
if (!seen.contains(neighbor)) {
List<List<Integer>> results = searchHops(neighbor, to, new HashSet<>(seen));
if (results != null) {
for(List<Integer> result : results) {
result.add(0, from);
if( allPaths != null )
allPaths.add(result);
}
if( allPaths == null )
allPaths = results;
}
}
}
return allPaths;
}
如果您真的关心从最短路径到最长路径的路径排序，那么使用 A* 会好得多。 A* 将 return 尽可能多的可能路径，按照最短路径优先的顺序。因此，如果您真正想要的是从最短到最长的所有可能路径，那么您仍然需要 A* 算法。如果你关心从最短到最长的排序，我上面建议的代码会比它需要的慢得多，更不用说会占用更多 space 然后你想要一次存储所有可能的路径.
既然您表示您首先关心最短路径，并且可能想要检索 N 条最短路径，那么您绝对应该在此处使用 A*。
如果您想要一个基于 A* 的实现能够 returning 从最短到最长排序的所有路径，以下内容将实现这一点。它有几个优点。首先，它可以有效地从最短到最长进行排序。此外，它仅在需要时才计算每条附加路径，因此如果您因为不需要每条路径而提前停止，则可以节省一些处理时间。每次计算下一条路径时，它还会为后续路径重用数据，因此效率更高。如果您关心按路径长度排序，Overall 应该是最有效的算法。
import java.util.*;
public class AstarSearch {
private final Map<Integer, Set<Neighbor>> adjacency;
private final int destination;
private final NavigableSet<Step> pending = new TreeSet<>();
public AstarSearch(Map<Integer, Set<Neighbor>> adjacency, int source, int destination) {
this.adjacency = adjacency;
this.destination = destination;
this.pending.add(new Step(source, null, 0));
}
public List<Integer> nextShortestPath() {
Step current = this.pending.pollFirst();
while( current != null) {
if( current.getId() == this.destination )
return current.generatePath();
for (Neighbor neighbor : this.adjacency.get(current.id)) {
if(!current.seen(neighbor.getId())) {
final Step nextStep = new Step(neighbor.getId(), current, current.cost + neighbor.cost + predictCost(neighbor.id, this.destination));
this.pending.add(nextStep);
}
}
current = this.pending.pollFirst();
}
return null;
}
protected int predictCost(int source, int destination) {
return 0; //Behaves identical to Dijkstra's algorithm, override to make it A*
}
private static class Step implements Comparable<Step> {
final int id;
final Step parent;
final int cost;
public Step(int id, Step parent, int cost) {
this.id = id;
this.parent = parent;
this.cost = cost;
}
public int getId() {
return id;
}
public Step getParent() {
return parent;
}
public int getCost() {
return cost;
}
public boolean seen(int node) {
if(this.id == node)
return true;
else if(parent == null)
return false;
else
return this.parent.seen(node);
}
public List<Integer> generatePath() {
final List<Integer> path;
if(this.parent != null)
path = this.parent.generatePath();
else
path = new ArrayList<>();
path.add(this.id);
return path;
}
@Override
public int compareTo(Step step) {
if(step == null)
return 1;
if( this.cost != step.cost)
return Integer.compare(this.cost, step.cost);
if( this.id != step.id )
return Integer.compare(this.id, step.id);
if( this.parent != null )
this.parent.compareTo(step.parent);
if(step.parent == null)
return 0;
return -1;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Step step = (Step) o;
return id == step.id &&
cost == step.cost &&
Objects.equals(parent, step.parent);
}
@Override
public int hashCode() {
return Objects.hash(id, parent, cost);
}
}
/*******************************************************
* Everything below here just sets up your adjacency *
* It will just be helpful for you to be able to test *
* It isnt part of the actual A* search algorithm *
********************************************************/
private static class Neighbor {
final int id;
final int cost;
public Neighbor(int id, int cost) {
this.id = id;
this.cost = cost;
}
public int getId() {
return id;
}
public int getCost() {
return cost;
}
}
public static void main(String[] args) {
final Map<Integer, Set<Neighbor>> adjacency = createAdjacency();
final AstarSearch search = new AstarSearch(adjacency, 1, 4);
System.out.println("printing all paths from shortest to longest...");
List<Integer> path = search.nextShortestPath();
while(path != null) {
System.out.println(path);
path = search.nextShortestPath();
}
}
private static Map<Integer, Set<Neighbor>> createAdjacency() {
final Map<Integer, Set<Neighbor>> adjacency = new HashMap<>();
//This sets up the adjacencies. In this case all adjacencies have a cost of 1, but they dont need to. Otherwise
//They are exactly the same as the example you gave in your question
addAdjacency(adjacency, 1,2,1,5,1); //{1 | 2,5}
addAdjacency(adjacency, 2,1,1,3,1,4,1,5,1); //{2 | 1,3,4,5}
addAdjacency(adjacency, 3,2,1,5,1); //{3 | 2,5}
addAdjacency(adjacency, 4,2,1); //{4 | 2}
addAdjacency(adjacency, 5,1,1,2,1,3,1); //{5 | 1,2,3}
return Collections.unmodifiableMap(adjacency);
}
private static void addAdjacency(Map<Integer, Set<Neighbor>> adjacency, int source, Integer... dests) {
if( dests.length % 2 != 0)
throw new IllegalArgumentException("dests must have an equal number of arguments, each pair is the id and cost for that traversal");
final Set<Neighbor> destinations = new HashSet<>();
for(int i = 0; i < dests.length; i+=2)
destinations.add(new Neighbor(dests[i], dests[i+1]));
adjacency.put(source, Collections.unmodifiableSet(destinations));
}
}
以上代码的输出如下：
[1, 2, 4]
[1, 5, 2, 4]
[1, 5, 3, 2, 4]
请注意，每次调用 nextShortestPath() 时，它都会根据需要为您生成下一条最短路径。它只计算所需的额外步骤并且不会遍历任何旧路径两次。此外，如果您决定不需要所有路径并尽早结束执行，您就可以节省大量的计算时间。您最多只能计算所需的路径数。
如果您有某种启发式方法可以帮助您估算路径成本，那么请覆盖 predictCost() 方法并将其放在那里。您提到您的节点也有与之关联的空间坐标。在这种情况下，一个好的启发式方法是两个节点之间的欧氏距离（它们之间的直线距离）。然而，它完全是可选的，只有在计算所有可能的路径之前退出才有助于缩短计算时间。
最后需要注意的是，A* 和 Dijkstra 算法确实有一些小的限制，但我认为这不会影响您。也就是说，它不会在具有负权重的图表上正常工作。
这是 JDoodle 的 link，您可以在其中 运行 自己在浏览器中编写代码并查看其运行情况。您还可以更改图表以显示它也适用于其他图表：http://jdoodle.com/a/ukx
我有一个 table 和它们的邻居，需要创建一个递归函数来找到 所有可能的路径 从开始 ID 到结束 ID 没有两次穿越相同的点。假设起始 ID 为 1，结束 ID 为 3。
{1 | 2,5}
{2 | 1,3,4,5}
{3 | 2,5}
{4 | 2}
{5 | 1,2,3}
当前由 @Jeffrey Phillips Freeman 编写的代码片段运行良好，只是它只有 returns 一个可能的路径，而不是所有可能的路径，即 (1,2,3) & (1 ,5,3).我被告知 A* 算法最适合这种情况，但我仍然想创建有效路径列表，这些路径将我从 A 点带到 B 点而不走那条路线。新代码片段需要简单地将 all 有效路径放入 ArrayList 中。我打算使用 ArrayList 通过考虑路径长度和其他因素来确定最佳路径。因此，按路径距离排序的 ArrayList 将是一个奖励。作为补充说明，实际问题中的节点附有空间坐标，但节点之间的路径并不总是直线。
List<Integer> searchHops(int from, int to, List<Integer> seen) {
seen.add(from);
if (from == to)
return new ArrayList<Integer>(Arrays.asList(from));
for (int neighbor : getNeighbors(from))
if (!seen.contains(neighbor)) {
List<Integer> result = searchHops(neighbor, to, seen);
if (result != null) {
result.add(0, from);
return result;
}
}
return null;
}
我有大约 200 分，在目前的状态下，从 A 点到 B 点（仅相距一个点）的简单测试让我踏上了 22 跳的旅程。
根本没有理由使用 A*。它旨在尽可能高效地找到最短路径。如果您想找到所有路径而不管长度，A* 将是开销，没有任何好处。
在伪代码中，您的算法应该类似于：
findPaths for path:
if path is complete
add to solution set
else
for each link from last step that is not in path
add next step to path
call findPaths
remove next step from path
目前您正在返回路径。如果要查找所有路径，则需要将其存储在路径列表中。
这是一个示例实现：
public class FindPath {
private final Stack<Integer> path = new Stack<>();
private final Map<Integer, Set<Integer>> links = new HashMap<>();
public void addLink(int from, int to) {
links.putIfAbsent(from, new HashSet<>());
links.get(from).add(to);
}
public void find(int from, int to, Consumer<Stack<Integer>> action) {
path.push(from);
if (from == to)
action.accept(path);
else
links.getOrDefault(from, Set.of()).stream()
.filter(s -> !path.contains(s))
.forEach(s -> find(s, to, action));
path.pop();
}
public static void main(String[] args) {
FindPath finder = new FindPath();
Random rand = new Random();
IntStream.range(0, 20).forEach(n -> rand.ints(7, 0, 20).forEach(t -> finder.addLink(n, t)));
finder.find(0, 19, System.out::println);
}
}
您可以将我的原始代码修改为return所有路径作为列表，就像您所要求的那样。只是没有提早获得代码 return。这不会按路径长度排序，但是，如果需要，则需要 A*.
public List<List<Integer>> searchHops(int from, int to, Set<Integer> seen) {
seen.add(from);
if (from == to) {
final List<List<Integer>> newList = new ArrayList<>();
newList.add(new ArrayList<>(Arrays.asList(from)));
return newList;
}
List<List<Integer>> allPaths = null;
for (int neighbor : getNeighbors(from)) {
if (!seen.contains(neighbor)) {
List<List<Integer>> results = searchHops(neighbor, to, new HashSet<>(seen));
if (results != null) {
for(List<Integer> result : results) {
result.add(0, from);
if( allPaths != null )
allPaths.add(result);
}
if( allPaths == null )
allPaths = results;
}
}
}
return allPaths;
}
如果您真的关心从最短路径到最长路径的路径排序，那么使用 A* 会好得多。 A* 将 return 尽可能多的可能路径，按照最短路径优先的顺序。因此，如果您真正想要的是从最短到最长的所有可能路径，那么您仍然需要 A* 算法。如果你关心从最短到最长的排序，我上面建议的代码会比它需要的慢得多，更不用说会占用更多 space 然后你想要一次存储所有可能的路径.
既然您表示您首先关心最短路径，并且可能想要检索 N 条最短路径，那么您绝对应该在此处使用 A*。
如果您想要一个基于 A* 的实现能够 returning 从最短到最长排序的所有路径，以下内容将实现这一点。它有几个优点。首先，它可以有效地从最短到最长进行排序。此外，它仅在需要时才计算每条附加路径，因此如果您因为不需要每条路径而提前停止，则可以节省一些处理时间。每次计算下一条路径时，它还会为后续路径重用数据，因此效率更高。如果您关心按路径长度排序，Overall 应该是最有效的算法。
import java.util.*;
public class AstarSearch {
private final Map<Integer, Set<Neighbor>> adjacency;
private final int destination;
private final NavigableSet<Step> pending = new TreeSet<>();
public AstarSearch(Map<Integer, Set<Neighbor>> adjacency, int source, int destination) {
this.adjacency = adjacency;
this.destination = destination;
this.pending.add(new Step(source, null, 0));
}
public List<Integer> nextShortestPath() {
Step current = this.pending.pollFirst();
while( current != null) {
if( current.getId() == this.destination )
return current.generatePath();
for (Neighbor neighbor : this.adjacency.get(current.id)) {
if(!current.seen(neighbor.getId())) {
final Step nextStep = new Step(neighbor.getId(), current, current.cost + neighbor.cost + predictCost(neighbor.id, this.destination));
this.pending.add(nextStep);
}
}
current = this.pending.pollFirst();
}
return null;
}
protected int predictCost(int source, int destination) {
return 0; //Behaves identical to Dijkstra's algorithm, override to make it A*
}
private static class Step implements Comparable<Step> {
final int id;
final Step parent;
final int cost;
public Step(int id, Step parent, int cost) {
this.id = id;
this.parent = parent;
this.cost = cost;
}
public int getId() {
return id;
}
public Step getParent() {
return parent;
}
public int getCost() {
return cost;
}
public boolean seen(int node) {
if(this.id == node)
return true;
else if(parent == null)
return false;
else
return this.parent.seen(node);
}
public List<Integer> generatePath() {
final List<Integer> path;
if(this.parent != null)
path = this.parent.generatePath();
else
path = new ArrayList<>();
path.add(this.id);
return path;
}
@Override
public int compareTo(Step step) {
if(step == null)
return 1;
if( this.cost != step.cost)
return Integer.compare(this.cost, step.cost);
if( this.id != step.id )
return Integer.compare(this.id, step.id);
if( this.parent != null )
this.parent.compareTo(step.parent);
if(step.parent == null)
return 0;
return -1;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Step step = (Step) o;
return id == step.id &&
cost == step.cost &&
Objects.equals(parent, step.parent);
}
@Override
public int hashCode() {
return Objects.hash(id, parent, cost);
}
}
/*******************************************************
* Everything below here just sets up your adjacency *
* It will just be helpful for you to be able to test *
* It isnt part of the actual A* search algorithm *
********************************************************/
private static class Neighbor {
final int id;
final int cost;
public Neighbor(int id, int cost) {
this.id = id;
this.cost = cost;
}
public int getId() {
return id;
}
public int getCost() {
return cost;
}
}
public static void main(String[] args) {
final Map<Integer, Set<Neighbor>> adjacency = createAdjacency();
final AstarSearch search = new AstarSearch(adjacency, 1, 4);
System.out.println("printing all paths from shortest to longest...");
List<Integer> path = search.nextShortestPath();
while(path != null) {
System.out.println(path);
path = search.nextShortestPath();
}
}
private static Map<Integer, Set<Neighbor>> createAdjacency() {
final Map<Integer, Set<Neighbor>> adjacency = new HashMap<>();
//This sets up the adjacencies. In this case all adjacencies have a cost of 1, but they dont need to. Otherwise
//They are exactly the same as the example you gave in your question
addAdjacency(adjacency, 1,2,1,5,1); //{1 | 2,5}
addAdjacency(adjacency, 2,1,1,3,1,4,1,5,1); //{2 | 1,3,4,5}
addAdjacency(adjacency, 3,2,1,5,1); //{3 | 2,5}
addAdjacency(adjacency, 4,2,1); //{4 | 2}
addAdjacency(adjacency, 5,1,1,2,1,3,1); //{5 | 1,2,3}
return Collections.unmodifiableMap(adjacency);
}
private static void addAdjacency(Map<Integer, Set<Neighbor>> adjacency, int source, Integer... dests) {
if( dests.length % 2 != 0)
throw new IllegalArgumentException("dests must have an equal number of arguments, each pair is the id and cost for that traversal");
final Set<Neighbor> destinations = new HashSet<>();
for(int i = 0; i < dests.length; i+=2)
destinations.add(new Neighbor(dests[i], dests[i+1]));
adjacency.put(source, Collections.unmodifiableSet(destinations));
}
}
以上代码的输出如下：
[1, 2, 4]
[1, 5, 2, 4]
[1, 5, 3, 2, 4]
请注意，每次调用 nextShortestPath() 时，它都会根据需要为您生成下一条最短路径。它只计算所需的额外步骤并且不会遍历任何旧路径两次。此外，如果您决定不需要所有路径并尽早结束执行，您就可以节省大量的计算时间。您最多只能计算所需的路径数。
如果您有某种启发式方法可以帮助您估算路径成本，那么请覆盖 predictCost() 方法并将其放在那里。您提到您的节点也有与之关联的空间坐标。在这种情况下，一个好的启发式方法是两个节点之间的欧氏距离（它们之间的直线距离）。然而，它完全是可选的，只有在计算所有可能的路径之前退出才有助于缩短计算时间。
最后需要注意的是，A* 和 Dijkstra 算法确实有一些小的限制，但我认为这不会影响您。也就是说，它不会在具有负权重的图表上正常工作。
这是 JDoodle 的 link，您可以在其中 运行 自己在浏览器中编写代码并查看其运行情况。您还可以更改图表以显示它也适用于其他图表：http://jdoodle.com/a/ukx