Computer system configured in support of solving NP-complete problems at high speed
AssigneeInternational Intellectual Group, Inc.
InventorsIvan Ivanovich Goray, Leonid Ivanovich Goray
Life of this patent
Estimating the term…
Abstract
The present invention is a computer system and associated method configured to in support of solving NP-complete problems such as minimal Hamiltonian cycle type problems. According to the invention, a primary network represented by the matrix of its edges is recorded in the memory space, and an equivalent representation of the primary network is formed as a set of subnetworks. Nodes of a present path are reordered according to a set of reordering rules and edge weights of edges of the set of subnetworks are changed according to a set of edge weight changing rules.
Claims48
A computer-implemented method in support of solving an NP-complete-type problem, said method comprising the steps of:
- recording in a memory of said computer a primary network having N nodes represented by a matrix of edge weights;
- forming an equivalent representation of said primary network as a set of N subnetworks, wherein each of said N subnetworks has a like number of nodes and all edges incident to one node of each of said N subnetworks have zero weight;
- improving a present path by application of reordering rule means for reordering nodes of said subnetworks successively utilizing data from each of said N subnetworks until for a complete cycle of application of data from each of said N subnetworks to said reordering rule means, no subnetwork is reordered;
- transforming by application of edge weight changing rule means for changing weights of edges of said subnetworks successively utilizing data from each of said N subnetworks until for a complete cycle of application of data from each of said N subnetworks to said edge weight changing rule means, no edge weight is changed;
- and
- repeating said improving and transforming steps until said path cannot be reordered by application of said reordering rule means, and said edge weights cannot be changed by application of said edge weight changing rule means.
A computer system in support of solving an NP-complete-type problem, said computer system comprising:
- recording means recording in a memory of said computer system a primary network having N nodes represented by a matrix of edge weights;
- forming means forming an equivalent representation of said primary network as a set of N subnetworks, wherein each of said N subnetworks has a like number of nodes and all edges incident to one node of each of said N subnetworks have zero weight;
- improving means improving a present path by application of reordering rule means for reordering nodes of said subnetworks successively utilizing data from each of said N subnetworks until for a complete cycle of application of data from each of said N subnetworks to said reordering rule means, no subnetwork is reordered;
- transforming means transforming by application of edge weight changing rule means for changing weights of edges of said subnetworks successively utilizing data from each of said N subnetworks until for a complete cycle of application of data from each of said N subnetworks to said edge weight changing rule means, no edge weight is changed;
- and
- repeating means repeating application of said reordering rule means and said edge weight changing rule means until said path cannot be reordered by application of said reordering rule means, and said edge weights cannot be changed by application of said edge weight changing rule means.
A memory device including a program for execution by a computer system, wherein said program configures said computer system to:
- record in a memory of said computer system a primary network having N nodes represented by a matrix of edge weights;
- form an equivalent representation of said primary network as a set of N subnetworks, wherein each of said N subnetworks has a like number of nodes and all edges incident to one node of each of said N subnetworks have zero weight;
- improve a present path by application of reordering rule means for reordering nodes of said subnetworks successively utilizing data from each of said N subnetworks until for a complete cycle of application of data from each of said N subnetworks to said reordering rule means, no subnetwork is reordered;
- transform by application of edge weight changing rule means for changing weights of edges of said subnetworks successively utilizing data from each of said N subnetworks until for a complete cycle of application of data from each of said N subnetworks to said edge weight changing rule means, no edge weight is changed;
- and
- repeat application of said reordering rule means and said edge weight changing rule means until said path cannot be reordered by application of said reordering rule means, and said edge weights cannot be changed by application of said edge weight changing rule means.
Dependencies are inferred from the claim text.