论文部分内容阅读
随着互联网广告的兴起，越来越多的商业机构通过投放网络广告获得客户购买行为，来产生利润。其中百度的搜索推广系统应用最为普遍，利用其精准的关键词定位技术，将高质量的企业推广结果展现给有商业意图的网民。本文主要针对在百度搜索推广系统中投放广告的广告主，在其账户的投资额固定时，求解一种关键词的投资选择策略，使得总收益最大。
该问题的数学模型类似于分组背包问题。其中贪心算法、动态规划均＼已应用到该问题中。
贪心算法是是通过一系列选择给出问题的最优解。对算法的每一个决策点，根据某个优化测度做出局部最优选择，省去了为找最优解穷尽所有可能而耗费的大量时间，极大的降低了时间复杂度。但对本文的竞价广告投资优化问题无法得到全局最优解，得到的只是近似解。
动态规划也解决这种最优化问题的普遍方法。其基本思想是，将目标问题分解为相似的目标子问题，在求解的过程中通过目标子问题的解求出目标问题的解。动态规划求解最优化问题给出的策略是最优解，但是时间复杂度与空间复杂度都随着问题的规模增大而增大。由于动态规划需要记录每个中间状态的解的信息，因此时间和空间花销都很大，不适用于本文大规模的竞价广告优化问题。
本文主要针对贪心算法和原始动态规划的缺点，提出了两种动态规划的改进算法，给出竞价广告投资优化问题的最优解。并降低了动态规划的时间和空间复杂度，改进了算法的空间花销，提高了解决问题的可行性。