20220224 APS응용 최단경로, dijkstra, 문자열패턴매칭

최단 경로

• 최단 경로 정의
  • 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로
• 하나의 시작 정점에서 끝 정점까지의 최단 경로
  • 다익스트라(dijkstra) 알고리즘
    • 음의 가중치를 허용하지 않음
  • 벨만-포드(Bellman-Ford) 알고리즘
    • 음의 가중치 허용
• 모든 정점들에 대한 최단 경로
  • 플로이드-워샬(Floyd-Warshall) 알고리즘

Dijkstra 알고리즘

• 시작 정점에서 다른 모든 정점으로의 최단경로를 구하는 알고리즘
• 시작 정점에서의 거리가 최소인 정점을 선택해가면서 최단 경로를 구하는 방식

S : Start Vertex, A : adjacent matrix, D : Distance from start vertex
V : Vertices, U : Selcted Vertices
Dijkstra(s, A, D)
	U = {s};
	for whole Vertex v
		D[v] = A[s][v]
	while U!=V
		select w (minimum D[w])
		U = U union {w}
		for not selected and adjacent with w
			D[v] = min(d[v], d[w]+a[w][v])

문자열 패턴 매칭

• 라빈-카프 알고리즘
  • 문자열 검색을 위해 해시 값 함수 비용
  • 최악의 시간 복잡도는 O(MN), 평균적으로는 선형에 가까움
  • 새로 추가되는 문자와 그 전에 읽었던 값을 이용
  • 새로 추가되는 값을 추가 앞에 있던 값을 버림
• 보이어-무어 알고리즘
  • 오른쪽에서 왼쪽으로 비교(뒤에서 앞으로 비교)
  • 오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 내에 존재하지 않는 경우, Y의 길이만큼 옮김
  • 내부에 패턴이 존재하면 그 자리로 비교할 문자 위치를 이동시킴
  • skip 배열을 생성, skip 배열은 길이 - 각 문자가 처음으로 존재하는 위치 (length-위치)
• KMP 알고리즘
  • 불일치가 발생한 텍스트 문자열의 앞 부분에 어떤 문자가 있는지 알고 있으므로, 불일치가 발생한 앞 부분에 대해 다시 비교하지 않고 매칭을 수행
  • 패턴을 이용하여 부분일치 테이블 배열 작성
    • 매칭이 실패했을 때 패턴 포인터가 돌아갈 곳을 계산