Article ID: | iaor1999903 |
Country: | United States |
Volume: | 144 |
Issue: | 3 |
Start Page Number: | 163 |
End Page Number: | 168 |
Publication Date: | Jul 1997 |
Journal: | IEE Proceedings Computers and Digital Techniques |
Authors: | Lam K.P., Tong C.W. |
Dynamic programming is well known as a powerful modelling technique for dealing with the issue of making optimal decisions sequentially. Many practical problems, such as finding shortest paths in route planning, and multi-stage optimal control, can be formulated as special cases of the general sequential decision process. The paper proposes a connectionist network architecture, called the binary-relation inference network, which solves a special class of dynamic programming problems in the continuous time. They include the all-pair solutions for a family of closed semi-ring path problems, such as shortest paths, transitive closure, minimum spanning tree, and minimax path problems. The all-pair inference network specifies a basic and uniform computation of its individual units, which then collectively emerge towards a global optimal solution. The computational order in its discrete-time variants, either as synchronous or asynchronous networks, bears a close resemblance to the Floyd–Warshall algorithm and doubling algorithm. However, the continuous-time inference network offers a significant speed advantage if its non-sequential computation nature can be exploited. Simulation results of using analogue very large scale integration implementation of the inference network for solving shortest-path problems are promising.