IMAGE PROCESSING, PATTERN RECOGNITION

Heuristic algorithm for finding approximate solution of Steiner problem based on physical analogies

A. V. Lisin, R. T. Faizullin

Omsk State Technical University

Abstract: The article contains analyze of existent methods for solving Steiner problem that use physical analogies. Algorithm for construction of minimal Steiner trees based on existent solutions and Delaunay triangulation for initial approximation is suggested. Done comparison of suggested algorithm output and one with exponential complexity, which produces exact results.

Keywords: steiner problem, heuristic algorithm, Delaunay triangulation.

Received: 14.09.2013