Algorithms, graphs, and computers

✍ Scribed by Bellman R., Cooke K.L., Lockett J.A.

• Publisher: Academic Press
• Year: 1970
• Tongue: English
• Leaves: 265
• Category: Library

✦ Table of Contents

Algorithms Graphs and Computers
Copyright Page
Contents
Preface
Chapter One. COMMUTING AND COMPUTING
1. Introduction
2. A Commuting Problem
3. Enumeration of Paths
4. Tree Diagrams
5. Timing and the Shortest Route
6. An Improved Map
7. The Array of Times
8. Arbitrary Starting Point
9. Minimum Time Functions
10. The Minimum Function
11. Equations for the fi
12. Reduced Tree
13. General Map
14. Solving the Equations
15. Why Not Enumeration Using Computers?
16. Graphs
17. The Problem of the Königsberg Bridges
18. Systems and States
19. Critical Path Analysis
20. Summing Up
Bibliography and Comments
Chapter Two. THE METHOD OF SUCCESSIVE APPROXIMATIONS
1. Introduction
2. A Simple Example of Successive Approximations
3. A Simple Example of the Failure of the Method
4. Algorithms
5. Computer Programming
6. Algorithms for Solving x = f(x)
7. The Newton–Raphson Method: Square Roots
8. An Example
9. Enter the Digital Computer
10. Stop Rules
11. Flow Charts for the Determination of S a
12. What Initial Approximation?
13. An Approximation Method of Steinhaus
14. Successive Approximations for a Simple Routing Problem
15. The Map of Fig. 3 of Chapter One
16. Determination of Optimal Policy
17. A Different Initial Policy
18. Successive Approximations for a General Map
19. Computer Program
20. The Connection Matrix and A Second Programming Method
21. Fictitious Links
22. Paths With a Given Number of Junctions
23. A Labelling Algorithm
24. Working Back From the End
Miscellaneous Exercises
Bibliography and Comment
Chapter Three. FROM CHICAGO TO THE GRAND CANYON BY CAR AND COMPUTER: Difficulties Associated With Large Maps
1. Introduction
2. How to Plan a Vacation
3. A Particular Initial Approximation
4. The Peculiarities of Structure
5. Computer Program
6. Storage Considerations
7. Use of Tapes
8. Storage of Sparse Data
9. Calculation of the tij
10. Transformation of Systems
11. Stratification
12. Acceleration of Convergence
13. Design of Electric Power Stations
Miscellaneous Exercises
Bibliography and Comments
Chapter Four. PROOF OF THE VALIDITY OF THE METHOD
1. Will the Method Always Work?
2. Is There at Least One Solution?
3. How Do We Find the Desired Solution?
4. Monotonicity
5. The Upper Solution
6. The Lower Solution
7. Experimental Proof of Uniqueness
8. Uniqueness of Solution
9. Determination of Optimal Policy
10. Arbitrary Initial Approximation
11. Least Time to Move k Steps
12. Number of Iterations
Miscellaneous Exercises
Bibliography and Comment
Chapter Five. JUGGLING JUGS
1. A Classical Puzzle
2. Precise Formulation
3. Trial and Error
4. Tree Diagrams
5. Some Further Observations
6. Enumeration by Computer
7. A Geometrical Representation
8. Cost Matrix
9. Connection Matrix
10. Minimum Cost Functions
11. Powers of the Adjacency Matrix
12. Functional Equations
13. Successive Approximations
14. The Labelling Algorithm
15. Avoiding the Cost Matrix
16. Another Initial Policy
17. Getting Close
18. Making the Closest Approach
19. Calculation of fN(y, z )
20. Accessible and Inaccessible States
Miscellaneous Exercises
Bibliography and Comment
Chapter Six. THE SAWYER GRAPH AND THE BILLIARD BALL COMPUTER
1. The Sawyer Graph
2. Analysis of the Sawyer Graph
3. Connectedness of the Sawyer Graph
4. The Spine of the Sawyer Graph
5. The Case When c is a Divisor of b
6. The General Case
7. The Case when b and c Have No Common Factor
8. The Billiard Ball Solution
9. The Billiard Ball Diagram and Sawyer Graph
10. Graphical Determination of Shortest Paths
11. Discussion
12. Computer Assistance in Drawing State Graphs
Miscellaneous Exercises
Bibliography and Comment
Chapter Seven. CANNIBALS AND MISSIONARIES
1. Another Classical Puzzle
2. Trees and Enumeration
3. The State Diagram
4. Existence and Uniqueness
5. Analytic Methods
6. Example
Miscellaneous Exercises
Bibliography and Comment
Chapter Eight. THE 'TRAVELLING SALESMAN' AND OTHER SCHEDULING PROBLEMS
1. Introduction
2. A Mathematician's Holiday
3. A Map and a Matrix
4. Enumeration
5. A Simplified Version
6. Recurrence Relations
7. Do All the Errands!
8. Feasibility
9. How Many Errands Could We Do?
10. Trading Time for Storage
11. How to Build a Tennis Court
12. Sequential Selection
13. Feasibility
14. Simplified and More Realistic Assignment Problem
15. Constraints
16. Discussion
17. 2N
18. A Branching Process
19. Recurrence Relations
20. Discussion
Miscellaneous Exercises
Bibliography and Comment
Author lndex
Subject Index
Mathematics in Science and Engineering