NAIAHD

그래프 이론

그래프 : 

그래프 라고 하면 막대그래프나 파이 그래프 등 표 형식의 데이터를 그림으로 나타낸 것을 연상하는 분을 많을 겁니다. 

그러니 여기에서 말하는 그래프는 점과 선을 연결한 것을 의미합니다. 

점을 꼭지점, 정점 Vertext, 노드 node라고 하면 , 선을 변 또는 간선 Edge이라고 합니다. 

연결 그래프 : Connected Grapah : 모든 정점 사이를 연결한 (경로가 존재하는)그래프

비연결 그래프:

고립 정점 Isolated vertex: 어떤 정점도 연결되지 않은 정점

평행 변 Parallel edge: 그래프에서 정점 2개가 2개 이상의 변으로 연결되는 변 

양 끝이 같은 변 self-loop: 1개의 정점에 시작과 끝이 연결된 변이 존재하면 

무향 그래프:

유향 그래프: Directed Graph :

그래프의 변에 방향이 존재하면 

특히 어떤 정점에서 출발 한 후 해당 정점에 돌아오는 경로가 하나인 그래프는 유항 비순환 그래프 directed acylic graph, DAG

무향 그래프 : Undirected graph 

변에 방향이 존재하지 않는 그래프는 무향 그래프 

가중 그래프 Weighted Graph : 유향 그래프 중 가중치 정보가 추가된 그래프는 

변에 가중치 숫자를 적어 가중치를 표현합니다. 

변에 숫자를 적는 것 외에 선의 굵기로 가중치를 나타낼 수 도 있다. 

간선 가중 그래프 : 가중치는 정점에도 적을 수 있으므로 변에 가중치를 나타내면 간선 가중 그래프 Edge-weighted Graph

정점 가중 그래프 : Vertex-Weighted Graph: 정점에 가중치를 나타내면

그래프의 행렬 표현 :

인접 행렬 Adjacency matrix: 정점 사이의 관계를 나타내는 행렬

근접 행렬 incidence matrix: 정점과 변의 관계를 나타내는 행렬

20211121

트리 구조 그래프 :

그래프에 있는 여러 개 정점에서 출발점이 되는 정점으로 돌아가는 경로가 유일하며, 출발점이 되는 정점이 막다른 정점(더는 새로운 변을 통해 이동할 수 없는 정점)인 그래프를 트리 구조라고 합니다. 

출발점이 있는 정점은 루트Root(뿌리)라고 합니다. 

20211122

그래프 탐색과 최적화

탐색 트리 구축: 

이진 탐색 트리 

깊이 우선 탐색 Depth-first search DFS: 루트 노드에 연결된 경로 중 하나를 선택해 막다른 노드에 도착할 때 까지 일단 탐색한 후 , 다시 바로 앞 노드로 이동해 다음 막다른 노드까지 탐색을 반복합니다. 

너비 우선 탐색 Breath-first search BFS:루트 노드와 연결된 노드를 모두 탐색한 다음 바로 다음에 깊이의 노드들을 전부 탐색하는 과정을 반복합니다. 

20211123

탐색 트리의 탐색에 필요한 목록:

1. 탐색 대상 노드와 연결된 주변 노드를 포함하는 탐색 노드의 목록 : 오픈 리스트

2. 탐색을 종료한 노드의 목록 : 클로즈드 리스트 , 클로즈드 리스트에 도달 목표 노드가 포함되면 탐색을 종료합니다. 

깊이 우선 탐색은 노드를 오픈 리스트의 맨 위에 추가해 첫번째 노드부터 차례대로 탐색합니다. 

LIFO

FIFO

20211125
동적계획법:Dynamic Programming

출처 : 처음 배우는 인공지능