[알고리즘] Traveling Salesman Problem

Traveling Salesman Problem은 NP 알고리즘 중 하나로 최적의 경로를 찾기 위해서는 2n의 시간이 필요합니다 따라서 최적의 해가 아닌 approximate(근사해)를 통해 접근하도록 한다 1. Traveling Salesman Problem (TSP) 여행자가 임의의 한 도시에서 출발하여 다른 모든 도시를 1번씩만 방문하고 다시 출발한 도시로 돌아오는 여행 경로의 길이를 최소화하는 문제이다 A에서 B까지의 경로는 B에서 A까지의 경로가 같다는 대칭성 A에서 B로 가는 거리는 A에서 C를 경유하여 B로 가는 거리보다 짧다는 삼각 부등식의 특성 2. 문제 해결을 위한 아이디어 주어진 여행 장소를 MST(최소 신장 트리)로 나타내어 모든 점을 연결한다 TSP를 만들기 위해 MST의 경로를 ..

• format_list_bulleted Computer Science/Data Structure & Algorithm
• · 2023. 12. 2.
• textsms

[알고리즘] Kruskal & Prim Algorithm in Python

Kruskal & Prim Algorithm을 Python으로 구현해보고 해당 알고리즘에 대해 분석해보자 Kruskal Algorithm 그래프 이론에서 사용되는 그래프 최소 신장 트리 (Minimum Spanning Tree,MST)를 찾는 알고리즘 중 하나 그래프의 모든 정점을 연결하면서 가중치가 작은 간선들로 이루어진 트리를 구성 간선의 가중치 기반 선택 사이클 방지 그리디 알고리즘 그래프의 모든 간선을 가중치 순으로 정렬 정렬된 간선 목록을 처음부터 순회하면서 사이클을 형성하지 않는 간선 선택 선택한 간선을 트리에 추가 > 해당 알고리즘을 통해 MST를 리턴 G = { 'vertices' : [], 'edges': [] } parent = dict() rank = dict() def initial..

• format_list_bulleted Computer Science/Data Structure & Algorithm
• · 2023. 10. 11.
• textsms