資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python矩陣中的廣度優先搜尋
在給定的矩陣中，有四個物件用於分析元素位置：左、右、下和上。
廣度優先搜尋就是找到給定二維矩陣的兩個元素之間的最短距離。因此，在每個單元格中，我們可以執行四個操作，可以用四個數字表示為：
- ‘2’表示矩陣中的單元格是源點。
- ‘3’表示矩陣中的單元格是目標點。
- ‘1’表示可以沿某個方向進一步移動該單元格。
- ‘0’表示不能沿任何方向移動矩陣中的單元格。
基於上述說明，我們可以對給定的矩陣執行廣度優先搜尋操作。
解決這個問題的方法
使用BFS遍歷整個矩陣並找到任何單元格之間最小或最短距離的演算法如下：
- 首先輸入行和列。
- 用給定的行和列初始化一個矩陣。
- 一個整數函式`shortestDist(int row, int col, int mat[][col])`以行、列和矩陣作為輸入，並返回矩陣元素之間的最短距離。
- 初始化變數`source`和`destination`以找出源元素和目標元素。
- 如果元素是‘3’，則將其標記為目標點；如果元素是‘2’，則將其標記為源元素。
- 現在初始化佇列資料結構，以在給定的矩陣上實現廣度優先搜尋。
- 將矩陣的行和列作為對插入佇列中。現在移動到單元格中，並找出它是否是目標單元格。如果目標單元格的距離最小或小於當前單元格，則更新距離。
- 再次移動到另一個方向，以找出從當前單元格到該單元格的最小距離。
- 返回最小距離作為輸出。
示例
import queue
INF = 10000
class Node:
def __init__(self, i, j):
self.row_num = i
self.col_num = j
def findDistance(row, col, mat):
source_i = 0
source_j = 0
destination_i = 0
destination_j = 0
for i in range(0, row):
for j in range(0, col):
if mat[i][j] == 2 :
source_i = i
source_j = j
if mat[i][j] == 3 :
destination_i = i
destination_j = j
dist = []
for i in range(0, row):
sublist = []
for j in range(0, col):
sublist.append(INF)
dist.append(sublist)
# initialise queue to start BFS on matrix
q = queue.Queue()
source = Node(source_i, source_j)
q.put(source)
dist[source_i][source_j] = 0
# modified BFS by add constraint checks
while (not q.empty()):
# extract and remove the node from the front of queue
temp = q.get()
x = temp.row_num
y = temp.col_num
# If move towards left is allowed or it is the destnation cell
if y - 1 >= 0 and (mat[x][y - 1] == 1 or mat[x][y - 1] == 3) :
# if distance to reach the cell to the left is less than the computed previous path distance, update it
if dist[x][y] + 1 < dist[x][y - 1] :
dist[x][y - 1] = dist[x][y] + 1
next = Node(x, y - 1)
q.put(next)
# If move towards right is allowed or it is the destination cell
if y + 1 < col and (mat[x][y + 1] == 1 or mat[x][y + 1] == 3) :
# if distance to reach the cell to the right is less than the computed previous path distance, update it
if dist[x][y] + 1 < dist[x][y + 1] :
dist[x][y + 1] = dist[x][y] + 1
next = Node(x, y + 1)
q.put(next);
# If move towards up is allowed or it is the destination cell
if x - 1 >= 0 and (mat[x - 1][y] == 1 or mat[x-1][y] == 3) :
# if distance to reach the cell to the up is less than the computed previous path distance, update it
if dist[x][y] + 1 < dist[x - 1][y] :
dist[x - 1][y] = dist[x][y] + 1
next = Node(x - 1, y)
q.put(next)
# If move towards down is allowed or it is the destination cell
if x + 1 < row and (mat[x + 1][y] == 1 or mat[x+1][y] == 3) :
# if distance to reach the cell to the down is less than the computed previous path distance, update it
if dist[x][y] + 1 < dist[x + 1][y] :
dist[x + 1][y] = dist[x][y] + 1
next = Node(x + 1, y)
q.put(next)
return dist[destination_i][destination_j]
row = 5
col = 5
mat = [ [1, 0, 0, 2, 1],
[1, 0, 2, 1, 1],
[0, 1, 1, 1, 0],
[3, 2, 0, 0, 1],
[3, 1, 0, 0, 1] ]
answer = findDistance(row, col, mat);
if answer == INF :
print("No Path Found")
else:
print("The Shortest Distance between Source and Destination is:")
print(answer)輸出
The Shortest Distance between Source and Destination is:2
更新於：2021年2月23日
2K+ 次瀏覽
廣告