论文部分内容阅读
数据时代，大数据已从现象成为常态，数据科学也逐渐成为高校研究和企业应用的重要课题。然而，在真实场景中，如何从海量数据中发掘有效信息、高效地指导决策过程，还有很多亟待解决的技术难点。大数据背景下的决策问题通常是NP难的，并且很多问题是非线性的。如商品动态定价问题(Dynamic Pricing Problem)、库存管理问题（Inventory Management Problem）、车辆路径问题(Vehicle Routing Problem)等。在处理这些问题时，决策者要做到传统意义上的精确决策，已经变得异常艰难。因此，决策者必须要改变传统行为习惯，重新思考怎样快速高效地做出合理的决策。要回答这样的问题，我们必须要清楚这些NP难问题“具体实例”的难度。 通常在求解一个NP难问题实例时，人们会采用近似算法或者启发式算法，以求能在更高效的时间内获取一个可以接受的结果。然而，如果所面临的实例是一个易解的，或则说在已有的计算资源条件下是可以得到精确解呢？事实上，这种情况也是存在的，例如具有上三角矩阵、下三角矩阵的TSP问题实例[1,2]。因此，我们不能主观地认定NP难问题的所有实例都是难的，不能在多项式时间获取精确解的。在计算能力已经大幅提升的今天，我们需要将实例的难度进行更为精细化的刻画，以便获取更为满意的解。 本文以带有非线性目标函数的N车探险问题为切入点，利用有效计算性的理念[11]，探寻度量难问题实例合理计算成本的方法。本文不局限于单纯的提高某个算法的效率或者证明某个问题的NP难性。而是基于对N车探险问题具体实例数据结构的研究，探索实例的难度分布和影响实例难度变化的因素。从而设计出度量具体实例合理计算成本的方式，同时给出获取该合理计算成本的多项式时间算法。并设计出以合理计算成本为计算代价的精确算法，藉此建立起有效计算性框架下切实可行的求解方案。本文的主要研究内容如下: 首先，探寻影响N车探险问题实例难度的数据结构因素，设计N车探险问题精确算法。寻找影响N车探险问题实例难度（或者计算成本）的因素是建立有效计算性的关键一步。对实例计算成本的度量，将实际指导我们对该实例的求解。此部分研究主要集中在分析问题实例性质，给出影响实例计算成本的因素。在此基础上，设计相关联的精确算法。该算法充分利用影响实例难度的数据结构因素，从而可以有效区分开同规模下不同难度的实例。 其次，设计N车探险问题实例合理计算成本的有效度量方式，建立针对该问题的有效计算性解决方案。此部分研究在分析实例难度影响因素的基础上，进一步找出度量实例合理计算成本的指标，并设计多项式时间算法找出该指标。这个指标是我们对N车探险问题实例难度最直观的认识，它帮助我们快速清晰地了解求解当前实例所需的计算代价。在获取实例合理计算成本的基础上，综合考虑计算资源和计算需求，最终给出有效计算性解决方案。 最后，开展了基于有效计算性框架的背包问题的研究，同时给出多任务N车探险问题的启发式算法。此部分研究将有效计算性的模式应用到背包问题上，设计度量背包问题实例合理计算成本的指标，给出其有效计算性求解方案。同时，针对多任务N探险问题精确解时间复杂度特别高的情况(O(n3n)[3]），设计求解该问题的启发式算法。 本文的主要创新点如下: (1)给出序贯可行解的定义，通过序贯可行解的规模重新认识和解释了N车探险问题实例的难度。序贯可行解规模刻画了N车探险问题实例由易到难的整个过程，使得人们对N车探险问题实例的难度有了新的全面的认识，而不再局限于某些特殊结构的实例。 (2)针对序贯可行解的性质，总结了多个剪枝规则，并设计了相关联的精确算法。根据序贯可行解性质得来的精确算法大大改进了以往精确算法的效率，而且对不同难度的实例呈现出计算量也随之变化的情况。实例“易”则计算量小，实例“难”则计算量大。 (3)给出以临界值Nlk为基础的多项式时间算法来获取序贯可行解规模，并以此度量实例计算难度。Nlk的提出有效解决了计算之前快速获取N车探险问题实例难度的问题。 (4)首次完整的建立了N车探险问题的有效计算性解决方案，并将其推广到背包问题上。针对多任务N车探险问题算法的不足，提出了更高效的启发式算法。