路徑查找應用算法

我想開發一個映射我的辦公室的應用程序（完全像谷歌地圖這樣的應用程序，顯示從一個座位到另一個座位的路徑）。路徑查找應用算法

從我迄今爲止閱讀的內容中，可以使用諸如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

路徑查找應用算法

回答

相關問題