| 摘要 |
PROBLEM TO BE SOLVED: To provide a system for calculating the initial division of a graph constituted of nodes and edges connecting them which does not optimally use analysis by satisfactory probabilistic search. SOLUTION: The optimal arrangement of nodes and edges is provided by division having the minimum cut size, and the initial division is provided for the following use by the Kernigan and Lin system of graph division. The combination of a seed development heuristic method and a probabilistic search process is used for calculating the initial division, and the seed development heuristic method constructs the division by repeatedly increasing the initial set of seed nodes, and the search process searches the set of the seed nodes satisfactory for being used. The combination of the seed development heuristic method, probabilistic search process, and the Kernigan and Lin algorithm 36 generated as the result constitutes an excellent system for dividing the graph.
|
