信息需求网络上最优连接问题

一个关于知识获取、信息需求或资源占有的系统往往可以用一个有向网络来描述，其中起点集表示已获得的资源(知识、信息等)，终点集表示要求获得的资源，而获取资源的过程就是从起点集到终点集的一个连接方式．论文建立此类问题的网络优化模型，并研究其基本性质及算法问题．主要结果包括：一般情形的NP-完全性，特殊情形的多项式时间算法，如没有中间点的网络或有固定数目中间点的网络，以及实用的启发式算法．

Optimal connection problem on information requirement networks

A system related to the knowledge acquirement, information requirement or resources occupation can be described by a directed network, in which several source_nodes stand for the already gained resources (knowledge, information, etc), several end_nodes stand for the resources to be required, and the process of obtaining resources is a way of connection from the source_nodes to the end_nodes. In this paper we establish a network optimization model for this practical problem, and study its basic properties and algorithmic aspects. The main results include the NP_completeness in general case, polynomial-time algorithms for special case, e.g., for the networks without or with fixed number of intermediate nodes, and heuristic algorithms for practical use.