平行结构类问题的分解与任务分布  

DECOMPOSITION AND ALLOCATION OF FLATSTRUCTURED PROBLEMS

作　　者：胡蓬[1] 苏伯珙[1] 石纯一[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《计算机学报》1992年第2期128-136,共9页Chinese Journal of Computers

摘　　要：本文给出平行结构类问题及其求解系统的形式化描述,讨论了此类问题的分解与任务分布,并提出了一种IPD算法(Improved Problem Decomposition).该算法从规模上将问题分解为若干性质相同的任务,按就近原则将任务预分布到系统中各结点上,并通过启发式状态空间查找方法进行负载调整,使系统负载平衡.试验表明:IPD算法的分解分布结果负载平衡,系统潜在协作量小.This paper classifies the applications of DPS into hierarchical and flatstructures, gives a formal description of the flat-structured problem and its solving system, discusses the decomposition and task allocation of this class of problems, and presents an Improved Problem Decomposition (IPD) algorithm, by which a problem is decomposed in scale, into several tasks of identical property, each task is allocated to a proximate problem solving agent, and heuristic state space search is used to balance the load. The experiments on a Distributed Transport Dispatching System indicate that IPD algorithm has a good decomposition and allocation result with balanced load and less potential system cooperation, and plays a positive role in enhancing efficiency and guaranteeing quality of problem solving.

关 键 词：平行结构类 人工智能 问题求解 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]