너비 우선 탐색(BFS)은 그래프에서 경로를 탐색하는 기본적인 알고리즘 중 하나로,
시작 정점을 방문한 후, 해당 정점과 인접한 모든 정점을 우선적으로 탐색하는 방법입니다.
이 방식은 출발지와 목적지 까지의 최단 경로를 찾는 데 사용하는 알고리즘 입니다.
위 그래프를 예를 들면 노드 A에서 시작하여, 각 레벨의 노드들이 너비 우선으로 탐색하여,
결과적으로는 A→B→C→D→E→F→G 의 순서로 노드를 방문합니다.
물류 최적화 분야에서 BFS는 창고에서 작업자의 동선 거리를 계산하는 데 활용될 수 있습니다.
창고는 보통 랙(Rack)과 평치를 할 수 있는 구역으로 구분되어 있으며, 사람이나 지게차가 통행할 수 있는 공간을 명확하게 식별할 수 있습니다.
따라서 창고에서 작업자의 이동거리를 단순히 직선 거리로 계산하면 큰 오차가 발생할 수 있습니다.
계산해야 하는 거리에 가중치가 존재하는 경우에는 다익스트라(Dijkstra) 알고리즘과 같은 다른 방법을 사용해야 하지만
창고에서는 일반적인 경우 BFS를 사용해서 거리를 계산해도 큰 무리는 없을 것으로 생각합니다.
이제 BFS를 설명하기 위해 4x4 그리드를 사용해 보겠습니다.
가장 좌측 상단의 (0, 0)에서 출발하여, 우측 하단의 (3, 3)으로 이동하는 최단 경로를 구하는 문제는 BFS를 통해 다음과 같은 방법으로 해결할 수 있습니다:
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
