Parallel Computational Geometry on Analog Hopfield Networks.

摘要

This thesis presents a novel approach to solving Computational Geometry problems in parallel, by using Analog Hopfield Neural Networks, which are simplified models of the human brain. The use of massively parallel analog networks requires a radically different approach to geometric problem solving because (i) time is continuous instead of the usual discretized time step used for sequential or parallel processing, and (ii) geometric data is represented by analog components instead of the usual digital representation. We present analog network algorithms for the following geometrical problems: (1) Minimum weight triangulation of planar point sets or of polygons with holes. (2) Finding the smallest ;We also present an improvement to Hopfield's solution for the Euclidean Travelling Salesman Problem.;For each network, we present a detailed analysis of the network's parameters, together with proofs that the networks indeed produce feasible solutions. Experimental results presented in each chapter demonstrate the performance of our networks.