CAJ | 학술논문

面对资源的日益紧缺,如何有效合理的利用资源一直是专家学者研究和探讨的热点问题.最少资源问题是对初步资源规划问题的探讨,可以为多个资源组合规划问题的基础研究提供有效的参考作用.传统的回溯法穷举虽然能找到最少资源问题的最优解但其时间复杂度会高于o(n!),往往耗时太多,不能满足问题的及时性.提出了一种以最早开始时间为贪心策略的求解最少资源问题的贪心算法,不仅能够找到最优解,而且其时间复杂度仅为o(n2),极大提高了算法的效率.
면대자원적일익긴결,여하유효합리적이용자원일직시전가학자연구화탐토적열점문제.최소자원문제시대초보자원규화문제적탐토,가이위다개자원조합규화문제적기출연구제공유효적삼고작용.전통적회소법궁거수연능조도최소자원문제적최우해단기시간복잡도회고우o(n!),왕왕모시태다,불능만족문제적급시성.제출료일충이최조개시시간위탐심책략적구해최소자원문제적탐심산법,불부능구조도최우해,이차기시간복잡도부위o(n2),겁대제고료산법적효솔.
Faced with the resources in short supply day by day, how to utilize available resources effectively and reasonablely has been a hot topic that experts and scholars research on and inquire into. The least resources problem is a discussion of primary resource planning, and it can provide effective reference for the basic study of a programming problem with multiple resource sets. Traditional Backward Search Algorithm can find the optimal solutions of the least resources problem by searching for all possible solutions, however, its time complexity is higher than o(n!). Therefore,it can't meet the timeliness of solving the problem. The dissertation puts forward a novel greedy algorithm that takes the earliest beginning time as greedy strategy to solve the least resources problem. It can not just find out the optimal solutions, but have lower time complexity, only o(n2). So, the efficiency of the algorithm is improved greatly.