Introduction to Search Algorithms

Cover......Page 1
Half Title Page......Page 3
Full Title Page......Page 5
Copyright Page......Page 6
About the Author......Page 7
Table of Contents......Page 9
List of Figures......Page 13
List of Tables......Page 17
Preface......Page 19
Chapter 1 Fundamentals of Search Algorithms......Page 21
1.1. Introduction......Page 22
1.2. Unordered Linear Search......Page 23
1.3. Ordered Linear Search......Page 24
1.4. Chunk Search......Page 25
1.5. Binary Search......Page 27
1.6. Searching in Graphs......Page 28
1.7. Graph Grep......Page 33
1.8. Searching in Trees......Page 35
1.9. Searching in Temporal Probabilistic Object Data Model......Page 38
References......Page 40
Chapter 2 Fundamentals of Linear Search Algorithm......Page 55
2.1. Introduction......Page 56
2.2. Theory of The Linear Search Algorithm......Page 58
2.3. Modified Linear Search Technique With One Middle Component......Page 59
2.4. Modified Linear Search Technique With Two Middle Components......Page 61
2.6. Proof of Accuracy for Two-Way Linear Search......Page 65
2.7. Analysis And Comparison of Performance......Page 66
References......Page 68
Chapter 3 Introduction To A* Based Best-First Search Algorithms......Page 75
3.2. Best-First Heuristic Search: A*......Page 76
3.3. Classes......Page 77
3.4. A* Algorithm: An Overview......Page 85
References......Page 87
Chapter 4 A Fast Search Algorithm For A Large Fuzzy Database......Page 97
4.1. Introduction......Page 98
4.2. Previous Work on Fast Search Algorithms......Page 100
4.3. Algorithms......Page 103
4.4. Theoretical Results of Algorithms......Page 110
4.5. Experiment Results of Algorithms......Page 111
4.6. Comparison of Results......Page 116
References......Page 120
Chapter 5 Real-Time Heuristic Search Algorithms For Video Games’ Pathfinding......Page 133
5.1. Introduction......Page 134
5.2. Problem Formulation......Page 136
5.3. The Core Algorithms......Page 138
5.4. k Nearest Neighbors LRTA* (kNN LRTA*)......Page 141
5.5. Time-Bounded A* (TBA*)......Page 150
References......Page 158
Chapter 6 Real-Time Iterative-Deepening Best-First Search (RIBS)......Page 173
6.1. Introduction......Page 174
6.2. RIBS: Intuition......Page 176
6.3. Properties of RIBS......Page 179
6.4. Empirical Evaluation of RIBS In Heuristic Depressions......Page 180
References......Page 183
Chapter 7 Running Particle Swarm Optimization On Graphics Processing Units......Page 189
7.1. Introduction......Page 190
7.2. Particle Swarm Optimization......Page 191
7.3. Our GPU-Based Particle Swarm Optimization Proposals......Page 198
7.4. Experimental Approaches For Algorithms......Page 209
References......Page 216
Chapter 8 Search Via Quantum Walk......Page 227
8.1. Introduction......Page 228
8.2. Quantum Walk......Page 229
8.3. Search Algorithm Via Quantum Walk......Page 237
8.4. Physical Implementation of Quantum Walk Based Search......Page 239
8.5. Quantum Walk Based Search in Nature......Page 244
8.6. Biomimetic Application in Solar Energy......Page 247
References......Page 249
Index......Page 255