hepl 将给定问题识别为图形
hepl in identifying the given problem to a graph
一个小偷从你那里偷东西，并获得了 20 米的领先优势。您可以在开阔的地面上轻松追上他，因为您可以 运行 两倍的速度，因此每行驶 10 米追上 5 米。一旦小偷到达他试图返回的时间扭曲，你就无法抓住他并且路径中有一堆河流：见图。有 N 个地方（用黑线标记）足够浅，可以穿过，但每穿过 10 米的河流，你就会落后 5 米。假设小偷害怕得不敢考虑向地图左侧移动。
给定起点和终点位置，以及 N 个交叉路口（两端）的位置，我想要一个算法来确定小偷是否有可能逃脱，即在你追上之前到达终点位置。
我正在努力解决这个问题..任何想法都非常感谢..谢谢
figure
有点不清楚这里到底需要什么，但这里是解决这个问题的方法的概述：
你需要根据给定的图片创建一个非循环图，其中包含两组权重，一组给你，一组给小偷，代表你们每个人走那么远需要多少时间（或者，两个非循环的形状相同但权重不同的图）：
nodes/vertexes 出自：起点和终点（时间扭曲）点、每座桥的入口点和每座桥的出口点。
创建将每座桥的入口点顶点连接到它们自己的出口点顶点的边。将小偷的 edge-weights 设置为桥的长度，并将你的设置为它的 1.5 倍。
从起点顶点到穿过第一个河的每座桥的入口点制作边。
从第一条河上每座桥的出口点顶点到第二条河上每座桥的入口点顶点制作边。
重复第 4 步，直到到达最后一条河流。
从最后河上每座桥的出口点顶点到时间扭曲的顶点创建边。
对于每条 non-bridge 条边，将小偷的权重设置为其长度，并将您的权重设置为该长度的一半。
现在，您可以使用 A* search algorithm 来确定他们和您需要多长时间才能到达时间扭曲。谁先到谁就赢了。
对于 A*，您需要某种全局最大距离估计函数，如果您不能为此推导某些东西，只需对每件事使用最大可能距离。如果这样做，A* 会变成 Djikstra's algorithm，它仍然有效，但速度较慢。
一个小偷从你那里偷东西，并获得了 20 米的领先优势。您可以在开阔的地面上轻松追上他，因为您可以 运行 两倍的速度，因此每行驶 10 米追上 5 米。一旦小偷到达他试图返回的时间扭曲，你就无法抓住他并且路径中有一堆河流：见图。有 N 个地方（用黑线标记）足够浅，可以穿过，但每穿过 10 米的河流，你就会落后 5 米。假设小偷害怕得不敢考虑向地图左侧移动。 给定起点和终点位置，以及 N 个交叉路口（两端）的位置，我想要一个算法来确定小偷是否有可能逃脱，即在你追上之前到达终点位置。 我正在努力解决这个问题..任何想法都非常感谢..谢谢
figure
有点不清楚这里到底需要什么，但这里是解决这个问题的方法的概述：
你需要根据给定的图片创建一个非循环图，其中包含两组权重，一组给你，一组给小偷，代表你们每个人走那么远需要多少时间（或者，两个非循环的形状相同但权重不同的图）：
nodes/vertexes 出自：起点和终点（时间扭曲）点、每座桥的入口点和每座桥的出口点。
创建将每座桥的入口点顶点连接到它们自己的出口点顶点的边。将小偷的 edge-weights 设置为桥的长度，并将你的设置为它的 1.5 倍。
从起点顶点到穿过第一个河的每座桥的入口点制作边。
从第一条河上每座桥的出口点顶点到第二条河上每座桥的入口点顶点制作边。
重复第 4 步，直到到达最后一条河流。
从最后河上每座桥的出口点顶点到时间扭曲的顶点创建边。
对于每条 non-bridge 条边，将小偷的权重设置为其长度，并将您的权重设置为该长度的一半。
现在，您可以使用 A* search algorithm 来确定他们和您需要多长时间才能到达时间扭曲。谁先到谁就赢了。
对于 A*，您需要某种全局最大距离估计函数，如果您不能为此推导某些东西，只需对每件事使用最大可能距离。如果这样做，A* 会变成 Djikstra's algorithm，它仍然有效，但速度较慢。