路径查找应用算法

我想开发一个映射我的办公室的应用程序（完全像谷歌地图这样的应用程序，显示从一个座位到另一个座位的路径）。路径查找应用算法

从我迄今为止阅读的内容中，可以使用诸如Dijkstra的算法或Back Tracking的算法来解决该问题。但是这些算法需要一些2D矩阵（或其变体）作为输入。现在从管理的角度考虑应用程序，这个人只有办公楼的地图来作为应用程序的输入。这幅地图如何转换成这些算法可以作为输入的东西？或者我完全错过了什么？

任何建议，将不胜感激。

来源

2015-05-12 Peps0791

如果我正确地理解你的问题，它不是2天，它应该是3天。第一个d可以用来确定ppl是否来自同一楼层。如果他们在同一楼层，只需使用dijkstra的算法即可。如果不是，他们需要找到2条路径的最短路径。开始到电梯/步骤和电梯/步骤结束。 – nandu

让我们暂时假设它在同一层，dijkstra的需要以矩阵的形式输入，这是我想避免的。现在有一种可能，是我的问题！ – Peps0791

您可以使用“办公室的地板地图”图像作为二维矩阵 - 您只需使用不与任何障碍物相对应的“白色”像素在源点和目标点之间找到路径。 – mechatroner

其实矩阵不是必需的。该图可以在运行时生成。通过将图像转换成双色图像（其中一种颜色代表墙壁），可以将图像转换为墙壁和开放地点的地图。这看起来像你的要求：

define node: (int x , int y) 

define isWall: 
//this method is actually used for imageprocessing 
//i've forgotten the name of it, so if anyone knows it, pls comment 
    input: int rgb 
    output: boolean wall 

    int red = red(rgb) 
    int green = green(rgb) 
    int blue = blue(rgb) 

    int maxWallVal//comparison value 

    return (red + green + blue)/3 < maxWallVal 

define listNeighbours: 
    input: node n , int[][] img 
    output: list neighbours 

    int x = n.x 
    int y = n.y 

    list tmp 

    if x + 1 < img.length 
     add(tmp , (x + 1 , y) 
    if x > 0 
     add(tmp , (x - 1 , y) 
    if y + 1 < img[x].length 
     add(tmp , (x , y + 1) 
    if y > 0 
     add(tmp , (x , y - 1) 

    for node a in tmp 
     int rgb = img[a.x][a.y] 
     boolean wall = isWall(rgb) 

     if NOT wall 
      add(neighbours , a) 

    return neighbours 

define findPath: 
    input: node start , node end , int[][] img 
    output: list path 

    set visited 
    map prevNodes 

    queue nodes 
    add(nodes , start) 

    while NOT isEmpty(nodes) 
     node n = remove(0 , nodes) 

     if n == end 
      break  

     add(visited , nodes) 

     for node a in listNeighbours(n)//list all neighbour-fields that are no wall 
      if contains(visited , a) 
        continue 

      add(queue , a) 
      put(n , a) 

    node tmp = start 
    while tmp != null 
    add(path , tmp) 
    tmp = get(prevNodes , tmp) 

    return path

来源

2015-05-12 18:16:48 Paul

路径查找应用算法

回答

相关问题