Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
2000-01-18
2004-05-11
Teska, Kevin J. (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C703S013000, C703S021000, C716S030000
Reexamination Certificate
active
06735555
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a processing device for optimizing or locally optimizing the shape of a network such as a road network, a gas network, a watersupply network, a power supply network, a telephony network, a computer network, etc.
b
2
. Description of the Related Art
A Steiner problem being one of optimization problems is known as a problem of obtaining a connected tree which includes a plurality of points in a metric space as nodes and whose total distance is the shortest. A tree in a metric space is a network having no closed path. A network such as a road network, a gas network, a watersupply network, a power supply network, a telephony network, a computer network, etc. can be represented by using a tree. In the operations for installing, arranging, and wiring a target having any of these network shapes on a plane, a sphere, or in a three-dimensional space, it is vital to obtain a tree whose total distance is shorter.
For the Steiner problem, the total distance of a tree is used as a cost value, and a tree whose cost value is a minimum or a local minimum is searched. By changing the sign of a cost value, the problem of obtaining the minimum or the local minimum can be replaced with a problem of obtaining a maximum or a local maximum.
Conventionally, attempts were made mainly for a Steiner problem in a two-dimensional Euclidean space or rectilinear space, and no algorithm for solving a Steiner problem in a general metric space or a Riemann space is known. For a Steiner problem on a plane, many algorithms for obtaining the shortest distance network have been developed.
However, the conventional algorithms have the following practical problems.
(A) Cannot be applied to problems in spaces other than on a plane, such as a global network on a worldwide level, a network in a three-dimensional space, and the like.
(B) Cannot prohibit network installation in particular areas. For example, areas where a network cannot be installed or is difficult to be installed, such as a steep mountainous district, lake, sea, a nature conservation area, or a danger zone, etc. from a technical or institutional viewpoint.
(C) Since network installation costs which are respectively required for urban and rural districts per unit length are different, they cannot be estimated based only on the lengths of networks. Accordingly, a network installation cost cannot be accurately optimized.
As described above, the problems inherent in the conventional algorithms exist in a point that the algorithms can be applied only to the case where the length of a network is given as a Euclidean distance on a plane.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a processing device with higher universality, which comprises an algorithm for searching for a suitable network shape in a general metric space.
A processing device according to the present invention comprises a generating unit, a storing unit, a reshaping unit, and an outputting unit. The generating unit generates a tree model in an arbitrary space. The storing unit stores the data of existing nodes included in the tree model. The reshaping unit reshapes the tree model based on the existing nodes. The outputting unit outputs a reshape result.
REFERENCES:
patent: 5475842 (1995-12-01), Gilbert et al.
patent: 6047331 (2000-04-01), Medard et al.
patent: 6093153 (2000-07-01), Levin
patent: 6247167 (2001-06-01), Raspopovic et al.
patent: 6310883 (2001-10-01), Mann et al.
patent: 6374202 (2002-04-01), Robinson
patent: 6389376 (2002-05-01), Lam et al.
patent: 6401234 (2002-06-01), Alpert et al.
patent: 6442745 (2002-08-01), Arunachalam et al.
“Mathematical Programming in a Hybrid Genetic Algorithm for Steiner Point Problems” D. Thuente, 1995 ACM symposium on Applied computing, Feb. 1995.*
“Merlin: Semi-Order-Independent Hierarchical Buffered Routing Tree Generation using Local Neighborhood Search” A. Salek, ACM 1-58113-109-7/99/06, 1999.*
“On Minimum Stars, Minimum Steiner Stars, and Maximum Matchings”, S. Fekete, SCG99, ACM 1-58133-068-6/99/06, 1999.*
“A Multicast Routing Algorithm Reducing Congestion” A. Hac, Int. J. Network mgmt. vol. 7, pp. 147-163, 1997.*
“Closing the Gap: Near-Optimal Steiner Trees in Polynomial Time” J. Griffth, IEEE Transactions on Computer Aided Design of Integrated Circuits, Vol 13, No. 11, Nov. 1994.*
“A Consistant Hierarchical Representation for Vector Data”, R. Nelson, SIGGRAPH 86, ACM 0-89791-196-2/86/008/0197, 198.*
“Automatic Array Alignment in Data-Parallel Programs”, S. Chatterjee, ACM 0-80791-561-5/93/0001/0016, 1993.
Fukuda Ikuo
Kameda Shigeru
Masuda Shoichi
Suzuki Ichiro
Ferris Fred
Fujitsu Limited
Staas & Halsey , LLP
Teska Kevin J.
LandOfFree
Processing device for searching for a suitable network shape... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Processing device for searching for a suitable network shape..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processing device for searching for a suitable network shape... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3213672