路径寻找算法以最大化沿路线的兴趣点 [英] Path finding algorithm to maximise points of interest along the route

问题描述

我正在尝试编写一个算法来找到给定起点和终点之间的路径（不一定是最短路径）。



用户将输入起始位置，结束位置和可用的旅行时间。对于我图表的每个eadge，我知道遍历该边缘的时间成本以及沿着该边缘的兴趣点的增益。



到目前为止我只找到了对星型路由算法或对它的优化仅计算最短路径。



您能否给我一些关于我应该使用什么算法或一些解决方案的提示类似的问题？



谢谢，

Radu-Stefan

Hi,

I am trying to write an algorithm to find a path (not necessarily the shortest one) between a given start and end point.

An user will enter the start location, the end location and the available time to travel. For each eadge of my graph I know the cost in time to traverse that edge and the gain in points of interest along that edge.

Until now I only found references to A Star routing algorithm or optimisations to it witch only compute the shortest path.

Could you please give me some hints on what algorithm should I use or some references to solutions of similar problems?

Thank you,
Radu-Stefan

推荐答案

路由算法试图最小化成本 - 通过距离或行程时间来衡量。我天真地尝试将您的问题转化为这样的优化。我不确定以下想法是否有效：

假设每个旅行时间有多个POI（取最大值或高于它的值）。现在，当您计算细分市场的成本时，请使用该值与该细分市场中遇到的POI数量之间的差异作为错过的POI的度量。然后使用常用算法来最小化错过的POI数量。

我担心可能不会总是满足可用时间的约束。

Routing algorithms try to minimize costs - measured by the distance or by the travel time. I'd naively try to translate your problem into such an optimization. I am not sure whether following idea works:
Assume a number of POIs per travel time (take the maximum or a value above it). When you now calculate the costs of your segments, use the difference between that value and the number of POIs encountered along that segment as a measure for "missed POIs". And then use the common algorithms for minimizing the number of missed POIs.
I fear that the constraint of the available time might not always be met.

这篇关于路径寻找算法以最大化沿路线的兴趣点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！