摘要
The goal of efficient computation is to determine reasonable computing cost in polynomial time by using data structure of instance, and analyze the computing cost of satisfactory solution which can meet user’s requirements. When faced with NP-hard problem, we usually assess computational performance in the worst case. Polynomial algorithm cannot handle with NP-hard problem, so we research on NP-hard problem from efficient computation point of view. The work is intended to fill the blank of computational complexity theory.We focus on the cluster structure of instance data of aircraft range problem. By studying the partition and complexity measurement of cluster, we establish a connection between the aircraft range problem and N-vehicle exploration problem, and construct the efficient computation mechanism for aircraft range problem. The last examples show that the effect is significant when we use efficient computation mechanism on aircraft range problem. Decision makers can calculate the computing cost before actually computing.
The goal of efficient computation is to determine reasonable computing cost in polynomial time by using data structure of instance, and analyze the computing cost of satisfactory solution which can meet user’s requirements. When faced with NP-hard problem, we usually assess computational performance in the worst case. Polynomial algorithm cannot handle with NP-hard problem, so we research on NP-hard problem from efficient computation point of view. The work is intended to fill the blank of computational complexity theory.We focus on the cluster structure of instance data of aircraft range problem. By studying the partition and complexity measurement of cluster, we establish a connection between the aircraft range problem and N-vehicle exploration problem, and construct the efficient computation mechanism for aircraft range problem. The last examples show that the effect is significant when we use efficient computation mechanism on aircraft range problem. Decision makers can calculate the computing cost before actually computing.
基金
Supported by Key Laboratory of Management,Decision and Information Systems,Chinese Academy of Science