// Links to the libraries needed
Jump to:
Navigation
About Project Study Blog

[알고리즘 최적화] TSP 알고리즘 시간 복잡도를 반의반의반의반의….반의 반으로 줄여??(과장 조금 보태서)

카테고리:    tag #
2024년 10월 20일

문제 상황: [프로젝트 최적화 및 알고리즘] 추천 여행지 경로 최적화 문제

이전 포스트: [API 호출 최적화] API 호출을 420번에서 14번으로?

이제 각 위치에 대한 거리값을 2차원 배열로 만들었으니 이에 대한 최단 경로를 구해주겠습니다!

현재 상황

  • 만약 AI 서버에서 3일치의 결과를 뽑는다면 클러스터 내에서 가장 만족스러운 결과를 1일 당 5개의 장소 씩 총 15개를 뽑아서 주고 있습니다.
  • 클러스터에 만족하는 결과가 원하는 개수만큼 안나올 수도 있기 때문에 클러스터를 넓게 지정했기 때문에 결과가 너무 넓게 나옴
  • 그런데 이건 AI 서버에서 조정할 문제라서 주어진 결과로 최적화해야 합니다.
  • 어쨌든 최단경로를 찾아야 합니다!

적용할 알고리즘 찾기

  • 그래서 이에 대해 적용할 알고리즘을 찾아보았습니다!
  • 저희 서비스는 목적지가 따로 없고 출발지(숙소 또는 사용자가 설정한 출발지)에서 모든 노드를 돌아 출발지로 다시 돌아와야 하기 때문에 TSP로 모델링하여 알고리즘을 적용시켜보기로 했습니다!
  • 그렇다면 TSP 문제를 해결할 수 있는 알고리즘을 알아보겠습니다!

TSP 문제를 해결할 수 있는 알고리즘

1. 브루트 포스로 풀기

  • 가능한 모든 경로를 계산하여 그중 최단 경로를 선택하는 방법입니다.
  • 다음의 장단점과 고려 사항을 가지고 있습니다!
  • 장점: 모든 경우를 탐색하므로 최적해를 보장한다
  • 단점: 시간 복잡도가 O(n!)로, 노드 수가 증가할수록 계산량이 기하급수적으로 늘어난다!
  • 고려 사항: 시간이 상당히 오래 걸리니 노드 수가 매우 적거나 최최최최최후에만 쓰자!

2. 분기 한정법(Branch-and-Bound)으로 풀기

  • 분기와 한정을 나누어 탐색 공간을 효율적으로 줄이는 방법입니다.
  • 분기(Branching): 전체 해 공간을 작은 부분 문제로 나누어 탐색합니다.
  • 한정(Bounding): 각 부분 문제에 대해 최적해의 상한과 하한을 계산하여, 더 이상 탐색할 필요가 없는 부분 문제를 제외(가지치기)합니다.
  • 다음의 장단점과 고려 사항을 가지고 있습니다!
  • 장점
    • 효율성 향상: 불필요한 경로를 가지치기하여 계산량을 줄임
    • 최적해 보장: 탐색 공간을 줄이지만 최적의 해를 찾을 수 있음
  • 단점: 가지치기를 통해 실제로는 훨씬 더 좋은 성능을 가지지만 최악의 상황에 O(n!)의 시간복잡도를 가짐
  • 고려 사항
    • 효율적인 가지치기를 위해 좋은 하한과 상한 계산 방법이 필요

3. Dynamic Programming + 비트마스킹으로 풀기

  • dp를 이용하여 중복 계산을 최적화합니다.
  • 비트마스킹을 이용하여 방문 상태를 표시하여 각 정점마다 다른 모든 정점들의 방문상태를 표시해줄 때 메모리 사용을 줄입니다.
  • 다음의 장단점과 고려 사항을 가지고 있습니다!
  • 장점
    • 효율성 향상
    • 최적해 보장: 동적 계획법을 통해 최적의 해를 찾음
  • 단점
    • 시간 복잡도: O(n² * 2^n)으로, 여전히 노드 수가 많아지면 수가 많이 커짐..
    • 메모리 사용량: 상태 공간이 증가하여 공간 복잡도가 증가..
  • 고려 사항
    • 메모리 최적화
      • 비트마스킹을 통해 방문 상태를 이진수로 표현하여 메모리 사용을 줄이자
      • 필요 없는 상태는 저장하지 않고 필요할 때 계산하는 방법을 사용하자
    • 병렬화 가능성
      • 동적 계획법의 특성을 활용하여 일부 계산을 병렬화할 수 있음
      • 하지만 구현 복잡도가 급격하게 증가하기 때문에 일단 보류..

Google Maps Directions API의 Waypoint 최적화 기능 사용

이제 알고리즘을 사용하는 것보다 훨씬 간편한 Google Maps Directions API를 사용하여 최적 경로를 구하는 방법이 있다고 합니다.

  • 다음의 장단점과 고려 사항을 가지고 있다고 합니다!
  • 장점
    • 간편함: Google API가 최적 경로를 제공하기 때문에 복잡한 알고리즘을 구현할 필요가 없고 위에서 각 장소 간 거리를 구하는 로직을 거칠 필요가 없다.
    • 실제 교통 정보 반영: Google Maps는 실시간 교통 상황, 거리, 이동 시간을 고려해 최적화할 수 있다.
  • 단점
    • 제한된 경유지: Google API는 최대 25개의 경유지로 제한된다. → 1일 당 추천 여행지 갯수가 5개로 정해져있는데 출발지와 도착지를 함께 넣는다고 하면 사실상 4일치의 여행지밖에 넣을 수 없다.
    • 비용 문제: 사용량에 따라 비용이 발생하기 때문에 다중 경유지를 포함한 요청은 추가 비용이 들 수 있다.
    • TSP 문제에 대한 근사 해결: API가 제공하는 최적화는 엄밀한 TSP 최적해를 보장하지는 않는다.
  • 고려 사항:
    • 비용: 많은 경유지를 처리하거나 잦은 API 호출이 필요한 경우, 사용량을 고려한 비용 관리가 필요하다.
    • 제한된 Waypoint: 25개 이상의 경유지가 있는 경우, API만으로 해결할 수 없으므로 다른 알고리즘을 혼합하는 방법을 고려해야 한다.
    • 진짜 사용할 수 있는지 확인해야 한다…

| | Google Maps Directions API의 Waypoint 최적화 기능 사용 | dp + 비트마스킹 알고리즘 | | — | — | — | | 장점 | • 간편함: Google API가 최적 경로를 제공하기 때문에 복잡한 알고리즘을 구현할 필요가 없고 위에서 각 장소 간 거리를 구하는 로직을 거칠 필요가 없다. • 실제 교통 정보 반영: Google Maps는 실시간 교통 상황, 거리, 이동 시간을 고려해 최적화할 수 있다. | • 최적해 보장: 엄밀한 TSP 문제 해결을 보장하며, 모든 경로에 대한 최단 경로를 찾음 • 메모이제이션을 통한 효율성: 중복된 계산을 방지하여 연산을 크게 줄일 수 있음 | | 단점 | • 제한된 경유지: Google API는 최대 25개의 경유지로 제한된다. → 1일 당 추천 여행지 갯수가 5개로 정해져있는데 출발지와 도착지를 함께 넣는다고 하면 사실상 4일치의 여행지밖에 넣을 수 없음 • 비용 문제: 사용량에 따라 비용이 발생하기 때문에 다중 경유지를 포함한 요청은 추가 비용이 들 수 있다. • TSP 문제에 대한 근사 해결: API가 제공하는 최적화는 엄밀한 TSP 최적해를 보장하지는 않는다. | • 시간 복잡도: O(n² * 2^n)으로 노드 수가 많아질수록 계산량이 급증함. 20개 이상의 노드가 있는 경우 계산 속도가 급격히 느려짐 • 메모리 사용량: 노드 수에 따라 메모리 사용량이 기하급수적으로 증가함 | | 고려 사항 | • 제한된 Waypoint: 25개 이상의 경유지가 있는 경우, API만으로 해결할 수 없으므로 다른 알고리즘을 혼합하는 방법을 고려해야 한다. • 비용: 많은 경유지를 처리하거나 잦은 API 호출이 필요한 경우, 사용량을 고려한 비용 관리가 필요하다. | • 노드 수 제한: 노드 수가 많을 경우 계산이 매우 느려질 수 있으므로, 최대 20~25개 정도의 노드에 대해 이 알고리즘을 사용하는 것이 적합 • 메모리 효율성: 메모리 최적화가 필요한 경우, 경로 정보를 저장하는 방법에 대한 개선이 필요 |

그러면 이제 직접 알고리즘과 API를 적용해보며 비교해보겠습니다.

Google Maps Directions API 사용해보기

우선 비교적 간단한 API를 사용한 결과를 먼저 받아보려합니다!

아래와 같이 테스트해봤습니다.

String url = "https://maps.googleapis.com/maps/api/directions/json?"
                + "destination=" + places.get(places.size() - 1).getLatitude() + "," + places.get(places.size() - 1).getLongitude()
                + "&origin=" + places.get(0).getLatitude() + "," + places.get(0).getLongitude()
                + "&waypoints=optimize:true|" + waypoints
                + "&key=" + googleApiKey;
        log.info(url);
        Map<String, Object> response = webClient.get()
                .uri(url)
                .retrieve()
                .bodyToMono(new ParameterizedTypeReference<Map<String, Object>>() {})
                .block();
        log.info(response.toString());

2024-09-23T10:44:39.051+09:00  INFO 13714 --- [bami] [nio-8080-exec-2] c.e.b.s.service.AIRecommendationService  : https://maps.googleapis.com/maps/api/directions/json?destination=37.28728,127.02574&origin=37.566826,126.97865&waypoints=optimize:true|37.566826,126.97865|37.56704,126.87561|37.433903,127.0187|37.66463,126.741806|37.55588,126.97159|38.13125,127.0171|37.294544,127.19163|37.510643,127.09972|37.498234,126.8671|37.55483,126.97925|37.337067,127.29683|37.55895,126.802864|38.011604,127.06411|37.43658,126.4573|37.574272,126.95607|37.580826,127.003975|37.579536,126.9844|37.66627,126.74749|37.40722,126.634895|37.293095,127.20282|37.28728,127.02574&key=secret
2024-09-23T10:44:39.307+09:00  INFO 13714 --- [bami] [nio-8080-exec-2] c.e.b.s.service.AIRecommendationService  : {routes=[], status=ZERO_RESULTS}

ZERO_RESULT 에러가 발생했습니다!

요청의 문제인 것 같아 URL을 이용하여 POSTMAN으로 테스트해보려합니다!

POSTMAN으로 URL 테스트

  • ZERO_RESULTS 에러 발생

image

API URL이 잘못되었나 싶어서 Google Maps Directions API 공식 문서에 예제를 위도, 경도 데이터로 바꿔서 URL을 만들고 테스트해보겠습니다!

  • 예제 URL
https://maps.googleapis.com/maps/api/directions/json?destination=Los%20Angeles%2C%20CA&origin=Chicago%2C%20IL&waypoints=Joplin%2C%20MO%7COklahoma%20City%2C%20OK&key=secret
  • 바뀐 URL
https://maps.googleapis.com/maps/api/directions/json?origin=41.8781,-87.6298&destination=34.0522,-118.2437&waypoints=37.0842,-94.5133|35.4676,-97.5164&key=YOUR_API_KEY
  • 잘 나오는 결과

image

예제의 주소는 잘 나와서 예제의 URL과 비슷하게 위도, 경도 데이터를 넣어서 테스트해보겠습니다!

  • 내 URL
https://maps.googleapis.com/maps/api/directions/json?origin=37.566826,126.97865&destination=37.28728,127.02574&key=secret
  • 결과: ZERO_RESULT

image

이정도 되면 아무리 봐도 URL의 문제는 아닌 것 같아서 다른 문제점을 찾아보기로 했습니다!

한국에서 구글 맵 자동차 길찾기 미지원

구글 맵에 똑같이 위도, 경도를 넣어 길찾기를 해봤습니다.

그런데 자동차 이용, 도보 이용 경로 결과가 안나오는 확인할 수 있었습니다,,

image

위와 같은 결과의 원인을 알아보니 한국 정부에서는 국가 안보를 이유로 국내 지도 데이터를 구글에 제공하고 있지 않아서 자동차 길찾기나 도보 길찾기는 안된다고 합니다…

그래서 Mode를 transit으로 바꿔봤습니다!

image

하지만 transit모드는 두 개의 요소만 받는다는 메시지가..

waypoint를 1개로 줄여도 똑같은 결과를 반환하는 것을 보니 waypoint를 못받는다는 얘기를 하는 듯 합니다..

돌고돌아 알고리즘으로 가보겠습니다..

알고리즘 적용해보기

이들의 시간 복잡도를 계산했을 때 dp 알고리즘을 사용하는 것이 가장 효율적이라는 것을 알지만 그래도 각 시간을 측정해보고 소요 시간이 얼마나 차이나는지 확인해보기 위해 가장 시간복잡도가 높은 브루트포스와 낮은 dp를 사용하여 비교해보도록 하겠습니다.

우선 저는 파이썬으로 알고리즘을 구현하는 것이 가장 빠르게 테스트 코드를 짤 수 있는 방법이라 생각하여 테스트는 파이썬으로 하고 본 코드는 Java로 구현한 뒤 Spring에 적용시키도록 하겠습니다.

환경 세팅

우선 무작위 수로 2차원 배열을 만들어줍니다.

def generate_distance_matrix(n, seed=42):
    random.seed(seed)
    matrix = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            distance = random.randint(10, 100)
            matrix[i][j] = distance
            matrix[j][i] = distance
    return matrix

테스트는 3일의 여행 일정을 구한다고 생각하고 15개 + 출발지 1개로 16개의 노드를 넣어서 테스트해보겠습니다.

image

1. 브루트 포스로 풀기

우선 브루트 포스로 풀어보겠습니다.

def tsp_bruteforce(graph, start=0):
    vertices = list(range(len(graph)))
    vertices.remove(start)
    min_cost = float('inf')
    min_path = None

    for path in permutations(vertices):
        path = (start,) + path + (start,)
        cost = sum(graph[path[i]][path[i + 1]] for i in range(len(path) - 1))
        if cost < min_cost:
            min_cost = cost
            min_path = path

    return min_cost, min_path

단순히 모든 순열을 구해서 반복문을 돌리고 시작 위치에서 출발하여 다시 시작 위치로 돌아오는 순열에 대한 노드의 이동 값을 더하여 그에 대한 최소 거리값을 구해주는 코드입니다.

이에 대한 시간 복잡도는 16개의 노드에서 넣었을 때 출발지를 고정하면 순열을 생성하는 시간복잡도 O(n-1!) = O(15!), 각 순열에 대한 전체 경로 비용까지 고려하면 O(n*(n-1)!) = O(16!)가 되고 조 단위가 넘어가는 엄청난 숫자가 나오게 됩니다.

테스트

자, 그러면 브루트포스는 시간이 얼마나 소요되는지 확인해보겠습니다.

…라고 했지만 16을 넣어서 구하니 30분이 지나도 연산을 다 못하는 문제가 발생했습니다.

그래서 낮은 수부터 차근차근 구해보았습니다!

  • n = 11

image

  • n = 12

image

  • n = 13

image

(n=12일 때랑 n=13일 때랑 비용을 비교하면 왜 n=13일 때가 더 적냐!!라고 하신다면 테스트마다 거리 배열이 초기화되기 때문입니다..)

이 규칙대로 간다면 완전 선형적으로 증가하지는 않겠지만 n=14일 때 대충 5000초, n = 15일 때 60000초, n = 16일 때 70000초, 즉, 20시간 정도가 걸립니다!!

어마무시한 수가 나오니 완전 탐색은 패쓰..

2. dp와 비트마스킹을 이용하여 풀기

마지막으로 dp를 사용하는 풀이입니다.

TSP 문제를 해결할 때 가장 자주 보이고 보편적인 방법인 것 같습니다.

비트마스킹을 통해 메모리 사용을 최적화했다는 특징이 있습니다. 비트마스킹은 조금 있다가 추가 최적화 포인트를 볼 때 설명하겠습니다.

def solve(mask, pos, graph, dp, path, n):
    # 모든 도시를 방문했으면 출발지로 돌아가는 비용과 경로 반환
    if mask == (1 << n) - 1:
        return graph[pos][0], [0]

    # 이미 계산한 경로가 있으면 dp 값 사용
    if (mask, pos) in dp:
        return dp[(mask, pos)], path[(mask, pos)]

    ans = float('inf')
    best_path = []

    # 다음 방문할 도시를 결정
    for city in range(n):
        if not mask & (1 << city):  # 아직 방문하지 않은 도시
            # 다음 도시 방문에 대한 비용과 경로 계산
            val, sub_path = solve(mask | (1 << city), city, graph, dp, path, n)
            total_cost = graph[pos][city] + val
            if total_cost < ans:
                ans = total_cost
                best_path = [city] + sub_path

    # 결과 저장 및 반환
    dp[(mask, pos)] = ans
    path[(mask, pos)] = best_path
    return ans, best_path

def tsp_dp(graph):
    n = len(graph)
    dp = {}
    path = {}

    final_cost, final_path = solve(1, 0, graph, dp, path, n)
    return final_cost, [0] + final_path

위 코드의 흐름은 다음과 같습니다.

  • solve 함수는 mask와 pos를 기준으로 현재 방문한 도시의 상태와 현재 위치를 인수로 받아 최소 비용을 계산합니다.
  • 모든 도시를 방문했으면 출발지로 돌아가는 비용을 반환합니다.
  • 이미 계산한 (mask, pos) 상태가 dp에 저장되어 있으면 이를 재사용하여 중복 계산을 방지합니다 (메모이제이션)
  • 도시를 방문할 때마다 다음 방문할 도시를 결정하고, 이 선택에 따른 최소 비용을 계산하여 dp에 저장합니다.

이 문제 해결의 특징은 재귀함수로 끝을 찍고 내려오면서 각각의 값들을 구한다는 특징이 있습니다.

또한 최적의 경로는 path에 저장된 정보를 통해 재귀적으로 역추적하여 구합니다.

테스트

자, 그러면 이 방법을 사용할 때는 얼마나 시간이 소요되는지 확인해보겠습니다.

n = 16으로 테스트하였습니다.

image

1.2초로 극단적으로 시간이 단축된 것을 확인할 수 있었습니다.

저는 자신이 생겨 4일차의 일정 즉, n=21일 때의 테스트도 진행해보았습니다.

image

100초면 완전 탐색에 비해 양호해보이지만 실제 서비스에서 사용할만한 성능은 아닌 것 같습니다!

Optimizer Point

기본적으로 TSP 문제는 Dynamic Programming을 사용하여 해결할 수 있습니다.

하지만 이 방법에는 여러 최적화 포인트가 있습니다.

✅dp 사용으로 중복 최적화 → 비트마스킹으로 공간 최적화 → 1번 노드가 출발지임을 고려한 공간 및 시간 최적화

1. 비트마스킹을 통한 Memorization (DP)

각 도시의 방문 처리를 하나의 비트로 표현하는 것입니다.

예를 들어, 도시가 4개인 경우 비트마스크 0110은 도시 1과 2를 방문했음을 나타냅니다.

그리고 dp라는 2차원 배열을 다음과 같은 규칙으로 Memoization합니다.

dp[현재 방문 중인 도시][비트마스킹] = 현재 방문 중인 도시에서 출발하여 방문 안 한 나머지 도시들을 전부 방문하여 0번 도시까지 갈 때 필요한 최솟값

그렇다면 배열이 다음과 같이 만들어집니다.

image

ex) dp[2][5(101)] = 0, 2번 도시를 방문했으며 현재 2번 도시에 있을 때, 2번에서 출발하여 남은 도시들을 방문하여 0번 도시까지 갈 때 필요한 최솟값입니다.

image

위와 같이 Memorization을 잘 하면 dp[3][11]의 값을 한 번 구한 후, 다음에 dp[3][11]의 값이 또 필요해도 굳이 다음을 계산할 필요가 없어지므로 시간복잡도를 최적화 할 수 있습니다.

2. 메모리 사용량이 안그래도 큰데 재귀를? 반복문 사용하자. ~= 헬드-카프 알고리즘

2-1. 재귀 사용

보통의 TSP를 해결하는 데 재귀를 많이 사용합니다.

재귀 함수의 사용은 다음과 같습니다.

비트마스킹이 모든 도시를 다 방문했다는 표시가 될 때까지 재귀를 들어갑니다.

  • 3개의 도시가 있는 경우의 dfs 예시
dp[0][001] -> dp[1][011] -> dp[2][111]
					 -> dp[2][101] -> dp[1][111]
  1. dp[0][001]의 값을 알기 위해 dp[1][011]과 dp[2][111]의 값을 구해야 합니다.
  2. dp[1][011]의 값을 구하기 위해 dp[2][111]의 값을 구해야 합니다.
  3. dp[2][111]의 비트마스킹이 111이기 때문에 재귀를 들어가지 않고 cycle이기 때문에 2번 도시에서 0번 도시로 가는 비용을 return합니다.
  4. dp[1][011]의 값은 ‘return 받은 dp[2][111]’ + ‘1번 도시에서 2번 도시로 가는 비용’ 이 되고 dp[1][011]을 return합니다.
  5. 같은 방법으로 dp[2][101]를 구해 return하고 dp[0][001] = Math.min(dp[1][011], dp[2][101]) 이 되고 그 값을 return합니다.

예시와 같이 비트마스킹이 전부 채워진 다음부터 비용을 더한 값을 계속 return하고 그 중 최솟값을 고르는 과정을 반복하는 것이다.

하지만 저는 안그래도 메모리를 많이 사용하는 방법인데 재귀를 사용하여 함수 호출 스택을 추가로 사용하면 메모리 사용량이 더 늘어날 것이라 생각하여 반복문을 사용하기로 했습니다.

2-2. 반복문 사용

제가 생각한 위 재귀함수의 문제점은 다음과 같습니다.

  • 함수 호출 스택에 의한 메모리 사용량 증가
  • 이에 따른 오버헤드 발생으로 실행 속도 감소

그래서 저는 반복문을 사용하기로 했습니다.

반복문은 구현이 조금 더 복잡한 대신 추가 메모리 사용이 없고 가독성 및 유지보수성이 좋다는 장점이 있다고 생각하였습니다.

제가 생각한 반복문의 흐름은 다음과 같습니다.

  1. 초기화:

시작 도시에서 다른 도시로 직접 이동하는 비용을 초기화합니다.

  • 예: dp[1 « 시작도시][시작도시] = 0
    1. dp 테이블 채우기:
  • 모든 방문 상태(mask) 반복
    • 모든 현재 도시(u) 반복
      • 방문하지 않은 모든 도시(v) 반복
        • 새로운 방문 상태 next_mask = mask (1 « v)를 계산합니다.
        • dp 값을 갱신합니다:

dp[next_mask][v] = min(dp[next_mask][v], dp[mask][u] + cost[u][v])

  • 부모 배열을 업데이트하여 경로를 추적할 수 있도록 합니다.
    1. 최소 비용 계산 및 경로 복원:

모든 도시를 방문한 상태에서 시작 도시로 돌아오는 비용을 포함하여 최소 비용을 찾습니다.

부모 배열을 사용하여 최적 경로를 복원합니다.

3. 어차피 출발 노드가 고정되어있는데? 2^n - 1개로 공간과 시간을 최적화하자.

저의 문제에서는 출발지가 고정되어 있습니다. 그리고 심지어 제가 구한 2차원 배열에는 0번째 인덱스에 출발지에 대한 정보를 추가해주고 있습니다.

그렇다면 출발지인 첫 번째 노드는 항상 방문 상태이고 방문 처리는 무의미하다고 생각하였습니다.

그리고 dp 배열에서 0010, 0100, 0110 등 0번 노드가 방문되지 않는 상태를 나타내는 비트마스크가 생깁니다.

이를 모두 해결하기 위해 생각한 방법은 출발 노드가 항상 방문 상태임을 염두에 두고 열 갯수를 2^(n-1)개로 두는 것입니다.

그렇다면 배열의 가로 크기가 절반으로 줄어들어 배열의 메모리 사용이 줄어들게 됩니다.

코드 성능 비교

우선 얼마나 최적화 되었는지 확인하기 위해 재귀 함수를 사용한 방법, 반복문을 사용한 방법, 0번 노드를 방문한다고 확정한 방법을 구현하여 성능을 비교해보려 합니다!

  • 시간 복잡도 측정 방법

시간 복잡도 측정 방법은 다음과 같이 해당 메소드가 실행되기 전과 실행된 후의 시간을 측정하고 end_time - start_time으로 계산하였습니다.

start_time = time.time()
result_recursive = tsp_recursive(distances)
end_time = time.time()

print(f"실행 시간: {end_time - start_time:.4f}초")
  • 공간 복잡도 측정 방법

공간 복잡도는 다음과 같은 방법으로 측정했습니다.

c=[[[1,2,3] for _ in range(10000)] for _ in range(500)]
sys.getsizeof(c)

다차원 배열 리스트는 내부 배열들의 주솟값만을 가지고 있습니다.

그래서 위와 같은 방식으로 측정한다면 가장 바깥쪽의 배열에서 사용하는 메모리 밖에 측정을 못하기 때문에 재귀와 반복문을 사용하여 list를 순회하며 각 리스트의 사이즈를 구해주고 이를 더해서 구하였습니다.

def get_size(obj, seen=None):
    """객체의 메모리 사용량을 재귀적으로 계산"""
    size = sys.getsizeof(obj)
    if seen is None:
        seen = set()
    obj_id = id(obj)
    if obj_id in seen:
        return 0
    seen.add(obj_id)
    if isinstance(obj, dict):
        size += sum([get_size(v, seen) for v in obj.values()])
        size += sum([get_size(k, seen) for k in obj.keys()])
    elif isinstance(obj, (list, tuple, set)):
        size += sum([get_size(i, seen) for i in obj])
    return size

1. dp + 비트 마스킹 - 재귀 함수

  • 코드

코드는 다음과 같습니다.

재귀를 타고타고 들어가서 가장 끝 재귀로 들어가고 이를 내려오면서 값을 더해줍니다.

dp 테이블은 현재 도시와 방문 처리를 위한 비트마스킹으로 구성되어 있고 중복을 제거하기 위해 사용합니다.

함수의 흐름은 다음과 같습니다.

  1. 모든 도시 방문 확인
    • 모든 도시의 방문이 확인되면 그 때부터 다시 재귀를 내려가면서 값을 전해줌
  2. 메모이제이션 확인
    • 이미 계산되었는지 확인
  3. 다음 방문할 도시 탐색
  4. 비트 연산을 통해 방문을 확인하고 해당 도시를 방문하지 않았다면 재귀호출
  5. 새로운 값이 기존 값보다 작다면 갱신
  6. 메모이제이션 저장
def tsp_recursive(graph):
    n = len(graph)
    dp = {}
    path = {}

    def solve(mask, pos):
        if mask == (1 << n) - 1:
            return graph[pos][0], [0]

        if (mask, pos) in dp:
            return dp[(mask, pos)], path[(mask, pos)]

        ans = float('inf')
        best_path = []

        for city in range(n):
            if not mask & (1 << city):
                val, sub_path = solve(mask | (1 << city), city)
                total_cost = graph[pos][city] + val
                if total_cost < ans:
                    ans = total_cost
                    best_path = [city] + sub_path

        dp[(mask, pos)] = ans
        path[(mask, pos)] = best_path
        return ans, best_path

    final_cost, final_path = solve(1, 0)

    mem_usage = get_size(dp) + get_size(path)

    return {
        'cost': final_cost,
        'path': [0] + final_path,
        'memory': mem_usage,
    }

2. dp + 비트 마스킹 - 반복문

  • 코드

코드는 다음과 같습니다.

모든 방문 상태에 대해 반복하고 그 안에서 모든 도시에 대해 이중으로 반복합니다.

반복을 하며 아직 도달하지 않은 상태나 방문 처리를 확인하고 건너 뛰어줍니다.

새로운 방문 상태와 비용을 계산한 뒤 기존 비용보다 적다면 갱신해줍니다.

def tsp_iterative(graph):
    n = len(graph)
    size = 1 << n
    dp = [[float('inf')] * n for _ in range(size)]
    parent = [[-1] * n for _ in range(size)]
    dp[1][0] = 0  # 시작 도시 포함

    for mask in range(size):
        for u in range(n):
            if dp[mask][u] == float('inf'):
                continue
            for v in range(n):
                if mask & (1 << v):
                    continue
                next_mask = mask | (1 << v)
                cost = dp[mask][u] + graph[u][v]
                if dp[next_mask][v] > cost:
                    dp[next_mask][v] = cost
                    parent[next_mask][v] = u

    min_cost = float('inf')
    last = -1
    full_mask = size - 1
    for u in range(n):
        cost = dp[full_mask][u] + graph[u][0]
        if cost < min_cost:
            min_cost = cost
            last = u

    # 경로 복원
    path = []
    mask = full_mask
    while last != -1:
        path.append(last)
        temp = parent[mask][last]
        mask ^= (1 << last)
        last = temp
    path.append(0)
    path.reverse()

    mem_usage = get_size(dp) + get_size(parent)

    return {
        'cost': min_cost,
        'path': path,
        'memory': mem_usage,
    }

3. dp + 비트 마스킹 - 반복문 + 공간 및 시간 최적화

  • 코드

이전 코드에서 달라진 것은 다음과 같습니다.

  • 비트 마스크의 크기가 -1!
  • 이로 인해 DP 테이블의 크기가 절반으로!
  • 내부 반복문의 범위도 -1!

⇒ 메모리 사용량이 절반으로! 시간복잡도도 감소!(기대효과)

def tsp_optimized(graph):
    n = len(graph)
    size = 1 << (n - 1)  # 0번 노드를 제외한 나머지 노드들에 대한 비트마스크 크기
    dp = [[float('inf')] * n for _ in range(size)]
    parent = [[-1] * n for _ in range(size)]

    dp[0][0] = 0

    for mask in range(size):
        for u in range(n):
            if dp[mask][u] == float('inf'):
                continue
            for v in range(1, n):
                if mask & (1 << (v - 1)):
                    continue
                next_mask = mask | (1 << (v - 1))
                cost = dp[mask][u] + graph[u][v]
                if dp[next_mask][v] > cost:
                    dp[next_mask][v] = cost
                    parent[next_mask][v] = u

    min_cost = float('inf')
    last = -1
    full_mask = size - 1
    for u in range(1, n):
        cost = dp[full_mask][u] + graph[u][0]
        if cost < min_cost:
            min_cost = cost
            last = u

    # 경로 복원
    path = []
    mask = full_mask
    while last != -1:
        path.append(last)
        temp = parent[mask][last]
        if last != 0:
            mask ^= (1 << (last - 1))
        last = temp
    path.append(0)  # 시작 도시 추가
    path.reverse()

    mem_usage = get_size(dp) + get_size(parent)

    return {
        'cost': min_cost,
        'path': path,
        'memory': mem_usage,
    }

비교 결과

비교는 이전 N = 21로 하였을 때 재귀 함수를 사용한 코드가 500초가 걸렸었기 때문에 N = 16으로 진행하였습니다.

image

  • 재귀 사용 → 반복문 사용

메모리 사용량이 3.3배 정도, 시간 복잡도가 2배 정도 최적화가 되었습니다.

  • 반복문 사용 → 출발지 고정 최적화

메모리 사용량이 2배 정도, 시간 복잡도가 2배 정도 최적화가 되었습니다.

  • 재귀 사용 → 출발지 고정 최적화

최종적으로 메모리 사용량이 6.6배 정도, 시간복잡도가 4배 정도 최적화가 되었습니다!

그러면 이를 자바로 구현하여 결과를 확인해보겠습니다!!

자바로 구현하여 적용

코드 구현

public List<Integer> computeTspOptimized(int[][] graph) {
    int n = graph.length;
    int size = 1 << (n - 1);
    int[][] dp = new int[size][n];
    int[][] parent = new int[size][n];

    for (int i = 0; i < size; i++) {
        Arrays.fill(dp[i], Integer.MAX_VALUE);
        Arrays.fill(parent[i], -1);
    }

    dp[0][0] = 0;

    for (int mask = 0; mask < size; mask++) {
        for (int u = 0; u < n; u++) {
            if (dp[mask][u] == Integer.MAX_VALUE) {
                continue;
            }
            for (int v = 1; v < n; v++) {
                if ((mask & (1 << (v - 1))) != 0) {
                    continue;
                }
                int nextMask = mask | (1 << (v - 1));
                int cost = dp[mask][u] + graph[u][v];
                if (dp[nextMask][v] > cost) {
                    dp[nextMask][v] = cost;
                    parent[nextMask][v] = u;
                }
            }
        }
    }

    int minCost = Integer.MAX_VALUE;
    int last = -1;
    int fullMask = size - 1;
    for (int u = 1; u < n; u++) {
        int cost = dp[fullMask][u] + graph[u][0];
        if (cost < minCost) {
            minCost = cost;
            last = u;
        }
    }

    List<Integer> path = new ArrayList<>();
    int mask = fullMask;
    while (last != -1) {
        path.add(last);
        int temp = parent[mask][last];
        if (last != 0) {
            mask ^= (1 << (last - 1));
        }
        last = temp;
    }
    Collections.reverse(path);

    log.info(String.valueOf(minCost));
    return path;
}

전체 결과

image

API 호출에 34초, 알고리즘 사용에 0.02초가 소요된 것을 확인할 수 있습니다.

확실히 자바가 파이썬보다 빨라서 0.6초가 걸리던 파이썬보다 훨씬 성능이 좋게 나온 것 같습니다!

이렇게 비교하면 안되지만 브루트 포스가 대략 70000초가 걸리던 것을 생각해보면 아주 격세지감입니다!

시간 최적화를 정리해보면 다음과 같습니다.

여행지 노드 = 15개 기준

  • 브루트포스: 70000초
  • dp + 재귀: 2초
  • dp + 반복문: 1초
  • dp + 반복문 + 출발지 최적화: 0.6초 (자바 기준 0.02초)

이렇게 되면 처음의 API 호출과 알고리즘 사용보다 소요 시간을 조금(많이 엄청)의 과장을 보태서 반의반의반의…반의 반을 줄인 것 같습니다.

실제 알고리즘을 프로젝트에 적용해본 것 자체가 좋은 경험이었던 것 같습니다!!

혹시나 여기까지 읽어주신 분이 있다면 감사합니다!

<맨 위로>

© 2024. All rights reserved.

김민제의 블로그