자료구조 프로젝트 FIN

▼자료구조 프로젝트 목록

2022.10.18 - [프로젝트] - 자료구조 프로젝트 MID

2022.12.04 - [프로젝트] - 자료구조 프로젝트 FIN

※ 본 프로젝트의 전체 코드는 여기서 확인하실 수 있습니다.

 

이전 글 요약

본 자료구조 프로젝트의 목표는 이전 글에서 작성했다시피, 직접 구축한 하천 부유 쓰레기 데이터를 이용해 문제를 정의하고 해결하는 것이었습니다. 저는 하천별 쓰레기양을 기준으로 스케줄링하여 관리하는 방법을 제안했는데요. 이를 위해 red-black tree를 이용하고자 했습니다. 다만 기말 프로젝트를 준비하면서 수정된 부분이 많기 때문에 다시 문제부터 소개하기로 하겠습니다.

 

문제 소개

저는 단순히 하천별 스케줄링을 할 뿐만 아니라, 쓰레기가 많은 하천에서 시작하여 데이터로 저장된 모든 쓰레기를 수거할 수 있도록 문제를 구성하였습니다. 이를 위해 몇 가지 가정을 하였습니다.

1. 하천들의 상태를 관리해주며, 청소가 시급한 장소를 알려주는 스케줄러가 있다.
2. 하천 쓰레기 수거용 로봇이 2대 있다. 이 로봇들은 국지적인 경로를 따라 하천을 부유하며 쓰레기를 수거한 뒤 출발점으로 돌아온다.
3. 로봇을 관리하는 매니저가 있다. 매니저는 쓰레기 데이터를 가공하고, 스케줄러를 이용하여 로봇이 가야 할 장소를 지정한다. 또한 로봇이 자신의 경로를 생성할 수 있도록 사전 처리를 해준다.

 

이에 해당하는 코드 파일 목록은 다음과 같습니다. 아래 3개 파일은 전처리 및 자료구조 사용을 위한 코드입니다.

scheduler.py                # red-black tree 코드를 포함합니다.
collect_manager.py      # (CollectManager 및 CollectBot을 포함합니다.)
garbage_collect.py       # (코드 실행을 위한 main 함수는 이 파일에 있습니다.)
preprocessing.py
prim.py
dfs.py

 

사실 스케줄러를 만드는 것은 어렵지 않습니다. 이진탐색트리의 일종인 red-black tree의 원형을 데이터 형태만 맞게 가공하고, key가 최대값인 노드를 반환하는 함수를 추가하면 끝입니다. 다만 위도·경도 데이터만 가지고 해당 데이터가 어떤 하천인지 구분하는 것은 어려웠습니다. 가장 큰 문제는 데이터 자체에 있는데, 위도·경도 정보가 소수점 2자리까지만 존재하는 데이터가 많았기 때문입니다. 이정도 수치로는 엄밀한 위치 구분은 불가능합니다. 따라서 아쉽지만 '하천별'로 스케줄링을 하는 것은 포기하고, 대신 위도·경도를 기준으로 데이터를 분리하기로 하였습니다. 위도와 경도를 소수점 1자리까지 내림하여 이 위치에 해당하는 데이터들을 누적했습니다.

누적한 데이터는 사진과 같습니다.

 

사실 스케줄러보다도 제가 시간을 들여 고민한 부분은, 어떻게 해서 로봇이 모든 쓰레기를 수거할 수 있는 경로를 만들 것인가? 였습니다. 이 문제를 해결하기 위해 몇 가지 단계가 필요했는데요.

 

첫째로 위도·경도만 존재하는 데이터를 가지고 어떻게 그래프 초안을 구성할지가 문제였습니다. 효율적인 수거 경로를 구성하기 위해서는 먼저 간선이 존재하는 그래프가 필요했지만, 제가 임의로 간선을 넣을 수는 없는 노릇이었습니다.

두 번째 문제는, 그래프 초안을 가지고 어떻게 최단 경로를 만들 수 있을지였습니다. 시작 노드 S으로부터 임의의 노드 N까지의 최단 경로를 구하는 알고리즘은 간단합니다. dijkstra 알고리즘이나 floyd 알고리즘을 사용하면 됩니다. 하지만 모든 노드를 최단 경로로 한번에 탐색하는 알고리즘은 존재하지 않는 것으로 알고 있습니다.

 

저는 이 두 가지 문제를 해결하기 위해 두 종류의 알고리즘을 결합하기로 했습니다. 구체적인 해결 방법은 다다음 목차에서 설명하도록 하겠습니다.

 

데이터 소개

제가 사용한 데이터는 아래 링크에서 공유받았습니다.

GitHub - dapin1490/waste-complain-system: river waste complain system simulation project

학생들이 수집한 52개의 데이터 파일을 모두 합친 데이터로, 쓰레기 데이터 숫자는 약 5000개 정도입니다.

모두 직접 촬영하고 수집한 것이기에 특정 지역에 데이터가 몰려 있다는 특징이 있습니다. 따라서 제가 풀고자 하는 쓰레기양을 기준으로 스케줄링한다는 문제에는 적합하지 않은 데이터입니다만, 이 점은 감안해 주시길 바랍니다.저는 이 데이터를 대부분 사용했지만 알고리즘상의 문제로 사용하지 않은 데이터도 몇 줄 존재합니다.

 

문제 해결

스케줄러에 대한 설명은 위에서 했으므로 생략하도록 하고, 로봇이 쓰레기를 수거하는 경로를 어떻게 생성할 것인지에 집중하도록 하겠습니다.스케줄러가 쓰레기양이 가장 많은 위치의 위도·경도를 반환하면, 로봇을 관리하는 매니저가 해당 정보를 받아갑니다. 그리고 기존에 가지고 있던 전체 쓰레기 데이터에서 필요한 데이터만 잘라냅니다. 여기서 쓰레기 데이터가 특정 개수 이상이면, 매니저는 두 대의 로봇에게 데이터를 분할하게 됩니다. 한 로봇이 과중한 업무를 떠안지 않도록 조치하는 것입니다.그러고 나서 매니저는 각 로봇이 사용할 그래프 초안을 생성하는데, 모든 쓰레기 사이의 거리를 구한 뒤 완전연결 그래프를 생성하게 됩니다. 여기서 쓰레기간 거리를 구할 때는 하버시안 공식을 이용할 것입니다. 하버시안 공식은 좌표계 거리를 계산해주는 공식으로, 이를 통해 계산한 실제 거리를 알고리즘에 사용할 것입니다.

 

매니저가 생성한 완전연결 그래프를 로봇에게 넘겨주면, 로봇은 이 그래프를 가지고 자신의 쓰레기 수거 경로를 생성합니다. 이를 위해 두 단계를 거치는데요,

1. prim 알고리즘을 이용해 모든 쓰레기(정점)를 연결하는 최소 비용 신장 트리를 생성합니다.
2. 1번에서 생성한 트리를 깊이 우선 탐색(DFS)를 이용해 탐색합니다.

이 과정을 거치면 단 하나의 경로만으로 모든 쓰레기를 수거할 수 있습니다.

dijkstra 알고리즘을 여러번 돌리는 등의 방법도 생각해 보았지만, 데이터 특성상 이 방법은 이동 경로에 있어서 비효율적이라고 생각했습니다. 기본적으로 이 데이터는 하천을 따라 학생들이 직접 촬영한 데이터라서, 거의 일직선 모양을 띄고 있습니다. 그런데 그 쓰레기들을 한번에 수거하지 않고 여러번 왔다갔다하는 것은 아무래도 효율이 좋지 않습니다.

한편 트리가 거의 일직선 모양이라는 것은, DFS를 사용하기에 적합하다는 생각이 들었습니다. 쓰레기를 수거하러 나갔다가 돌아오는 과정에서 멀리 동떨어진 쓰레기들도 수거해올 수 있으니까요.

이러한 이유로 번거롭지만 2개의 알고리즘을 같이 사용하기로 했습니다. 기본적인 기능만 사용하므로 알고리즘에 큰 변형은 필요하지 않습니다.

 

결과

결과는 로그 파일로 저장되도록 했습니다. 다음과 같은 내용이 모든 쓰레기를 수거할 때까지 반복됩니다.

다른 방식으로 문제를 해결한 다음 시간 복잡도 측면에서 비교해 보고 싶었는데, 거기까지는 시간이 부족해 하지 못했습니다. 추후에 시간이 나면 추가하도록 하겠습니다.

프로젝트를 마치고 뒤늦게 떠올린 것이지만, '한 번에 모든 쓰레기를 수거한다'에 너무 집착했다는 생각이 드네요. 쓰레기 수거 후 로봇이 돌아갈 수 있는 처리장을 하천 유역에 n개 설치하고, 해당 노드까지 다익스트라 알고리즘 등으로 찾아가며 쓰레기를 수거하는 쪽이 더 현실적일 것 같습니다.

 

사용한 모듈 및 참고자료

언어는 파이썬을 사용했고, 데이터 가공을 위해 pandas 및 numpy를 사용했습니다. 이 두 모듈을 사용하기 위해 파이썬을 사용했다고 해도 될 것 같습니다.

red-black tree, prim 알고리즘, DFS의 코드는 https://www.geeksforgeeks.org/ 사이트에서 가져와 변형해 사용했습니다. 아이디어를 정리하기 위해 참고한 특허 문서가 있으므로 참고 바랍니다.