너비 우선 탐색(BFS)은 그래프에서 경로를 탐색하는 기본적인 알고리즘 중 하나로,
시작 정점을 방문한 후, 해당 정점과 인접한 모든 정점을 우선적으로 탐색하는 방법입니다.
이 방식은 출발지와 목적지 까지의 최단 경로를 찾는 데 사용하는 알고리즘 입니다.
위 그래프를 예를 들면 노드 A에서 시작하여, 각 레벨의 노드들이 너비 우선으로 탐색하여,
결과적으로는 A→B→C→D→E→F→G 의 순서로 노드를 방문합니다.
물류 최적화 분야에서 BFS는 창고에서 작업자의 동선 거리를 계산하는 데 활용될 수 있습니다.
창고는 보통 랙(Rack)과 평치를 할 수 있는 구역으로 구분되어 있으며, 사람이나 지게차가 통행할 수 있는 공간을 명확하게 식별할 수 있습니다.
따라서 창고에서 작업자의 이동거리를 단순히 직선 거리로 계산하면 큰 오차가 발생할 수 있습니다.
계산해야 하는 거리에 가중치가 존재하는 경우에는 다익스트라(Dijkstra) 알고리즘과 같은 다른 방법을 사용해야 하지만
창고에서는 일반적인 경우 BFS를 사용해서 거리를 계산해도 큰 무리는 없을 것으로 생각합니다.
BFS를 설명하기 위해 4x4 그리드를 사용해 보겠습니다.
가장 좌측 상단의 (0, 0)에서 출발하여, 우측 하단의 (3, 3)으로 이동하는 최단 경로를 구하는 문제는 다음과 같은 방법으로 해결할 수 있습니다:
1.
(0, 0)에서 출발하여 인접한 모든 노드를 큐에 넣습니다.
2.
큐에서 노드를 하나씩 꺼내어, 그 노드와 인접한 노드들을 탐색하고, 이미 방문한 노드를 제외한 나머지를 다시 큐에 넣습니다.
3.
이 과정을 반복하여 (3, 3)에 도달하면, 해당 경로가 최단 경로가 됩니다.
이처럼 BFS는 다양한 경로 탐색 문제에서 매우 유용하게 사용될 수 있습니다.
전체 소스
def main():
input = makeInput()
#행
xSize = len(input)
#열
ySize = len(input[0])
fromX = 0
fromY = 0
toX = 3
toY = 3
#방문한 distance
visited = [[0 for j in range (ySize)] for i in range(xSize)]
directionX = [-1, 1, 0, 0]
directionY = [0, 0, -1, 1]
queue = [(fromX,fromY)]
visited[fromX][fromY] = 1
while queue:
x, y = queue.pop(0)
if x == toX and y == toY:
print(visited[x][y]-1)
break
for i in range(4):
nextX = x + directionX[i]
nextY = y + directionY[i]
if 0 <= nextX < xSize and 0 <= nextY < ySize:
if visited[nextX][nextY] == 0 and input[nextX][nextY] == 1:
visited[nextX][nextY] = visited[x][y] + 1
queue.append((nextX, nextY))
def makeInput():
input = [
[1,1,1,1],
[0,1,0,1],
[0,1,1,1],
[1,1,1,1],
]
return input
if __name__ == '__main__':
main()
Python
복사
결과는 아래와 같습니다.
(0,0) → (0,1) → (1,1) → (2,1) → (3,1) → (3,2) → (3,3)
Keyword: Logistics Optimization, 물류 최적화, 파이썬, Python, 선형계획법, Linear Programming, Google OR Tools
Reference
