小B在闲暇时到X主题公园游玩。X主题公园主要有9个景点，分别用1，2，…，9标识，它们的相对位置如图10-5所示，其中4和8是小B一定要去游览的两个景点。小B对每个景点的喜好程度及基本参观时间如表10-6所示，喜好程度一般与满足感成正比。表10-7为出入口及各景点间的行走时间。小B上午9时从入口（用0标识）进入X，下午17时30分从出口（用10标识）离开。由于正值旺季，部分景点需要排队，不同的时段，排队等待的时间不同。各景点在9：00～10：00、10：00～11：00、11：00～12：00、12：00～13：00、13：00～14：00、14：00～15：00、15：00～16：00不同时段的排队时间如表10-8所示。为保证17时30分前离开X，16时后不再排队。从表10.8中可以看到，景点1和景点2不用排队游览。指定点和非指定点在不同时段的等待时间曲线图分别如图10-6、10-7所示。

图10-5 起讫点及各景点的相对位置图

表10-6 小B对各景点的喜好程度及基本参观时间

表10-7 出入口及各景点间的行走时间 （单位：h）

表10-8 各景点在不同时段内的等待时间 （单位：h）

(www.daowen.com)

图10-6 指定点在不同时段的等待时间曲线图

图10-7 非指定点在不同时段的等待时间曲线图

从图10-6中可以看出，两指定点的等待时间随时间的推移，上午呈上升趋势，中午左右比较平稳，下午则呈下降趋势。因此，应选择在上午刚开始的时段和下午的后半时段游览指定点，尽量避免中午时段。根据指定点4和8的等待时间特点和点间距离，在9：00～10：00时段游览指定点4、在15：00～16：00时段游览指定点8的策略可以使两指定点的总等待时间最少。在这种游览策略下，游客小B从入口进入X后将指定点4作为第一个游览景点。离开指定点4的时间为10：36。

分别计算景点1、2、3、5、7、9单位时间的收益，选择单位时间收益最大的景点作为景点4的紧后游览景点。以景点1为例介绍景点的单位时间收益的计算。小B对景点1的喜好程度是55，从景点4到景点1的行走时间为0.5h，到达景点1的时间为11：06后，此时需要等待时间为0，参观景点1需要0.3h，因此景点1的单位时间收益为68.75，即单位时间收益=喜好程度/（行走时间+等待时间+基本参观时间）。经计算，景点1、2、3、5、7、9中，2的单位时间收益最大。继景点4后，小B接着游览景点2，离开2的时间为11：09。按照上述的游览方法，后续的游览景点依次有1、3、5、8，17：15离开X，总的满意度为435。游览路径P如图10-8所示。

图10-8 贪婪算法求解的路径P