建立從棋盤鄰接圖（對於dijkstra）

我遇到了一個問題，我想添加一個小功能，我的作業，它變得對我來說是壓倒性的（讀大膽的句子沒有上下文的問題）。建立從棋盤鄰接圖（對於dijkstra）

我的程序有一個約35個項目的列表，其中包含有關我應該使用的地圖的信息。它可以有以下要素：

「牆」與它的座標（X，Y），在Dijkstra算法它應該有重量100
「樹」用繩索（X，Y）， 3重量

我有佈局像棋盤，這意味着100瓦和35項的10×10的地圖。列表中的「Nothing」意味着dijkstra中的權重1（這意味着正常路由）

爲了使dijkstra能夠工作並能夠在兩個tile之間找到最短路徑，我必須構建一個鄰接圖。 我的問題在於，如何定義當前瓷磚「周圍」的瓷磚，如果我擁有的是該清單？在「+」形狀

只有相鄰瓷磚在他們之間圖形的邊緣，但我必須在列表中運行檢查一次，如果有就可以了什麼時間？

任何問題的領導都將不勝感激，同樣如果你可以指向我的源代碼樣本，也可以。我只能看到很多「if-elseif-elseif ...」的雜亂代碼來解決這個問題。

謝謝你的時間！

編輯：我最終使用了@kraskevich的建議方式，它效果很好，但所有的答案和建議都非常有用，非常感謝大家！

來源

2017-06-02 Dragonturtle

這似乎基於一個誤解，沒有必要t o *實際上爲Dijkstra構建一個圖形，它隱含地使圖形「存在」是完全正確的（實際上更常見）。 – harold

@harold你有沒有僞代碼，或者只是一個描述，我可以在那裏建立沒有圖形的dijkstra？我會很高興！ – Dragonturtle

僞代碼是完全一樣的，它從來沒有提到圖表。除非你正在看奇怪的低級僞代碼。 – harold

你並不需要建立圖表。只要創建一個10x10表，並把相應的物品的重量進去：

board = 10x10 array filled with 1 
for item in list: 
    if item is a tree: 
     board[item.row][item.column] = 3 
    else if item is a wall: 
     board[item.row][item.column] = 100

之後，你可以把對座標(row, col)爲頂點，當你處理一個平鋪更新4個相鄰單元的距離。而已。當然，您也可以創建一個包含100個頂點的圖形，並從一個圖塊向所有4個相鄰的單元格明確添加邊（重量是邊圖塊末端的權重），並使用標準實現。

最方便的方式相鄰小區遍歷如下：

delta_rows = [-1, 1, 0, 0] 
delta_cols = [0, 0, -1, 1] 
... 
for direction = 0 .. 3 
    new_row = row + delta_rows[direction] 
    new_col = col + delta_cols[direction] 
    if is_valid(new_row, new_col) 
      // do something

來源

2017-06-02 19:13:02 kraskevich

它應該是簡單的基於這個通用的圖形界面來實現的Dijkstra：

interface Graph<T> { 
    Iterable<T> adjacentNodes(T node); 
    double getDistance(T node, T adjacent); 
}

所以，現在我們只需要要做的是填寫你的情況：

class Field { 
    final int x; 
    final int y; 
    int value = 1; 
    Field (int x, int y) { 
    this.x = x; 
    this.y = y; 
    } 
} 

class ChessboardGraph implements Graph<Field> { 
    Field[][] board = new Filed[10][10]; 

    ChessboardGraph(List<Entry> list) { 
    for (int x = 0; x < 10; x++) { 
     for (int y = 0; y < 10; y++) { 
     board[x][y] = new Field(x, y); 
     } 
    } 
    for (Entry e: list) { 
     board[e.x][e.y].value = e.value == TREE ? 3 : 100; 
    } 
    } 

    Iterable<Field> adjacentNodes(Field node) { 
    ArrayList result = new ArrayList<>(); 
    int x = node.x; 
    int y = node.y; 
    if (x > 0) { 
     if (y > 0) { 
     result.add(board[x - 1][y - 1]); 
     } 
     if (y < 9) { 
     result.add(board[x - 1][y + 1]); 
     } 
    } 
    if (x < 9) { 
     if (y > 0) { 
     result.add(board[x + 1][y - 1]); 
     } 
     if (y < 9) { 
     result.add(board[x + 1][y + 1]); 
     } 
    } 
    } 

    double getDistance(Field node, Field adjacent) { 
    assert Math.abs(node.x - adjacent.x) + Math.abs(node.y - adjacent.y) == 1; 
    return board[adjacent.x][adjacent.y]; 
    } 
}

來源

2017-06-02 20:04:45

建立從棋盤鄰接圖（對於dijkstra）

回答

相關問題