基于蒙特卡罗树搜索的智能行程规划系统设计

引言

如今旅游越来越受到人们的欢迎，旅游规划成为了必不可少的事情。然而，对于大多数旅游新手来说，制作一份完美的旅游规划是非常困难的事情。如果寻求专业的旅游规划师的帮助，或许能获得很好的旅游行程规划，但需要的是专业的资质以及必要的金钱花费。
在人工智能迅速发展的当下，智能行程设计受到许多人的瞩目。智能行程算法只需要用户输入游玩偏好（如景点偏好、时间安排偏好、价格偏好），就能够从众多潜在游玩项目中找出最符合游客喜好的出游路线。根据旅游平台的数据，产品库存以及促销方案等都会反馈到行程算法中，从而提升行程规划的服务质量。
此外，游客出行完成之后，会对行程路线进行评价和反馈。等积累数据足够多后，AI算法就可以对海量数据进行挖掘分析，进一步优化行程算法模型。从而为游客提供越来越靠谱的游玩体验。

国内外研究现状

如今，智能行程规划已经被许多旅游公司所实现，速度最快的甚至只需要2秒即可完成行程规划，大大节省了用户等待的时间。其主要的实现方法是使用关键词匹配以及大数据运算来实现规划。
然而，现有行程规划存在诸多不足：
（1）流程上，如何确定预计旅行天数是让大多数用户迷惑的地方。对于一个不了解这个旅游景点的旅客，如何估计预计旅行天数非常困难。依然需要通过查看别人的攻略或者游记来确定在这个地方玩几天。
（2）智能生成行程，应该提供多种方案让用户选择。用户的行程会根据实际游玩体验而产生改变，一些不确定因素也会导致用户更改游玩路线。而目前的智能行程规划仅仅考虑了符合用户期望的最佳规划路线，并没有实现足够的灵活性。
（3）旅行点以及路途信息不详细。以国内最有名的百度旅游规划为例，百度旅游并没有把在路上需要花费的时间考虑进去，如何去景区、需要花费多少等等都没有提供详细的信息。此外，百度旅游对于美食和住宿的引导也不够。对于游客来说，到达一个不熟悉的旅游景点这两个方面是必须要考虑到的，这样才能获得更好的旅游体验。
（4）当前的行程规划没有实现最优惠出行建议。什么时候有最便宜的机票，怎么坐交通工具最省钱/最省时间、什么酒店或者餐饮最实惠/最方便/最优惠等等，这些并没有结合到当前的智能行程规划中去。

研究的基本内容

爬取相关旅游网站上的数据。
基于蒙特卡洛树搜索算法思想构建旅游行程规划AI。
实现旅游行程规划网站/APP/接口。

MCTS算法及UCT算法

MCTS算法

MCTS也就是蒙特卡罗树搜索（Monte Carlo Tree Search），是一类树搜索算法的统称，是一种基于树数据结构、能权衡探索与利用、在搜索空间巨大仍然比较有效的的搜索算法。一般的围棋AI算法都是基于MCTS实现的。
MCTS要解决的就是搜素空间巨大以至于不能计算得到所有子树价值的问题。MCTS给出的搜素策略较为高效，同时也兼顾探索和利用，尽量避免陷入局部最优解。MCTS实现这些特性的方法很多，较为经典的就是结合了UCB（Upper Confidence Bounds）公式的UCT算法（Upper Confidence Bound Apply to Tree）。

UCB算法

UCB算法，是MCTS的经典实现UCT（Upper Confidence bounds for Trees）里面用到的算法。其公式如下：

其中v’表示当前树节点，v表示父节点，Q表示这个树节点的累计quality值，N表示这个树节点的visit次数，C是一个常量参数（可以控制exploitation和exploration权重）。其中C常量我们可以使用 1 / sqrt{2} ，这是Kocsis、Szepesvari提出的经验值。
这个公式对每一个节点求一个值用于之后的选择，该值由两部分组成，左边的
是这个节点的平均收益值（越高表示这个节点期望收益好，越值得选择，用于exploitation），右边的
是这个父节点的总访问次数除以子节点的访问次数（如果子节点访问次数越少则值越大，越值得选择），因此使用这个公式是可以兼顾探索和利用的。

UCT算法

Kocsis 和 Szepervari 于 2006 年首先构建了一个完备的 MCTS 算法，通过扩展 UCB 到 minimax 树搜索，将其命名为 Upper Confidence Bounds for Trees（UCT）方法。经典的UCT算法工作步骤如图1所示：

参考：

https://yq.aliyun.com/articles/193863?type=2