通过坐标的最短距离 [英] shortest distance through coordinates

问题描述

我在xy平面上得到了一组点= {（x1，y1），（x2，y2），.....（xn，yn）}

，我得到两个点a（xa，ya）和b（xb，yb），并要求找到覆盖最短路径的点集。

点之间没有连接。如果我假设与其他所有点都存在连接，那么计算加权图的这些值将花费很长时间。有人可以告诉我应该做什么阅读。这个问题属于图形算法的主题是什么？！（有没有特定的算法）我已经坚持了好几天。注意：需要经过几点。不能越过这些点。无需遍历集合中的每个点。只需将您带到B点，这样做的距离就应该最小。例如：{（1,3），（1,4），（1,1），（5,2），（5,3），（1,4），（2,2），（1,2） ，（1,3）}
并假设A =（1,1）和B =（1,4），则路径= {（1,1），（1,2），（1,3） ，（1,4）}
注意：路径也不必是直线。也可以是锯齿形。

解决方案

由于我们一次最多可以移动两个距离单位，因此我们可以轻松地使用集合来实现DFS遍历，并且只需猜测点是否存在，因为我们必须猜测每个点最多8点：

 输入：设定点//放置在网格上的一组点
点a 
点b 
输出：列表路径//从a到b的点列表
 
地图的前任
 predecessor.put（a，null）
 
已访问
 visit.add（a）
 
 //存储由（行进距离，点）
 //组成的对，按距离升序排列到
 sortedset tovisit（sortyBy（pair :: first，compare :: ascending））
 tovisit.add（pair（0，a））
 
 //要检查的标志，如果找到了路径
 bo ol pathFound = false 
 
而！tovisit.isEmpty（）
对搜索= tovisit.remove（0）
 int dist = search.first（）
点pt = search.second（）
 
 //检查我们是否到达路径的末尾
如果pt == b 
 pathFound = true 
 break 
 
 //检查一个点是否存在于当前点的下方
 //距离未被访问的最多2个单位
 point next = point（pt.x，pt .y + 1）$ points.contains（next）
 if！visited.contains（next）
 predecessor.put（next，a）
 tovisit.add（pair（ dist + 1，next）
 else if points.contains（point（next.x，next.y + 1）
 next = point（pt.x，pt.y + 2）
 if！visited.contains（next）
 predecessor.put（next，a）
 tovisit.add（pair（dist + 2，next）
 
 //继续进行其他操作
 // ... 
 
 //如果！pathFound 
构建路径
返回null 
 
列表路径
节点tmp = b 
 do 
 path.prepend（tmp）
 tmp = predecessor.get（tmp）
 while tmp！= null 
 
返回路径
  

此代码利用了事实，那么我们只能在每个方向上最多移动2个单位，因此最多只能检查8个方向。

如果未指定，则必须首先建立一个代表网格的数据结构。一个简单的解决方案是构建一个栅格，在该栅格中每个点都与其直接邻居相连（最坏的情况 O（n ^ 2）），然后使用DFS遍历该栅格。 / p>

I am given a set of point in the x-y plane ={(x1,y1),(x2,y2),.....(xn,yn)}

and I am given two points a(xa,ya) and b(xb,yb) and asked to find the set of points that cover the shortest path.

no connection between points are given. If I assume a connection to every other point.it will take a long time to compute these values for a weighted graph. Can someone tell me what reading I should do. what topic does this problem come under graph algorithms?!!(Is there any specific algorithm) I have been stuck on this for days. note: need to go through the points. cannot jump across the points. NO need to travel each and every point in the set. JUST THE POINTS THAT TAKE YOU TO POINT B and the distance covered in doing so should be minimum. ex: { (1,3),(1,4),(1,1),(5,2),(5,3),(1,4),(2,2),(1,2),(1,3)} and suppose A=(1,1) and B=(1,4) then the path={(1,1),(1,2),(1,3),(1,4)} note: paths need not be straight lines.can be zig zag too.

解决方案

Since we can move at most two distance-units at a time, we can easily implement a DFS-traversal using sets and simply guessing whether points exist, since we have to guess for at most 8 points per point:

input: set points //a set of points that are placed on the grid
       point a
       point b
output: list path //a list of points, from a to b

map predecessor
predecessor.put(a , null)

set visited
visited.add(a)

//stores pairs consisting of (distance traveled , point)
//ordered ascending by distance to a
sortedset tovisit(sortyBy(pair::first , comparison::ascending)) 
tovisit.add(pair(0 , a))

//flag to check, if path was found
bool pathFound = false

while !tovisit.isEmpty()
    pair search = tovisit.remove(0)
    int dist = search.first()
    point pt = search.second()

    //check if we reached the end of the path
    if pt == b
        pathFound = true
        break

    //check if a point exists down from the current point
    //with a distance of at most 2 units that hasn't been visited
    point next = point(pt.x , pt.y + 1)
    if points.contains(next)
        if !visited.contains(next)
            predecessor.put(next , a)
            tovisit.add(pair(dist + 1 , next)
    else if points.contains(point(next.x , next.y + 1)
        next = point(pt.x , pt.y + 2)
        if !visited.contains(next)
            predecessor.put(next , a)
            tovisit.add(pair(dist + 2 , next)

    //proceed for other directions
    //...    

//build path
if !pathFound
    return null

list path
node tmp = b
do
    path.prepend(tmp)
    tmp = predecessor.get(tmp)
while tmp != null

return path

This code utilizes the fact, that we can only traverse at most 2 units in each direction, thus leaving us with at most 8 directions to check.

If this isn't given, we have to at first build a data-structure representing the grid. A simple solution would be to build a grid in which each point is connected to it's direct neighbors (worst case O(n ^ 2)) and traversing this grid with DFS.

这篇关于通过坐标的最短距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！