design_patterns_for_searching_in_csharp.pdf

(1334 KB) Pobierz
all
Design Patterns
for
Searching in C#
By Fred Mellender
660345125.001.png
Copyright ¨ 2008 by Fred Mellender. All rights reserved.
Contact the author at fredm73@hotmail.com .
You can download the source code and the SEL library at:
http://www.lulu.com/content/2008403
Source code may be freely used, copied, and modified. However, no
warranty is given as to its suitability or accuracy.
The source code was compiled under MicrosoftÓs Visual Studio 2005,
Standard Edition (C#), and uses generics, iterators, and anonymous
methods.
ISBN: 978-1-4357-2301-6
 
Contents
Preface...........................................................................................................vii
1 Permutations...............................................................................................11
Design Patterns.........................................................................................12
Permutations.............................................................................................13
Lexigraphical Order and ÐCutÑ.................................................................16
Summary of the Permutation Design Pattern...........................................19
2 Combinations and Cartesian Product.........................................................21
Combinations............................................................................................22
Summary of the Combination Design Pattern..........................................28
3 Depth First Search......................................................................................31
Depth First Search Classes.......................................................................34
DFS Class Collaboration..........................................................................38
Some Graph Theory.................................................................................39
Chains in DFS...........................................................................................40
Application Analysis................................................................................45
DFS Debugging Tips................................................................................59
How DFS Works......................................................................................60
Depth Bound.............................................................................................60
Summary of the Depth First Search pattern.............................................61
4 Variations on Depth First Search...............................................................63
Divide and Conquer (D&C).....................................................................63
Performance of D&C................................................................................70
Recursion vs. DFS....................................................................................70
Summary of the Divide and Conquer Pattern...........................................70
Branch and Bound (B&B)........................................................................71
iii
Design Patterns for Searching in C#
Heuristics..................................................................................................77
Summary of the Branch and Bound Pattern.............................................80
5 Dynamic Programming..............................................................................83
Using DFS in Dynamic Programming.....................................................84
Branch and Bound Revisited....................................................................94
Summary of the Dynamic Programming Pattern...................................105
6 Breadth First Search.................................................................................107
Best-First................................................................................................110
Greedy Search.........................................................................................112
Beam Search...........................................................................................119
A Storage Optimization..........................................................................126
Summary of the Breadth First Search Design Pattern............................126
7 A*.............................................................................................................129
Heuristics................................................................................................129
Summary of the A* Design Pattern........................................................143
8 Game Trees..............................................................................................145
Preliminary notions................................................................................145
Minimax.................................................................................................148
Alpha/Beta Pruning................................................................................160
Summary of the Game Tree Design Pattern...........................................163
Iterative Deepening and Move Ordering................................................164
9 Simulated Annealing................................................................................167
The SA Algorithm..................................................................................168
Summary of the Simulated Annealing Design Pattern...........................178
Envoi.......................................................................................................179
Bibliography................................................................................................181
iv
Contents
 
Design Patterns for Searching in C#
Index of Problems and Applications
Traveling Salesman Problem (TSP)..............................................................14
Machine Sequencing.....................................................................................15
8-Queens........................................................................................................15
Quadratic Assignment Problem....................................................................18
Obtaining all sublists of a list........................................................................22
Creating a round-robin tournament...............................................................23
Nested parentheses........................................................................................23
Combinations of Combinations.....................................................................25
8-Queens Revisited.......................................................................................31
Searching a Maze..........................................................................................40
A Parser.........................................................................................................48
Parenthesizing a list.......................................................................................64
Knapsack.......................................................................................................72
Knapsack Problem (Revisited)......................................................................83
Lot Sizing Problem........................................................................................96
TSP, Version 1, Greedy Search...................................................................113
TSP, Version 2, Beam Search.....................................................................120
TSP, Version 3, Beam Search.....................................................................122
Knapsack via A*.........................................................................................132
15-Puzzle.....................................................................................................135
Reversi.........................................................................................................150
TSP solved via SA.......................................................................................168
Contents
v
 

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin