Path finding Exercises#

Consider the graph shown above. The links are annotated to show their cost (for instance the link between D and G has a cost 6). The figures in brackets next to the nodes represent heuristic estimates of the distance from those nodes to the node G (don’t worry about how we arrived at these estimates, we just did). Assume that the method we use never overestimates the distance to G (i.e. it is admissible).

Exercise 1#

Using a similar notation to that used in the lecture, show the sequence of steps by which Dijkstra’s algorithm would calculate the shortest path from A to G. Note that you do not need to make use of the heuristics to answer this part of the question. If you have a choice about which node is at the front of the “Open” set priority queue (because two nodes have the same g-value) then pick the one that comes lowest in the alphabet.

Exercise 2#

Now show the sequence of steps by which the A* algorithm would calculate the shortest path.

Reference Answer#

1
// Command-line flags:
2
// -g <graphFile>: specify a graph file (format: each non-empty non-comment line: FROM TO WEIGHT)
3
// -h <heuristicFile>: specify a heuristic file (format: each non-empty non-comment line: NODE H)
4
// If no files provided, uses built-in graph and heuristics from the diagram in the lecture slides.
5
import java.util.*;
6
import java.io.*;
7

8
public class pathFinding {
9

10
  static class Edge { String to; int w; Edge(String to, int w){this.to=to;this.w=w;} }
11

12
  // Build the directed graph corresponding to the diagram
13
  private static Map<String, List<Edge>> buildGraph() {
14
    Map<String, List<Edge>> g = new HashMap<>();
15
    for (String name: Arrays.asList("A","B","C","D","E","F","G")) g.put(name, new ArrayList<>());
16

17
    // From diagram (directed): A->B(2), A->C(2), A->D(1)
18
    g.get("A").add(new Edge("B",2));
19
    g.get("A").add(new Edge("C",2));
20
    g.get("A").add(new Edge("D",1));
21

22
    // B->D(1), B->E(1)
23
    g.get("B").add(new Edge("D",1));
24
    g.get("B").add(new Edge("E",1));
25

26
    // C->D(1), C->F(2)
27
    g.get("C").add(new Edge("D",1));
28
    g.get("C").add(new Edge("F",2));
29

30
    // D->G(6)
31
    g.get("D").add(new Edge("G",6));
32

33
    // E->G(3)
34
    g.get("E").add(new Edge("G",3));
35

36
    // F->G(1)
37
    g.get("F").add(new Edge("G",1));
38

39
    return g;
40
  }
41

42
  // Utility: produce the Open list ordered by (g, alphabetical) for printing
43
  private static String formatOpen(Map<String,Integer> dist, Set<String> closed) {
44
    List<String> nodes = new ArrayList<>();
45
    for (String n: dist.keySet()) if (!closed.contains(n) && dist.get(n) < Integer.MAX_VALUE) nodes.add(n);
46
    nodes.sort((x,y)->{
47
      int dx = dist.get(x), dy = dist.get(y);
48
      if (dx!=dy) return Integer.compare(dx,dy);
49
      return x.compareTo(y);
50
    });
51
    StringBuilder sb = new StringBuilder("{");
52
    for (int i=0;i<nodes.size();i++){
53
      String n = nodes.get(i);
54
      sb.append(n).append("(").append(dist.get(n)).append(")");
55
      if (i<nodes.size()-1) sb.append(", ");
56
    }
57
    sb.append("}");
58
    return sb.toString();
59
  }
60

61
  // Dijkstra with verbose trace
62
  private static void dijkstraTrace(Map<String,List<Edge>> graph, String start, String goal) {
63
    // distances and parents
64
    Map<String,Integer> dist = new HashMap<>();
65
    Map<String,String> parent = new HashMap<>();
66
    for (String v: graph.keySet()) { dist.put(v, Integer.MAX_VALUE); parent.put(v, null); }
67
    dist.put(start, 0);
68

69
    // Priority queue entries; comparator by (dist, name) using current dist map for tie-breaking
70
    PriorityQueue<String> pq = new PriorityQueue<>((x,y)->{
71
      int dx = dist.get(x), dy = dist.get(y);
72
      if (dx!=dy) return Integer.compare(dx,dy);
73
      return x.compareTo(y);
74
    });
75
    pq.add(start);
76

77
    Set<String> closed = new LinkedHashSet<>();
78

79
    System.out.println("Initial state:");
80
    System.out.println("g("+start+")=0; all others = ∞");
81
    System.out.println("Open = {"+start+"(0)}; Closed = {}");
82
    System.out.println();
83

84
    while (!pq.isEmpty()){
85
      String u = pq.poll();
86
      // skip stale entries: if u already closed or its dist is infinite, continue
87
      if (closed.contains(u)) continue;
88
      if (dist.get(u)==Integer.MAX_VALUE) continue;
89

90
      // Pop u
91
      System.out.println("Pop " + u + " (g=" + dist.get(u) + ")");
92
      closed.add(u);
93

94
      // Relax neighbors
95
      for (Edge e: graph.get(u)){
96
        String v = e.to; int w = e.w;
97
        int tentative = dist.get(u) + w;
98
        System.out.print("  Relax "+u+" -> "+v+" (w="+w+"): ");
99
        if (tentative < dist.get(v)){
100
          System.out.println("update g("+v+") from " + (dist.get(v)==Integer.MAX_VALUE?"∞":dist.get(v)) + " to " + tentative + ", parent("+v+")="+u);
101
          dist.put(v, tentative);
102
          parent.put(v, u);
103
          pq.remove(v); // remove stale if present
104
          pq.add(v);
105
        } else {
106
          System.out.println("no update (tentative="+tentative+", current=" + (dist.get(v)==Integer.MAX_VALUE?"∞":dist.get(v)) + ")");
107
        }
108
      }
109

110
      // Print Open and Closed (Open computed from dist/closed for clarity)
111
      String openStr = formatOpen(dist, closed);
112
      System.out.println("  Open = " + openStr + "; Closed = " + closed);
113
      System.out.println();
114

115
      if (u.equals(goal)) break; // stop when goal popped
116
    }
117

118
    if (dist.get(goal)==Integer.MAX_VALUE) {
119
      System.out.println("No path from " + start + " to " + goal);
120
      return;
121
    }
122

123
    // Reconstruct path
124
    List<String> path = new ArrayList<>();
125
    for (String at = goal; at!=null; at = parent.get(at)) path.add(at);
126
    Collections.reverse(path);
127
    System.out.println("Shortest path: " + String.join(" -> ", path) + " with total cost " + dist.get(goal));
128
  }
129

130
    // Heuristics from diagram (admissible)
131
    private static Map<String,Integer> buildHeuristics() {
132
      Map<String,Integer> h = new HashMap<>();
133
      h.put("A", 4);
134
      h.put("B", 4);
135
      h.put("C", 3);
136
      h.put("D", 2);
137
      h.put("E", 2);
138
      h.put("F", 1);
139
      h.put("G", 0);
140
      return h;
141
    }
142

143
    private static String formatOpenAStar(Map<String,Integer> dist, Set<String> closed, Map<String,Integer> h) {
144
      List<String> nodes = new ArrayList<>();
145
      for (String n: dist.keySet()) if (!closed.contains(n) && dist.get(n) < Integer.MAX_VALUE) nodes.add(n);
146
      nodes.sort((x,y)->{
147
        int fx = dist.get(x) + h.getOrDefault(x, 0);
148
        int fy = dist.get(y) + h.getOrDefault(y, 0);
149
        if (fx!=fy) return Integer.compare(fx,fy);
150
        return x.compareTo(y);
151
      });
152
      StringBuilder sb = new StringBuilder("{");
153
      for (int i=0;i<nodes.size();i++){
154
        String n = nodes.get(i);
155
        int gx = dist.get(n);
156
        int hx = h.getOrDefault(n, 0);
157
        int fx = gx + hx;
158
        sb.append(n).append("(").append(gx).append("/"+hx+"="+fx+")");
159
        if (i<nodes.size()-1) sb.append(", ");
160
      }
161
      sb.append("}");
162
      return sb.toString();
163
    }
164

165
    // A* with verbose trace
166
    private static void aStarTrace(Map<String,List<Edge>> graph, Map<String,Integer> h, String start, String goal) {
167
      Map<String,Integer> dist = new HashMap<>();
168
      Map<String,String> parent = new HashMap<>();
169
      for (String v: graph.keySet()) { dist.put(v, Integer.MAX_VALUE); parent.put(v, null); }
170
      dist.put(start, 0);
171

172
      PriorityQueue<String> pq = new PriorityQueue<>((x,y)->{
173
        int fx = (dist.get(x)==Integer.MAX_VALUE?Integer.MAX_VALUE:dist.get(x)+h.get(x));
174
        int fy = (dist.get(y)==Integer.MAX_VALUE?Integer.MAX_VALUE:dist.get(y)+h.get(y));
175
        if (fx!=fy) return Integer.compare(fx,fy);
176
        return x.compareTo(y);
177
      });
178
      pq.add(start);
179

180
      Set<String> closed = new LinkedHashSet<>();
181

182
      System.out.println("A* initial state:");
183
      System.out.println("g("+start+")=0; h("+start+")="+h.getOrDefault(start,0)+"; f="+(0+h.getOrDefault(start,0)));
184
      System.out.println("Open = {"+start+"(0/"+h.getOrDefault(start,0)+"="+(0+h.getOrDefault(start,0))+")}; Closed = {}");
185

186
      System.out.println();
187

188
      while (!pq.isEmpty()){
189
        String u = pq.poll();
190
        if (closed.contains(u)) continue;
191
        if (dist.get(u)==Integer.MAX_VALUE) continue;
192

193
        int fu = dist.get(u) + h.getOrDefault(u,0);
194
        System.out.println("Pop " + u + " (g=" + dist.get(u) + ", h="+h.getOrDefault(u,0)+", f="+fu+")");
195

196
        closed.add(u);
197

198
        if (u.equals(goal)) {
199
          System.out.println("  Goal popped; terminating.");
200
          break;
201
        }
202

203

204

205
        for (Edge e: graph.get(u)){
206
          String v = e.to; int w = e.w;
207
          int tentative = dist.get(u) + w;
208
          int fTent = tentative + h.getOrDefault(v,0);
209
          System.out.print("  Relax "+u+" -> "+v+" (w="+w+"): ");
210
          if (tentative < dist.get(v)){
211
            System.out.println("update g("+v+") from " + (dist.get(v)==Integer.MAX_VALUE?"∞":dist.get(v)) + " to " + tentative + ", h("+v+")="+h.getOrDefault(v,0)+", f="+fTent+", parent("+v+")="+u);
212
            dist.put(v, tentative);
213
            parent.put(v, u);
214
            pq.remove(v);
215
            pq.add(v);
216
          } else {
217
            System.out.println("no update (tentative="+tentative+", current=" + (dist.get(v)==Integer.MAX_VALUE?"∞":dist.get(v)) + ")");
218
          }
219
        }
220

221
        String openStr = formatOpenAStar(dist, closed, h);
222
        System.out.println("  Open = " + openStr + "; Closed = " + closed);
223
        System.out.println();
224
      }
225

226
      if (dist.get(goal)==Integer.MAX_VALUE) {
227
        System.out.println("No path from " + start + " to " + goal);
228
        return;
229
      }
230

231
      List<String> path = new ArrayList<>();
232
      for (String at = goal; at!=null; at = parent.get(at)) path.add(at);
233
      Collections.reverse(path);
234
      System.out.println("A* Shortest path: " + String.join(" -> ", path) + " with total cost " + dist.get(goal));
235
    }
236

237
    // Read graph from a simple text file: each non-empty non-comment line: FROM TO WEIGHT
238
    private static Map<String, List<Edge>> readGraphFromFile(String path) throws Exception {
239
      Map<String,List<Edge>> g = new HashMap<>();
240
      try (BufferedReader br = new BufferedReader(new java.io.FileReader(path))) {
241
        String line;
242
        while ((line = br.readLine())!=null) {
243
          line = line.trim();
244
          if (line.isEmpty() || line.startsWith("#")) continue;
245
          String[] parts = line.split("\\s+");
246
          if (parts.length < 3) throw new IllegalArgumentException("Invalid graph line: '"+line+"' (expected: FROM TO WEIGHT)");
247
          String from = parts[0];
248
          String to = parts[1];
249
          int w = Integer.parseInt(parts[2]);
250
          g.putIfAbsent(from, new ArrayList<>());
251
          g.putIfAbsent(to, new ArrayList<>());
252
          g.get(from).add(new Edge(to, w));
253
        }
254
      }
255
      return g;
256
    }
257

258
    // Read heuristics file: each non-empty non-comment line: NODE H
259
    private static Map<String,Integer> readHeuristics(String path) throws Exception {
260
      Map<String,Integer> h = new HashMap<>();
261
      try (BufferedReader br = new BufferedReader(new java.io.FileReader(path))) {
262
        String line;
263
        while ((line = br.readLine())!=null) {
264
          line = line.trim();
265
          if (line.isEmpty() || line.startsWith("#")) continue;
266
          String[] parts = line.split("\\s+");
267
          if (parts.length < 2) throw new IllegalArgumentException("Invalid heuristic line: '"+line+"' (expected: NODE H)");
268
          String node = parts[0];
269
          int val = Integer.parseInt(parts[1]);
270
          h.put(node, val);
271
        }
272
      }
273
      return h;
274
    }
275

276
  public static void main(String[] args) {
277
    // Determine input sources: support command-line flags:
278
    // -g <graphFile> -h <heuristicFile>
279
    String graphFile = null;
280
    String heurFile = null;
281
    for (int i=0;i<args.length;i++){
282
      if ("-g".equals(args[i]) && i+1<args.length) { graphFile = args[++i]; }
283
      else if ("--graph".equals(args[i]) && i+1<args.length) { graphFile = args[++i]; }
284
      else if ("-h".equals(args[i]) && i+1<args.length) { heurFile = args[++i]; }
285
      else if ("--heuristic".equals(args[i]) && i+1<args.length) { heurFile = args[++i]; }
286
    }
287

288
    Map<String,List<Edge>> graph;
289
    Map<String,Integer> h = null;
290
    if (graphFile!=null) {
291
      try {
292
        graph = readGraphFromFile(graphFile);
293
        System.out.println("Loaded graph from: " + graphFile);
294
      } catch (Exception e) {
295
        System.err.println("Failed to read graph file '"+graphFile+"': "+e.getMessage());
296
        System.err.println("Falling back to default graph.");
297
        graph = buildGraph();
298
      }
299
    } else {
300
      graph = buildGraph();
301
      System.out.println("Using default graph built into program.");
302
    }
303

304
    if (heurFile!=null) {
305
      try {
306
        h = readHeuristics(heurFile);
307
        System.out.println("Loaded heuristics from: " + heurFile);
308
      } catch (Exception e) {
309
        System.err.println("Failed to read heuristic file '"+heurFile+"': "+e.getMessage());
310
        System.err.println("Falling back to default heuristics (if available).");
311
        h = buildHeuristics();
312
      }
313
    } else {
314
      // If no heuristic file provided, use default heuristics when running A*; otherwise A* will still run but with missing nodes defaulting to 0
315
      h = buildHeuristics();
316
      System.out.println("Using default heuristics built into program.");
317
    }
318

319
    // Run Dijkstra from A to G and print detailed trace
320
    dijkstraTrace(graph, "A", "G");
321

322
    System.out.println();
323
    // Run A* from A to G and print detailed trace
324
    aStarTrace(graph, h, "A", "G");
325
  }
326
}

1
# Sample graph matching the diagram
2
# Format: FROM TO WEIGHT
3
A B 2
4
A C 2
5
A D 1
6
B D 1
7
B E 1
8
C D 1
9
C F 2
10
D G 6
11
E G 3
12
F G 1

1
# Sample heuristics matching the diagram
2
# Format: NODE H
3
A 4
4
B 4
5
C 3
6
D 2
7
E 2
8
F 1
9
G 0

音乐

音乐

Path finding Exercises#

Exercise 1#

Exercise 2#

Reference Answer#

支持与分享

评论区

音乐

文章目录