[TIL]20220531

CS 스터디

 

챕터22 :10 개 도시를 최단거리로 여행하는 법

P-NP 문제는 어떤 문제가 주어졌을 때 어렵다, 쉽다를 결정하는 기준점  을 제시한다.

P - NP문제는 수학계의 최대 난제인 7대 밀레니엄 문제 중 하나이다. P=NP를 증명하거나, P!=NP를 증명하게 되면, 약 12억의 상금과 튜링상 수상 및 모든 컴퓨터과학 업계를 뒤흔들 수 있다.

P

• 어떤 문제가 주어졌을 때 다항식으로 표현되어 polynomical time 즉, 다항 시간내에 해결 가능한 알고리즘을 의미하며 알고리즘의 복잡도가 O(nk)로 표현되는 문제를 'P'라 한다. 문제를 푸는데 걸리는 시간이 다항식으로 표현가능한 문제 (O(n^2), O(n^3)같이 O(n^k), O(n*log(n)). 복잡도 O(n^k) 이하를 가지는 경우 같은 복잡도 내에 모든 해를 구한다. ex) 정렬문제*

NP

• 어떤 문제가 주어졌을 때 다항식으로 표현될 수 있는지의 여부가 결정되지 않은 문제들을 'NP(Non-deterministic polynomial)'라 한다. 문제를 푸는건 어렵지만 답을 확인하는 시간이 다항식으로 표현 가능한 문제입니다 (그래서 검산이 가능해야 NP문제입니다)

NP−Hard

• “모든” NP 문제를 다항 시간 내에  어떤 문제 A로 환원할 수 있다면, 그 A 문제를 NP-Hard 문제 라고 한다.예를들면 곱셈과 덧셈을 생각해보자“어렵다”라는 개념을 쉽게 이해하기 위해 다시 곱셈과 덧셈을 생각해보자. 상식적으로 생각하기엔 곱셈이 더 어려워 보이지만, 사실은 곱셈은 덧셈이 기반이 된다면 빠르게 할 수 있는 연산이다. 하지만 덧셈 그 자체에 대한 개념은 생각해내는거 자체가 굉장히 까다로운 것이다. 그래서 P-NP 개념에서는 덧셈을 더 “어렵다”고 정의하는 것이고, 환원은 쉬운 문제(곱셈)에서 어려운 문제(덧셈)으로 바꾼다는 개념이다.
• NP - hard 문제에는 NP에 속하는 문제(NP- Complete) 가 있고 속하지 않는 문제가 있다.
• 곱셈은 사실 덧셈만 알고 있어도 된다. 7 x 8 은, 7을 8번 더한 것과 같고, 4 x 4은 4를 4번 더한 것과 같다. 결국, 곱셈 문제는 덧셈 문제로 환원할 수 있다고 하는 것이다. 그래서 결국 덧셈 문제는 곱셈 문제보다는 “어렵다”라고 정의하는 것이고, 덧셈 문제를 해결할 수 있다면 곱셈 문제도 당연히 해결할 수 있다. 다시 NP-난해의 설명으로 돌아가면, 이 세상에 있는 모든 NP문제를 다항 시간내에 어떤 문제로 환원할 수 있다면, 그 문제를 NP- Hard 라고 하는 것이고, NP-난해 문제는 이 세상에 있는 모든 NP 문제보다 “어렵다”라고 정의할 수 있는 것이다.
• 만약 P-NP 문제가 P=NP로 풀린다면 P=NP=NP-Complete이므로 P와 NP는 NP-Hard의 부분집합이 되고, P≠NP인 경우는 P와 NP-Hard는 서로소가 된다.
• 적어도 모든 NP 문제만큼은 어려운 문제들의 집합이다.

NP−Complete

• NP이면서 동시에 NP-Hard 에 속한다면 그 문제는 'NP-Complete'라 한다. (전수조사가 답)
• ex) 해밀턴 경로 문제, 외판원 문제, 충족 가능석 문제, 그래프 색칠문제 시간표 짜기 문제

P=NP문제임이 밝혀진다면 NP문제를 쉽거나효율적으로 풀 방법이 존재함을 말한다.

찾기, 방문 판매 알고리즘 등을 포함한 모든 문제들이 전부 P 문제로서 풀릴 수 있다는 의미이다

반대로 P≠NP 가 증명 되면, 수 많은 NP 문제들이 P 문제로 환원될 수 없음이 증명되었으니 더 쉬운 방법(P 문제로 환원할 방법)을 찾으려 더 이상 애쓸 필요가 없다는 것이다.

---

알고리즘 

최단 경로 (1)

다익스트라 알고리즘 

다이나믹 프로그래밍을 활용한 대표적인 최단경로 탐색 알고리즘

특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.(음의 간선은 포함할 수 없다.)

현실세계의 지도 등에 매우 많이 쓰이고 있다.

 

다음과 같은 두가지 방법으로 구현할수 있다. 

INF = int(1e9)


def dijkstra_naive(graph, start):
    def get_smallest_node():
        min_value = INF
        idx = 0
        for i in range(1, N):
            if dist[i] < min_value and not visited[i]:
                min_value = dist[i]
                idx = i
        return idx

    N = len(graph)
    visited = [False] * N
    dist = [INF] * N

    visited[start] = True
    dist[start] = 0

    for adj, d in graph[start]:
        dist[adj] = d

    # N개의 노드 중 첫 노드는 이미 방문했으므로,
    # N-1번 수행하면 된다.
    for _ in range(N - 1):
        # 가장 가깝고 방문 안한 녀석을 고르고,
        cur = get_smallest_node()
        visited[cur] = True
        # 최단거리를 비교, 수정한다.
        for adj, d in graph[cur]:
            cost = dist[cur] + d
            if cost < dist[adj]:
                dist[adj] = cost

    return dist

 

import heapq

INF = int(1e9)


def dijkstra_pq(graph, start):
    N = len(graph)
    dist = [INF] * N

    q = []
    # 튜플일 경우 0번째 요소 기준으로 최소 힙 구조.
    # 첫 번째 방문 누적 비용은 0이다.
    heapq.heappush(q, (0, start))
    dist[start] = 0

    while q:
        # 누적 비용이 가장 작은 녀석을 꺼낸다.
        acc, cur = heapq.heappop(q)

        # 이미 답이 될 가망이 없다.
        if dist[cur] < acc:
            continue

        # 인접 노드를 차례대로 살펴보며 거리를 업데이트한다.
        for adj, d in graph[cur]:
            cost = acc + d
            if cost < dist[adj]:
                dist[adj] = cost
                heapq.heappush(q, (cost, adj))

    return dist

---

알고리즘 문제

 

화성탐사 - 이코테

숨바꼭질 - 이코테

미래도시 -이코테

네트워크 딜레이 타임

K 경유지 내 가장 저렴한 항공권