确定最优解的方法、补货方法、装置、设备及介质

摘要

本发明提供确定最优解的方法、补货方法、装置、设备及介质，方法包括：根据贪心算法和事件目标对第k个事件状态向后模拟n步得到向后模拟第n步时的若干个局部解，补全向后模拟第n步时得到的局部解得到对应的完整解；根据事件目标确定所有完整解中的最优完整解；根据最优完整解回溯至向后模拟第1步时得到的对应的局部解，在第k个事件状态下执行所回溯的局部解；其中，k满足0≤k≤p，n满足n≥1，k和n还满足n+k＜p。方法基于贪心算法进行改进，弥补了贪心算法只注重当前最优的短视缺陷，实现整体利益最大化，避免局部利益与整体利益相冲突的情况，使在每个事件状态执行的局部解都充分考虑了对后一事件状态的影响，具备了考虑整体最优的特性。

说明书

技术领域

本发明涉及领域，更具体地，涉及确定最优解的方法、补货方法、装置、设备及介质。

背景技术

补货问题是组合优化领域的其中一个经典问题，所谓组合优化是指在离散的、有限的数学结构上寻找一个满足给定条件，并使其目标函数值达到最大或最小的解。经典问题还包括装箱问题、装包问题等等。其中，补货问题是指在满足给定约束的情况下制定补货策略，以达到某种补货目的(如补货成本最低，周期最短等)，补货策略有很多种，例如指在某时为某仓库补某个数量的货品。装箱问题与装包问题类似，是指要求把一定数量的物品放入容量相同的一些箱子中,使得每个箱子中的物品大小之和不超过箱子容量并使所用的箱子数目最少。

对于组合优化的经典问题有过很多求解方法，以补货问题为例，现有的求解方法中，首先有利用遗传算法进行补货策略的计算，但该由于遗传算法在交叉、变异过程中的随机性，导致其在处理复杂约束问题时，进行交叉和变异后会产生大量不符合约束的解，需要花费大量的时间对这些不合符约束进行修复，最终导致算法的收敛速度慢，因此利用该方法求解很难在短时间内得到高质量的解。

其次，现有的求解方法还利用多目标粒子群优化算法进行求解，该算法在求解的过程中存在的问题是容易产生早熟收敛(尤其是在处理复杂的多峰搜索问题中)、局部寻优能力较差等，算法陷入局部最优，主要归咎于种群在搜索空间中多样性的丢失。

常见的求解方法还有利用经济批量模型以及整数规划的方法，但两个方法同样存在缺点，分别为经济批量模型难以增加其他约束，该模型只是根据出货节奏、库存费用等信息计算最优的订购批量，但企业在生产运营过程中还面临许多其他约束，该模型难以对其进行考量；经济批量模型难以处理需求波动的情况，该模型基于需求已知的情况，出货稳定的情况进行求解，假设过于理想化，不适用于当今复杂的商业情况；整数规划方法过于精准，导致求解规模非常小，求解时间比较长，很难应用到实际生产运营过程中。

最后，贪心算法也是用于解决组合优化的常用方法，贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。但贪心算法的缺点也十分明显，即无法顾及补货的全过程，只顾及当前状态的局部最优解，导致贪心算法基于每个状态的局部最优解得出的全局最优解并非方案下的最优解。

发明内容

本发明旨在克服上述现有技术的至少一种缺陷，提供确定最优解的方法、补货方法、装置、设备及介质，用于解决利用现有的算法对组合优化等经典问题进行求解时出现的求解时长过长、难以求出高质量最优解等缺陷和不足。

本发明采用的技术方案包括：

一种确定最优解的方法，包括：根据贪心算法和事件目标对第k个事件状态向后模拟n步得到向后模拟第n步时的若干个局部解，补全所述向后模拟第n步时得到的局部解得到对应的完整解；根据所述事件目标确定所有所述完整解中的最优完整解；根据所述最优完整解回溯至向后模拟第1步时得到的对应的局部解作为最优局部解，在所述第k个事件状态下执行所述最优局部解；其中，所述k满足0≤k≤p，所述p为所述事件状态的总数，所述n的值为向后模拟的模拟步数的总数，所述n满足n≥1，所述k和所述n还满足n+k＜p。

本发明提供的确定最优解的方法是基于贪心算法的改进，一般利用贪心算法求解第k个状态的局部解时缺乏对整体最优解的考虑，因此本发明提供的方法利用贪心算法和事件目标对第k个状态向后模拟n步得到模拟第n步后的若干个局部解，对若干个局部解进行基于贪心算法进行方案的补全后得到若干个对应的完整解，再根据需要满足的事件目标从若干个完整解中挑选出最符合事件目标的最优完整解，回溯最优完整解对应的向后模拟1步的局部解，在第k个事件状态下执行回溯所确定的局部解。由于贪心算法是基于当前状态作出一个最优局部解，缺乏对整体最优解的考虑，而在本发明提供的方法下执行的局部解对应的是在第k个事件状态下向后模拟n步后选出的最优完整解，因此，该局部解虽然由贪心算法确定，但具备整体最优解的特性。由此可见，本发明提供的方法基于贪心算法进行改进，弥补了贪心算法只注重当前最优的短视缺陷，实现整体利益最大化，避免局部利益与整体利益相冲突的情况，使在每个事件状态执行的局部解都充分考虑了对后一事件状态的影响，具备了考虑整体最优的特性。同时，由于在对第k个事件状态向后模拟n步后是通过补全得到每个局部解的完整解，即不是对事件状态向后模拟至完整解，则本发明提供的方法能够实现在合理时间内确定最终执行的最优局部解，该最优局部解是在合理时间限制下的近似最优解。

进一步，在根据贪心算法和事件目标对第k个事件状态向后模拟n步得到向后模拟第n步时的若干个局部解之前，判断所述k的值是否小于p，如是，则继续执行根据贪心算法和事件目标对第k个事件状态向后模拟n步得到向后模拟第n步时的若干个局部解的操作。本发明提供的方法针对的是非最终事件状态的事件，对每个非最终事件状态的事件状态向后模拟n步，使在该事件状态下执行的局部解具备考虑整体最优的特性。

进一步，在所述第k个事件状态下执行所述最优局部解之后，将所述k的值加一，重复执行判断所述k的值是否小于p的操作直至所述k的值大于或等于p为止。本发明提供的方法应用于非最终状态的每个事件状态，因此在第k个事件状态下执行所回溯的局部解后，将k的值加一，重复执行对第k个事件状态向后模拟n步最后获得最优完整解回溯的局部解，直至k的值等于p为止，保证每个事件状态下执行的操作均考虑到对整体最优的影响，弥补贪心算法的短视缺陷。

进一步，在根据贪心算法和事件目标对第k个事件状态向后模拟n步得到向后模拟第n步时的若干个局部解之前，初始化第k个事件状态当前的模拟步数i的值为0；根据贪心算法和事件目标对第k个事件状态向后模拟n步得到向后模拟第n步时的若干个局部解具体为：当所述i的值为0时，根据所述贪心算法和所述事件目标对所述第k个事件状态向后模拟1步，得到向后模拟第1步时的若干个局部解，将所述i的值加一；当所述i的值不为0且小于n时，根据所述贪心算法和所述事件目标，分别对向后模拟第i步时所得到的每个局部解向后模拟1步，得到向后模拟第i+1步时的若干个局部解，并将所述i的值加一。

利用模拟步数i控制执行每一个事件状态下向后模拟的每一步，每向后模拟1步得到若干个局部解后，通过将模拟步数i的值加一重复执行对第k个事件状态向后模拟的1步，直至i的值等于n为止，根据实际需要或其他限制条件在设定n的值后，保证每个事件状态下向后模拟至少一步，弥补贪心算法确定的局部解没有顾全整体事件的缺陷。

进一步，当所述i的值为0时，根据所述贪心算法和所述事件目标对所述第k个事件状态向后模拟1步，得到向后模拟第1步时的若干个局部解，将所述i的值加一，具体为：当所述i的值为0时，根据所述贪心算法确定在第k个事件状态下满足所述事件目标的前若干个局部解作为向后模拟第1步时的若干个局部解，向后模拟第1步时的每个局部解构成一个暂时事件状态k+1，将所述i的值加一；当所述i的值不为0且小于n时，根据所述贪心算法和所述事件目标，分别对向后模拟第i步时所得到的若干个局部解向后模拟1步，得到向后模拟第i+1步时的局部解，将所述i的值加一，具体为：当所述i的值不为0且小于n时，根据所述贪心算法分别确定若干个暂时事件状态k+i下满足所述事件目标的前若干个局部解，将所有在暂时事件状态k+i下满足所述事件目标的前若干个局部解作为向后模拟第i+1步时的局部解，向后模拟第i+1步时的每个局部解构成一个暂时时间状态k+i+1，将所述i的值加一。

对第k个事件状态向后模拟1步实际上是利用贪心算法在第k个事件状态下确定若干个局部解，而若干个局部解优选为满足事件目标的前若干个局部解，如分别在第k个事件状态下执行前若干个局部解，会得到对应的若干个暂时事件状态k+1，如此类推，在向后模拟第i步时，由于i的初始值为0，且每次向后模拟后加一，因此得到的是各个暂时事件状态k+i下确定的若干个局部解，直至i的值等于n为止。在每一个事件状态下确定最满足事件目标的前若干个局部解，使每个局部解具备当前较优的特性，同时结合向后模拟和回溯，使每个局部解在具备当前较优的同时具备考虑到整体最优的特性。

进一步，根据所述事件目标确定所有所述完整解中的最优完整解，具体为：确定各个所述完整解的目标函数值，根据所述事件目标确定其中一个所述目标函数值作为最优目标函数值，将所述最优目标函数值对应的完整解作为最优完整解。

一种确定最优局部解的装置，包括：模拟模块，用于根据贪心算法和事件目标对第k个事件状态向后模拟n步得到向后模拟第n步时的若干个局部解；补全模块，用于补全所述向后模拟模块在向后模拟第n步时得到的局部解得到对应的完整解；最优完整解确定模块，用于根据所述事件目标确定所述补全模块得到的所有所述完整解中的最优完整解；回溯执行模块，用于根据所述最优完整解确定模块所确定的最优完整解回溯至所述模拟模块向后模拟第1步时得到的对应的局部解作为最优局部解，在所述第k个事件状态下执行所述最优局部解；其中，所述k满足0≤k≤p，所述p为所述事件状态的总数，所述n的值为向后模拟的模拟步数的总数，所述n满足n≥1，所述k和所述n还满足n+k＜p。

一种补货方法，包括：根据贪心算法和补货目标对第k个补货状态向后模拟n步得到向后模拟第n步时的若干个补货操作，补全所述向后模拟第n步时得到的补货操作得到对应的完整补货操作；根据所述补货目标分别确定所有所述完整补货操作中的最优完整补货操作；根据所述最优完整补货操作回溯至向后模拟第1步时得到的对应的补货操作作为最优补货操作，在所述第k个补货状态下执行所述最优补货操作；其中，所述k满足0≤k≤p，所述p为所述补货状态的总数，所述n的值为向后模拟的模拟步数的总数，所述n满足n≥1，所述k和所述n还满足n+k＜p。

补货方法基于上述确定最优解的方法的相同思想，是基于贪心算法进行改进的方法，弥补了贪心算法只注重当前最优的短视缺陷，使在每个补货状态下执行的补货操作都充分考虑了对后一补货状态的影响，具备考虑整体最优的特性。

一种补货装置，包括：补货模拟模块，用于根据贪心算法和补货目标对第k个补货状态向后模拟n步得到向后模拟第n步时的若干个补货操作；补货操作补全模块，用于补全所述向后模拟补货模块在向后模拟第n步时得到的补货操作得到对应的完整补货操作；最优补货操作确定模块，用于根据所述事件目标确定所述补货操作补全模块得到的所有所述完整补货操作中的最优完整补货操作；补货回溯执行模块，用于根据所述最优补货操作确定模块所确定的最优完整补货操作回溯至所述补货模拟模块向后模拟第1步时得到的对应的补货操作作为最优补货操作，在所述第k个事件状态下执行所述最优补货操作；其中，所述k满足0≤k≤p，所述p为所述事件状态的总数，所述n的值为向后模拟的模拟步数的总数，所述n满足n≥1，所述k和所述n还满足n+k＜p。

一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现上述确定最优解的方法，或上述补货方法。

一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现上述确定最优解的方法，或上述补货方法。

与现有技术相比，本发明的有益效果为：本发明提供的方法基于贪心算法进行改进，弥补了贪心算法只注重当前最优的短视缺陷，实现整体利益最大化，避免局部利益与整体利益相冲突的情况，使在每个事件状态执行的局部解都充分考虑了对后一事件状态的影响，具备了考虑整体最优的特性。同时，由于在对第k个事件状态向后模拟n步后是通过补全得到每个局部解的完整解，即不是对事件状态向后模拟至完整解，则本发明提供的方法能够实现在合理时间内确定最终执行的最优局部解，该最优局部解是在合理时间限制下的近似最优解。

附图说明

图1为实施例的步骤S1～S4的流程示意图。

图2为实施例的步骤S01～S5的流程示意图。

图3为实施例的步骤S11～S2的流程示意图。

图4为实施例中n＝2时执行方法的流程示意图。

图5为实施例的步骤T1～T4的流程示意图。

图6为实施例的步骤T01～S5的流程示意图。

图7为实施例的步骤T11～T2的流程示意图。

图8为实施例的确定最优解的装置的模块组成示意图。

图9为实施例的补货装置的模块组成示意图。

标号说明：

确定最优解的装置包括：模拟模块100；补全模块200；最优完整解确定模块300；回溯执行模块400；数据处理模块500；

补货装置包括：补货模拟模块10；补货操作补全模块20；最优补货操作确定模块30；补货回溯执行模块40；数据处理模块50。

具体实施方式

本发明附图仅用于示例性说明，不能理解为对本发明的限制。为了更好说明以下实施例，附图某些部件会有省略、放大或缩小，并不代表实际产品的尺寸；对于本领域技术人员来说，附图中某些公知结构及其说明可能省略是可以理解的。

如图1所示，本实施例提供一种确定最优解的方法，与一般利用贪心算法求解局部解的方法不同，本实施例提供的确定最优解的方法是基于贪心算法的改进方法，如背景技术所述，贪心算法最大的缺点是缺乏对整体最优解的考虑，即着眼于局部利益而忽略了整体利益，本实施例提供的方法主要针对这一点进行改进，包括以下步骤：

S1：根据贪心算法和事件目标对第k个事件状态向后模拟n步得到向后模拟第n步时的若干个局部解；

具体地，事件包含至少一个求解问题，事件状态指该事件的当前状态。k的值满足0≤k≤p，p的值为事件状态的总数，第0个事件状态为事件的初始状态，第p个事件状态为事件的最终状态，也可以理解为事件的结束状态。局部解是指在某一个事件状态下执行的操作，在一个事件状态下执行了任何操作都会导致该事件状态变为另一个事件状态，一般会认为是变为下一个事件状态。事件目标是指事件需要满足的给定条件；贪心算法的思想是找出当前事件状态下最满足给定条件的局部解，由此可见，通过贪心算法确定最优局部解时所考虑的首要条件就是满足事件目标。具体地，n的值为向后模拟的模拟步数的总数，n的值满足n≥1，且k和n还满足n+k＜p，n的值在k的值和p的值不同的情况下也会有所不同。n的初始值是预先设定的，但当n的预设值不满足n+k＜p，n的值则需要更换为满足n+k＜p这一关系式的值，例如，当k＝p-2时，则n的最大值为2，如果n的预设值为4，则需要更换为2或1。

具体地，如图2所示，本实施例提供的方法适用于确定非最终状态的事件状态的最优局部解，因此在执行步骤S1前先执行步骤S01：判断k的值是否小于p，即判断事件状态是否为非最终状态，如否，则执行步骤S02：不作任何操作；如是，则执行步骤S1：根据贪心算法和事件目标对第k个事件状态向后模拟n步得到向后模拟第n步时的若干个局部解。在第k个事件状态下，确定该事件状态所执行的局部解前，先在该事件状态下向后模拟n步，提前对第k个事件状态的后n步进行前瞻，使后续步骤能够关注第k个事件状态及后续状态的情况，同时也使最后执行的局部解具备考虑整体最优的特性。具体地，在步骤S1中每向后模拟1步时均能够得到向后模拟该一步时的若干个局部解，因此完成向后模拟n步时得到的是向后模拟第n步的若干个局部解。

S2：根据贪心算法和事件目标补全向后模拟第n步时得到的局部解得到对应的完整解；

具体地，补全是指将每一个向后模拟第n步得到的局部解作为已经执行的局部解，在每一个局部解的基础上利用贪心算法确定在事件的非最终状态(即第p个事件状态)前的每一个事件状态需要执行的局部解，直至得到事件的最终状态，在事件到达最终状态时也即得到事件的完整解。完整解具体是指从事件的某一个状态起一直到事件的最终状态的所有操作的集合。补全的过程不涉及对任何事件状态的向后模拟，仅基于贪心算法进行确定每个状态的局部解，从而得到完整解。

执行步骤S2：根据贪心算法和事件目标补全向后模拟第n步时得到的局部解得到对应的完整解；在步骤S1中通过向后模拟能够前瞻第k个事件状态的后n步的情况，如果对每个事件状态都向后模拟至最后得到完整解是整体最优的优选方案，但这一最优的优选方案需要耗费较长时间，不能够在合理的时间内得到最优局部解，因此步骤S2在步骤S1向后模拟了n步得到向后模拟第n步的若干个局部解后，补全每个局部解得到对应的完整解，补全的过程不再对任何事件状态涉及向后模拟的操作，保证整个方法能够在合理的时间内确定最终执行的最优局部解，该最优局部解是在合理时间限制下的近似最优局部解。

S3：根据事件目标确定步骤S2得到的完整解中的最优完整解；

具体地，如图2所示，步骤S3的具体执行过程为：确定各个步骤S2得到的完整解的目标函数值，根据事件目标确定其中一个完整解的目标函数值作为最优目标函数值，将最优目标函数值对应的完整解作为最优完整解。

执行步骤S3：根据事件目标确定完整解的目标函数，根据完整解包括的所有操作确定对应的目标函数值，再根据事件目标从多个完整解的目标函数值中选出最优目标函数值，将最优目标函数值对应的完整解作为最优完整解。例如，当事件为对商品进行装箱，包含装箱求解问题，事件目标假设是指包装箱的数量达到最精简(即尽可能达到最少)，则完整解的目标函数就是在执行完整解后用于确定/计算所使用的包装箱数量的函数，而目标函数值就是在执行完整解后所使用的包装箱的具体数量，由于事件目标是需要包装箱的数量达到最少，因此在多个目标函数值中数值最小的确定为最优目标函数值，该最优目标函数值所对应的完整解则作为最优完整解。

S4：根据步骤S3得到的最优完整解回溯至步骤S1中向后模拟第1步时得到的对应的局部解作为最优局部解，在第k个事件状态下执行最优局部解；

在步骤S3中确定了最优完整解对应的完整解，在步骤S4中对该完整解进行回溯，回溯至步骤S1中对应该完整解的向后模拟第1步得到的局部解，将其作为最优局部解，并在第k个事件状态下执行该最优局部解，最优局部解由于对应的是在第k个事件状态下向后模拟n步后选出的最优完整解，因此，该最优局部解虽然由贪心算法确定，但具备考虑整体最优解的特性。

具体地，如图2所示，在执行步骤S4后，还包括以下步骤：

S5：将k的值加一，执行步骤S01。在步骤S5中，由于步骤S1～S4已完成对第k个事件状态的最优局部解的确定，因此将k的值加一，重新执行步骤S01对下一个事件状态执行步骤S1～S4确定最优局部解，直至在步骤S01中k的值等于p为止，即使每个非最终状态的事件状态都能够适用于本方法确定最优局部解。

具体地，如图3所示，步骤S1的具体执行过程为：

S11：初始化第k个事件状态当前的模拟步数i的值为0；

S12：判断i的值是否为0，如是，执行步骤S13；如不是，执行步骤S14；

S13：根据贪心算法和事件目标对第k个事件状态向后模拟1步，得到向后模拟第1步时的若干个局部解，将i的值加一后执行步骤S12；

优选地，步骤S13的具体执行过程为：根据贪心算法确定在第k个事件状态下满足事件目标的前若干个局部解作为向后模拟第1步时的若干个局部解，向后模拟第1步时的每个局部解构成一个暂时事件状态k+1，将i的值加一后执行步骤S12；

S14：判断i的值是否小于n，如是，执行步骤S15；如不是，执行步骤S2；

S15：根据贪心算法和事件目标分别对向后模拟第i步时所得到的每个局部解向后模拟1步，得到向后模拟第i+1步时的若干个局部解，将i的值加一后执行步骤S14；

优选地，步骤S15的具体执行过程为：根据贪心算法分别确定若干个暂时事件状态k+i下满足事件目标的前若干个局部解，将所有在暂时状态k+i下满足事件目标的前若干个局部解作为向后模拟第i+1步时的局部解，向后模拟第i+1步时的每个局部解构成一个暂时时间状态k+i+1，将i的值加一后执行步骤S14。

步骤S11～S15具体化了步骤S1中对第k个事件状态向后模拟n步的过程，首先执行步骤S11：初始化第k个事件状态当前的模拟步数i的值为0，当前的模拟步数i代表第k个事件状态已向后模拟的步数，该步数从0开始；执行步骤S12：判断i的值是否为0，如是，则执行步骤S13：根据贪心算法和事件目标对第k个事件状态向后模拟1步得到若干个局部解，优选地，步骤S13具体是根据贪心算法确定在第k个事件状态下满足事件目标的前若干个局部解，该前若干个局部解是基于当前状态下最优的若干个选择，该前若干个局部解则为向后模拟第1步时达得到的若干个局部解，假若独立执行了该若干个局部解，则构成对应的若干个暂时事件状态k+1；由于第k个事件状态已经向后模拟了1步，因此当前的模拟步数i的值加一，在加一后执行步骤S12：判断i的值是否为0，执行步骤S14：判断i的值是否小于n，如是，执行步骤S15：根据贪心算法和事件目标分别对向后模拟第i步时所得到的每个局部解向后模拟1步得到若干个局部解，优选地，步骤S15具体是根据贪心算法分别确定若干个暂时事件状态k+i下满足事件目标的前若干个局部解作为向后模拟第i+1步时的局部解，即对每一个暂时事件状态k+i进行向后模拟1步，确定每一个暂时事件状态k+i下满足事件目标的前若干个局部解，将所有得到的局部解作为向后模拟第i+1的局部解，分别对应构成若干个暂时时间状态k+i+1，由于在暂时事件状态k+i下已经向后模拟了1步，因此当前的模拟步数i的值加一，在加一后执行步骤S14，如i此时未达到n的值，则重复执行步骤S15和步骤S14直至i的值达到n，即向后模拟的步数达到模拟步数的总数，在步骤S15中结束向后模拟，执行步骤S2对向后模拟第n步得到的若干个局部解进行补全。

如图4所示为n等于2时执行本实施例的方法的一个示例：对于状态K(对应为第k个事件状态，K＝k)，首先执行步骤S01，判断k的值是否小于p，k的值在本示例中默认为小于p，执行步骤S11：初始化状态K当前的模拟步数i的值为0，执行步骤S12：判断i的值是否为0，i的值为0，执行步骤S13：根据贪心算法确定在状态K下满足事件目标的前3个局部解，分别为局部解A、局部解B和局部解C，该局部解A、局部解B和局部解C则为状态K向后模拟第1步时得到的局部解，假若独立执行了局部解A、局部解B和局部解C，则会构成对应的3个暂时状态K+1(对应为暂时事件状态k+1)；由于状态K已经向后模拟了1步，因此当前的模拟步数i的值加一，执行步骤S12：判断i的值是否为0，i的值为1，执行步骤S14：判断i的值是否小于n，执行步骤S15：根据贪心算法确定由局部解A、局部解B和局部解C构成的3个暂时状态K+1下满足事件目标的前3个局部解，由局部解A构成的暂时状态K+1下满足事件目标的前3个局部解为①、局部解②和局部解③，由局部解B构成的暂时状态K+1下满足事件目标的前3个局部解为④、局部解⑤和局部解⑥，由局部解C构成的暂时状态K+1下满足事件目标的前3个局部解为⑦、局部解⑧和局部解⑨，9个局部解①～⑨构成向后模拟第2步时得到的局部解，由于在暂时状态K+1下已经向后模拟了1步，因此当前的模拟步数i的值加一，i的值为2，执行步骤S14：判断i的值是否小于n，由于i的值为2已经等于n的值，因此执行步骤S2：根据贪心算法和事件目标补全向后模拟第n步时得到的局部解得到对应的完整解，即根据贪心算法分别对每个局部解①～⑨补全满足事件目标的完整解，得到对应的9个完整解A1～A9，执行步骤S3：根据事件目标确定各个完整解A1～A9的目标函数以及目标函数值，根据事件目标确定其中一个完整解的目标函数值作为最优目标函数值，将最优目标函数值对应的完整解作为最优完整解，假设完整解A1的目标函数值确定为最优目标函数值，则完整解A1为最优完整解；执行步骤S4：根据步骤S3得到的最优完整解回溯至步骤S15和步骤S13确定向后模拟第1步时得到的对应的局部解，如完整解A1为最优完整解，则回溯至步骤S15确定向后模拟第2步时得到的对应的局部解为局部解①，再向前回溯至步骤S13确定向后模拟第1步时得到的对应的局部解为局部解A，将局部解A作为最优局部解，并在状态K下选择执行局部解A对应的操作，局部解A由贪心算法计算得到，是满足事件目标的前3个局部解之一，具备考虑当前较优的特性，同时，由于局部解A是向后模拟2步并补全的完整解中的最优完整解对应的局部解，因此局部解A还具备考虑整体最优的特性，弥补了贪心算法只注重当前最优的短视缺陷，实现整体利益最大化，避免局部利益与整体利益相冲突的情况，使在每个状态执行的局部解都充分考虑了对后一事件状态的影响。

基于与上述确定最优局部解的方法相同的思想，本实施例还提供一种补货方法，如图5所示，包括以下步骤：

T1：根据贪心算法和补货目标对第k个补货状态向后模拟n步得到向后模拟第n步时的若干个补货操作；

具体地，补货状态为补货事件的其中一个状态，补货事件中包含组合优化的补货问题。k的值满足0≤k≤p，p的值为补货状态的总数，第0个补货状态为补货事件的初始补货状态，第p个补货状态为补货事件的最终补货状态，也可以理解为补货事件的结束补货状态。补货操作是指在某一个补货状态下执行的操作，在一个补货状态下执行了任何操作都会导致该补货状态变为另一个补货状态，一般会认为是变为下一个补货状态。补货目标是指补货事件需要满足的给定条件；贪心算法的思想是找出当前补货状态下最满足给定条件的补货操作，由此可见，通过贪心算法确定最优补货操作时所考虑的首要条件是满足补货目标。具体地，n的值为向后模拟的模拟步数的总数，n的值满足n≥1，且k和n还满足n+k＜p，由此可见，n的值在k的值和p的值不同的情况下也会有所不同。n的初始值是预先设定的，但当n的预设值不满足n+k＜p，n的值则需要更换为满足n+k＜p这一关系式的值，例如，当k＝p-2时，则n的最大值为2，如果n的预设值为4，则需要更换为2或1。

如图6所示，在执行步骤T1前先执行步骤T01：判断k的值是否小于p，如否，则执行步骤T02：不作任何操作；如是，则执行步骤T1。

T2：根据贪心算法和补货目标补全步骤T1中向后模拟第n步时得到的补货操作得到对应的完整补货操作；

具体地，补全是指将每一个向后模拟第n步得到的补货操作作为已经执行的补货操作，在每一个补货操作的基础上利用贪心算法确定在补货事件的非最终状态(即第p个补货状态)前的每一个补货状态需要执行的补货操作，直至得到补货事件的最终状态，在补货事件到达最终状态时也即得到补货事件的完整补货操作。完整补货操作具体是指从补货事件的某一个补货状态起一直到补货事件的结束状态的所有操作的集合。补全的过程不涉及对补货操作的向后模拟，仅基于贪心算法进行补货操作的确定，从而得到完整补货操作。

T3：根据补货目标确定步骤T2得到的完整补货操作中的最优完整补货操作；

具体地，如图6所示，步骤T3的具体执行过程为：确定步骤T2得到的各个完整补货操作的目标函数值，根据补货目标确定其中一个完整补货操作的目标函数值作为最优目标函数值，将最优目标函数值对应的完整补货操作作为最优完整补货操作。

T4：根据最优完整补货操作回溯至向后模拟第1步时得到的对应的补货操作作为最优补货操作，在第k个补货状态下执行最优补货操作；

如图6所示，在执行步骤T4后还包括步骤T5：将k的值加一，执行步骤T0。在步骤T5中，由于步骤T1～T4已完成对第k个补货状态的最优补货操作的确定，因此将k的值加一，对下一个补货状态执行步骤T1～T4确定最优补货操作，直至在步骤T0中k的值等于p为止。

具体地，如图7所示，步骤T1的具体执行过程为：

T11：初始化第k个补货状态当前的模拟步数i的值为0；

T12：判断i的值是否为0，如是，执行步骤T13；如不是，执行步骤T14；

T13：根据贪心算法和补货目标对第k个补货状态向后模拟1步，得到向后模拟第1步时的若干个补货操作，将i的值加一后执行步骤T12；

优选地，步骤T13的具体执行过程为：根据贪心算法确定在第k个补货状态下满足补货目标的前若干个补货操作作为向后模拟第1步时的若干个补货操作，向后模拟第1步时的每个补货操作构成一个暂时补货状态k+1，将i的值加一后执行步骤T12；

T14：判断i的值是否小于n，如是，执行步骤T15；如不是，执行步骤T2；

T15：根据贪心算法和补货目标分别对向后模拟第i步时所得到的每个补货操作向后模拟1步，得到向后模拟第i+1步时的若干个补货操作，将i的值加一后执行步骤T14；

优选地，步骤T15的具体执行过程为：根据贪心算法分别确定若干个暂时补货态k+i下满足补货目标的前若干个补货操作，将所有暂时补货状态k+i下满足补货目标的前若干个补货操作作为向后模拟第i+1步时的补货操作，向后模拟第i+1步时的每个补货操作构成一个暂时补货状态k+i+1，将i的值加一后执行步骤T14。

以下结合实际例子对补货方法进行示例说明，实例的场景假设为：假设公司有M(M≥1)个仓库，每个仓库中存储N(N≥1)种产品，每个仓库对于每种产品有一个补货需求D

执行步骤T0：判断k的值是否小于p，k的值为0，执行步骤T11：初始化初始补货状态当前的模拟步数i的值为0，执行步骤T12：判断i的值是否为0，i的值为0，执行步骤T13：根据贪心算法确定在初始状态下满足收益最高的前3个补货操作，分别为补货操作(1)、补货操作(2)和补货操作(3)，该补货操作(1)、补货操作(2)和补货操作(3)则为初始状态向后模拟第1步时得到的补货操作，假设补货操作(1)为从工厂1将产品1补给仓库1，该操作的当前收益是500；补货操作(2)为从工厂2将产品3补给仓库1，该操作的当前收益是400；补货操作(3)为从工厂3将产品4补给仓库2，该操作的当前收益是300。

假若独立执行了补货操作(1)、补货操作(2)和补货操作(3)，则会构成对应的3个暂时补货状态1；由于初始状态已经向后模拟了1步，因此当前的模拟步数i的值加一，i的值为1，执行步骤T12：判断i的值是否为0，i的值为1，执行步骤T14：判断i的值是否小于2，执行步骤T15：根据贪心算法确定由补货操作(1)、补货操作(2)和补货操作(3)构成的3个暂时补货状态1下满足补货目标的前3个补货操作，共得到9个补货操作构成向后模拟第2步时得到的补货操作，由于在暂时补货状态1下已经向后模拟了1步，因此当前的模拟步数i的值加一，i的值为2，执行步骤T14：判断i的值是否小于2，由于i的值已经等于n的值，因此执行步骤T2：根据贪心算法和补货目标补全向后模拟第2步时得到的补货操作得到对应的完整补货操作，即根据贪心算法分别对向后模拟第2步时得到的9个补货操作补全满足收益最高的完整补货操作，得到对应的9个对应的完整补货操作，执行步骤T3：根据补货目标即收益最高的目标，确定各个完整补货操作的最终收益，选出收益最高的完整补货操作作为最优完整补货操作；执行步骤T4：根据步骤T3得到的最优完整补货操作回溯至步骤T15和步骤T13确定向后模拟第1步时得到的对应的补货操作(补货操作(1)、补货操作(2)和补货操作(3)的其中一个)，将该补货操作作为最优补货操作，在初始状态下选择执行最优补货操作，最优补货操作由贪心算法计算得到，是满足补货目标的前3个局部解之一，具备考虑当前较优的特性，同时，由于最优补货操作是向后模拟2步并补全的完整补货操作中的最优完整补货操作对应的局部解，因此最优补货操作还具备考虑整体最优的特性，弥补了贪心算法只注重当前最优的短视缺陷，实现整体利益最大化，避免局部利益与整体利益相冲突的情况，使在每个补货状态执行的补货操作都充分考虑了对后一补货状态的影响。

基于与上述确定最优解的方法相同的思想，本实施例还提供一种确定最优解的装置，如图8所示，包括：

模拟模块100，用于根据贪心算法和事件目标对第k个事件状态向后模拟n步得到向后模拟第n步时的若干个局部解；

补全模块200，用于补全向后模拟模块在向后模拟第n步时得到的局部解得到对应的完整解；

最优完整解确定模块300，用于根据事件目标确定补全模块得到的所有完整解中的最优完整解；

回溯执行模块400，用于根据最优完整解确定模块300所确定的最优完整解回溯至模拟模块100向后模拟第1步时得到的对应的局部解作为最优局部解，在第k个事件状态下执行最优局部解；

具体地，k满足0≤k≤p，p为事件状态的总数，n的值为向后模拟的模拟步数的总数，n满足n≥1，k和n还满足n+k＜p。

具体地，装置还包括数据处理模块500，用于判断k的值是否小于p；模拟模块100用于在数据处理模块500判定k的值小于p时执行根据贪心算法和事件目标对第k个事件状态向后模拟n步得到向后模拟第n步时的若干个局部解的操作。

具体地，数据处理模块500还用于在回溯执行模块400执行最优局部解后，将k的值加一，重复执行判断k的值是否小于p的操作直至k的值大于或等于p为止。

具体地，数据处理模块500还用于在模拟模块100执行根据贪心算法和事件目标对第k个事件状态向后模拟n步得到向后模拟第n步时的若干个局部解的操作之前，初始化第k个事件状态当前的模拟步数i的值为0。

模拟模块100用于根据贪心算法和事件目标对第k个事件状态向后模拟n步得到向后模拟第n步时的若干个局部解，具体为：

模拟模块100用于当i的值为0时，根据贪心算法和事件目标对第k个事件状态向后模拟1步，得到向后模拟第1步时的若干个局部解，将i的值加一；

模拟模块100还用于当i的值不为0且小于n时，根据贪心算法和事件目标，分别对向后模拟第i步时所得到的每个局部解向后模拟1步，得到向后模拟第i+1步时的若干个局部解，并将i的值加一。

优选地，模拟模块100具体用于当i的值为0时，根据贪心算法确定在第k个事件状态下满足事件目标的前若干个局部解作为向后模拟第1步时的若干个局部解，向后模拟第1步时的每个局部解构成一个暂时事件状态k+1，将i的值加一。

优选地，模拟模块100具体用于当i的值不为0且小于n时，根据贪心算法分别确定若干个暂时事件状态k+i下满足事件目标的前若干个局部解，将所有在暂时事件状态k+i下满足事件目标的前若干个局部解作为向后模拟第i+1步时的局部解，向后模拟第i+1步时的每个局部解构成一个暂时时间状态k+i+1，将i的值加一。

优选地，最优完整解确定模块300具体用于确定各个完整解的目标函数值，根据事件目标确定其中一个完整解的目标函数值作为最优目标函数值，将最优目标函数值对应的完整解作为最优完整解。

上述的确定最优解的装置的实施方式中，各功能模块的逻辑划分仅作为举例说明，实际应用中可根据需要，例如出于硬件的配置要求或软件的实现的考虑，将上述功能分配由不同的功能模块完成，即可对确定最优解的装置的内部结构划分为与上述内容不同的功能模块，但能够完成以上描述的全部功能。其次，上述示例的确定最优解的装置的模块的执行过程等内容，由于与本实施例前述的确定最优解的方法基于同一构思，其原理和所带来的技术效果与前述的确定最优解的方法相同，具体内容可参见方法实施方式的叙述，此处不再赘述。

基于与上述补货方法相同的思想，本实施例还提供一种确定补货装置，如图9所示，包括：

补货模拟模块10，用于根据贪心算法和补货目标对第k个补货状态向后模拟n步得到向后模拟第n步时的若干个补货操作；

补货操作补全模块20，用于补全向后模拟补货模块在向后模拟第n步时得到的补货操作得到对应的完整补货操作；

最优补货操作确定模块30，用于根据事件目标确定补货操作补全模块20得到的完整补货操作中的最优完整补货操作；

补货回溯执行模块40，用于根据最优补货操作确定模块30所确定的最优完整补货操作回溯至补货模拟模块10向后模拟第1步时得到的对应的补货操作作为最优补货操作，在第k个事件状态下执行最优补货操作；

其中，k满足0≤k≤p，p为事件状态的总数，n的值为向后模拟的模拟步数的总数，n满足n≥1，k和n还满足n+k＜p。

具体地，装置还包括数据处理模块50，用于判断k的值是否小于p；补货模拟模块10用于在数据处理模块50判定k的值小于p时执行根据贪心算法和事件目标对第k个补货状态向后模拟n步得到向后模拟第n步时的若干个补货操作的操作。

具体地，数据处理模块50还用于在补货回溯执行模块40执行最优补货操作后，将k的值加一，重复执行判断k的值是否小于p的操作直至k的值大于或等于p为止。

具体地，数据处理模块50还用于在模拟模块100执行根据贪心算法和事件目标对第k个补货状态向后模拟n步得到向后模拟第n步时的若干个补货操作的操作之前，初始化第k个补货状态当前的模拟步数i的值为0。

补货模拟模块10用于根据贪心算法和补货目标对第k个补货状态向后模拟n步得到向后模拟第n步时的若干个补货操作，具体为：

补货模拟模块10用于当i的值为0时，根据贪心算法和补货目标对第k个补货状态向后模拟1步，得到向后模拟第1步时的若干个补货操作，将i的值加一；

补货模拟模块10还用于当i的值不为0且小于n时，根据贪心算法和事件目标，分别对向后模拟第i步时所得到的每个补货操作向后模拟1步，得到向后模拟第i+1步时的若干个补货操作，并将i的值加一。

优选地，补货模拟模块10具体用于当i的值为0时，根据贪心算法确定在第k个事件状态下满足事件目标的前若干个补货操作作为向后模拟第1步时的若干个补货操作，向后模拟第1步时的每个补货操作构成一个暂时补货状态k+1，将i的值加一。

优选地，补货模拟模块10具体用于当i的值不为0且小于n时，根据贪心算法分别确定若干个暂时补货状态k+i下满足补货目标的前若干个补货操作，将所有在暂时补货状态k+i下满足补货目标的补货操作作为向后模拟第i+1步时的补货操作，向后模拟第i+1步时的每个补货操作构成一个暂时补货状态k+i+1，将i的值加一。

优选地，最优补货操作确定模块30具体用于确定各个完整补货操作的目标函数值，根据补货目标确定其中一个完整补货操作的目标函数值作为最优目标函数值，将最优目标函数值对应的完整补货操作作为最优完整补货操作。

上述的补货装置的实施方式中，各功能模块的逻辑划分仅作为举例说明，实际应用中可根据需要，例如出于硬件的配置要求或软件的实现的考虑，将上述功能分配由不同的功能模块完成，即可对补货装置的内部结构划分为与上述内容不同的功能模块，但能够完成以上描述的全部功能。其次，上述示例的补货装置的模块的执行过程等内容，由于与本实施例前述的补货方法基于同一构思，其原理和所带来的技术效果与前述的补货方法相同，具体内容可参见方法实施方式的叙述，此处不再赘述。

本实施例还提供一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现上述确定最优解的方法，或上述补货方法。

本实施例还提供一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现上述确定最优解的方法，或上述补货方法。

显然，本发明的上述实施例仅仅是为清楚地说明本发明技术方案所作的举例，而并非是对本发明的具体实施方式的限定。凡在本发明权利要求书的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。