List of Algorithms
1.1 Computing the approximation of the relaxed planning heuristic 34
2.1 Skeleton of search algorithms in implicitly given graphs 49
2.2 Tracing back the solution path using predecessor links 50
2.3 Improve procedure with duplicate detection and predecessor links 50
2.4 Choosing path to v through minimum of f(v) and f(u) + w(u, v) 54
2.5 An update routine that copes with negative edge weights 57
2.6 Relaxing the node expansion order in Algorithm A 59
2.7 Edge relaxation for implicit version of Bellman and Ford's algorithm 61
2.8 Bellman-Ford algorithm in an implicit graph 62
2.9 Floyd-Warshall algorithm 63
2.10 Pairwise sequence alignment with dynamic programming in column order 64
2.11 Policy iteration 67
2.12 Value iteration 68
2.13 A* 70
3.1 Initializing a 1-Level Bucket 91
3.2 Inserting an element into a 1-Level Bucket 91
3.3 Deleting the minimum element in a 1-Level Bucket 91
3.4 Updating the key in a 1-Level Bucket 92
3.5 Creating a Radix Heap 94
3.6 Inserting an element into a Radix Heap 94
3.7 Inserting an element into a Radix Heap 94
3.8 Delete the minimum from a Radix Heap 95
3.9 Finding the successor in a Van Emde Boas Priority Queue 96
3.10 Inserting an element in a Van Emde Boas Priority Queue 97
3.11 Deleting an element from a Van Emde Boas Priority Queue 97
3.12 Inserting an element into a Heap 99
3.13 Decreasing the key of an element in a Heap 99
3.14 Extracting the minimum element from a Heap 100
3.15 Rearrange Heap 100
3.16 Rearrange Pairing Heap 101
3.17 Implementation of different subroutines for Weak Heaps 103
3.18 Restoration of Weak Heaps 103
3.19 Extracting the minimum element from a Weak Heap 104
3.20 Inserting an element into a Weak Heap 104
3.21 Decreasing the key of an element in a Weak Heap 105
3.22 Consolidation with bitvectors and heuristic factor in a Fibonacci Heap 106
3.23 Reducing number of markings in a Relaxed Weak Queue 110
3.24 Algorithm of Rabin and Karp 114
3.25 Rank operation for permutations 119
3.26 Unrank operation for permutations 120
3.27 Recursion-free unranking and signature computation 120
3.28 Recursion-free ranking operation for permutations 122
3.29 Searching a chained hash table 122
3.30 Inserting an element into a chained hash table 122
3.31 Deleting an element from a chained hash table 123
3.32 Searching an element in an open hash table 124
3.33 Inserting an element into an open hash table 125
3.34 Deleting an element from an open hash table 125
3.35 Inserting an element for ordered hashing 125
3.36 Lookup for a key in a cuckoo hash table 128
3.37 Inserting a key into a cuckoo hash table 130
3.38 Searching a Trie for a partial match 140
3.39 Searching a hash table for a partial match 140
3.40 Inserting a set in an Unlimited Branching Tree 142
3.41 Searching for subsets in an Unlimited Branching Tree 142
3.42 Algorithm to construct a Suffix Tree in linear time 145
3.43 Insertion of one suffix in a Generalized Suffix Tree 149
3.44 Deleting a string in a Generalized Suffix Tree 150
4.1 Construction of pattern database using a backward search 168
4.2 Pattern database construction in directed and weighted problem graphs 171
5.1 Computing the BFS level with logarithmic space 196
5.2 Searching the shortest paths with logarithmic space 197
5.3 Depth-first branch-and-bound algorithm 199
5.4 Depth-first branch-and-bound subroutine 200
5.5 Depth-first iterative-deepening algorithm 202
5.6 DFS subroutine for DFID search 202
5.7 Driver loop for IDA* 204
5.8 The IDA* algorithm (no duplicate detection) 205
5.9 The RBFS algorithm, implemented recursively 220
6.1 IDA* driver with transposition table 230
6.2 IDA* with transposition table and cost revision 230
6.3 Fringe search algorithm 232
6.4 Algorithm ITS 234
6.5 Pruning nodes in ITS 235
6.6 Procedure SMAG 237
6.7 Update procedure in SMAG for newly generated nodes 238
6.8 Deleting unpromising nodes in SMAG 239
6.9 Backing up heuristic values in SMAG 239
6.10 Recursive deletion of unused Closed nodes 239
6.11 Enforced hill-climbing 241
6.12 BFS searching for a better state v 241
6.13 A* search with i-values 245
6.14 A* with an arbitrary overconsistent initialization 246
6.15 Subroutine for anytime repairing A* 248
6.16 Main function of anytime repairing A* 248
6.17 Algorithm k-best-first search 250
6.18 Algorithm k-beam search 252
6.19 A* search with (single) bit-state hashing 253
6.20 Partial IDA* search with (single) bit-state hashing 254
6.21 Dynamic programming search algorithm 256
6.22 Edge relaxation step in dynamic programming 256
6.23 Solution reconstruction in sparse-memory graph search 260
6.24 Improve procedure for SMGS 261
6.25 Pruning the list of expanded nodes in SMGS 261
6.26 Breadth-first heuristic search 263
6.27 Update of a problem graph edge in Algorithm 6.26 264
6.28 The beam-stack search algorithm 269
6.29 Algorithm PEA* 271
6.30 Update procedure in PEA* for newly generated nodes 272
6.31 Breadth-first search with two bits 272
6.32 Extended IDA* 276
6.33 Traversing the search space with one bit per state 279
7.1 BDD arithmetics via fixpoint computation 290
7.2 Symbolic breadth-first tree search implemented with BDDs 292
7.3 Symbolic BFS 293
7.4 Symbolic pattern database construction 295
7.5 Cost-optimal symbolic BFS algorithm 297
7.6 Dijkstra's algorithm implemented with BDDs 299
7.7 A* implemented with BDDs 303
7.8 Symbolic A* in a bucket implementation 306
7.9 Greedy best-first search implemented with BDDs 307
7.10 Symbolic breadth-first branch-and-bound with buckets 308
7.11 Relational product algorithm to compute the image of a state set 314
7.12 Dijkstra's algorithm on buckets 316
7.13 Shortest path A* algorithm on buckets 316
8.1 External BFS by Munagala and Ranade 327
8.2 Delayed duplicate detection algorithm for BFS 329
8.3 File subtraction for external duplicate elimination 330
8.4 External breadth-first branch-and-bound 331
8.5 Main routine for external enforced hill-climbing 333
8.6 External BFS searching for a better state v 333
8.7 External A* for consistent and integral heuristics 338
8.8 External value iteration algorithm 350
8.9 External value iteration—backward update 352
9.1 Algorithm to compute a1 + ⋯ + an in parallel 372
9.2 Algorithm to compute all prefix sums in parallel 373
9.3 Transposition-driven scheduling 376
9.4 The depth-slicing parallelization method 377
9.5 Searching and inserting an element in a lock-free hash table 379
9.6 Parallel branch-and-bound with global synchronization 380
9.7 Parallel DFS with stack splitting 381
9.8 Parallel IDA* with global synchronization 383
9.9 Distributing IDA* with respect to different search thresholds 383
9.10 Parallel external breadth-first search 390
9.11 Parallel external A* for consistent and integral heuristics 396
9.12 Large-scale breadth-first search on the GPU 403
9.13 Expanding a layer on the GPU 404
9.14 Detecting duplicates via sorting on the GPU 404
9.15 Bidirectional search with BHPA 410
9.16 Bidirectional BFS implemented with BDDs 417
10.1 Computation of failure function 437
10.2 Incremental learning of duplicates in A* 439
10.3 Bottom-up propagation in the search decomposition tree 443
10.4 The decomposition and bottom-up propagation algorithm 444
10.5 An algorithm for checking ample sets 455
11.1 LRTA* 471
11.2 Value-update step of LRTA* 472
11.3 LRTA* with lookahead one 474
11.4 Min-LRTA* 482
11.5 RTAA* 485
11.6 Variant of LRTA* (1) 489
11.7 FALCONS 490
11.8 Variant of LRTA* (2) 513
11.9 Variant of LRTA* (3) 514
12.1 The negmax game tree labeling procedure 525
12.2 Minimax game tree search 525
12.3 αβ negmax game tree pruning 527
12.4 Minimax game tree search with αβ-pruning 528
12.5 Negmax game tree search with αβ-pruning and transposition table 531
12.6 Principal-variation search in negmax formulation 532
12.7 MTD algorithm framework 533
12.8 The minimax game tree search procedure for accumulated node evaluations 535
12.9 Partition search 536
12.10 One iteration in the UCT algorithm 539
12.11 Temporal difference learning 541
12.12 Q-learning 543
12.13 Calculating the set of reachable positions 546
12.14 Classification 547
12.15 The αβ-branch-and-bound algorithm for multiplayer games 550
12.16 The AO* search algorithm for AND/OR trees 555
12.17 The AO* search algorithm for stochastic shortest path 556
12.18 The IDAO* search algorithm 556
12.19 The IDAO*-DFS search subroutine 557
12.20 The LAO* algorithm 558
13.1 Simple consistency algorithm 575
13.2 Arc consistency with AC-3 576
13.3 Arc consistency with AC-8 577
13.4 Algorithm for path consistency 580
13.5 Backtracking search algorithm 582
13.6 Pure backtracking search algorithm 582
13.7 Backjumping search algorithm 584
13.8 Simple consistency for backjumping 585
13.9 Backmarking search algorithm 587
13.10 One iteration in limited discrepancy search 589
13.11 One iteration in improved limited discrepancy search 590
13.12 Depth-bounded discrepancy search 592
13.13 Algorithm of Davis-Putnam and Logmann-Loveland 594
13.14 Computing strong and weak backdoors 596
13.15 Recursive computation of feasible sets for bin completion 600
13.16 Minimal network computation in simple temporal network 611
13.17 Computing the critical path with PERT scheduling 612
13.18 Formula progression algorithm 614
13.19 LTL path constraint solver 615
13.20 BDD construction algorithm for linear and bound arithmetic constraint 628
14.1 Hill-climbing 635
14.2 Simulated annealing 637
14.3 Tabu search 638
14.4 Randomized tabu search 639
14.5 Randomized local search 640
14.6 Randomized (1 + 1) EA 641
14.7 Simple GA on solution strings 643
14.8 Deterministic approximation algorithm for MAX-k-SAT 647
14.9 Monien-Speckenmeyer algorithm 648
14.10 Algorithm of Paturi, Pudlák, and Zane 648
14.11 Hamming sphere algorithm 649
14.12 Algorithm random walk 651
14.13 The ant system algorithm for solving TSP 653
14.14 Flood algorithm 655
14.15 Vertex ant walk 655
14.16 Saddle-point iteration method for finding a CLM 660
14.17 Lagrangian method for finding a CLM 662
15.1 Max-atom heuristic 679
15.2 Approximation of a plan with causal graph 688
15.3 Plan graph construction for numerical relaxed planning heuristic 691
15.4 Extraction of a numerical relaxed plan 692
15.5 Fixpoint for applying a set of rules to a planning state 696
16.1 The unification algorithm for first-order logic 731
16.2 Resolution refutation procedure 731
16.3 Functional implementation of the A* algorithm 734
17.1 Creating shortest path containers 750
17.2 Bounding-box graph search algorithm 751
17.3 Access operations on Heap of Heaps 753
17.4 Maintenance of active heap 754
18.1 Iterative-deepening dynamic programming 765
18.2 Edge expansion in IDDP 765
18.3 Edge relaxation step for IDDP 766
18.4 Recursive deletion of edges that are no longer part of any solution path 766
18.5 Divide-and-conquer solution reconstruction in reverse order 767
18.6 Sparsification of Closed list under restricted memory 768
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.