9장. 프로덕션에서 경로 찾기
이 작품은 AI를 사용하여 번역되었습니다. 여러분의 피드백과 의견을 환영합니다: translation-feedback@oreilly.com
흔히 경로에 대해 가장 먼저 생각하는 개념은 시작부터 끝까지 얼마나 많은 정거장을 거쳐야 하는가입니다. 이것이 8장의 주제였습니다.
그래프를 통해 경로로 작업할 때 다음 개념은 거리의 개념을 발전시키는 것입니다. 이를 위해 경로의 단계에 일종의 가중치 또는 비용을 추가합니다. 이러한 유형의 문제를 최소 비용 경로 또는 최단 가중치 경로라고 합니다.
최단 가중치 경로는 컴퓨터 과학과 수학에서 매우 인기 있는 최적화 문제입니다. 이러한 유형의 문제는 최소화를 위해 두 개 이상의 정보 소스를 비용 지표로 결합하기 때문에 다면적이고 복잡한 최적화 문제인 경향이 있습니다.
8장 마지막에 가중치 경로 문제의 예를 보았습니다. 경로 가중치를 집계하여 데이터를 통해 가장 신뢰할 수 있는 경로를 찾으려고 했습니다. 샘플 데이터에 대한 높은 신뢰도는 높은 값으로 나타나기 때문에 이러한 유형의 경로 찾기 문제에서는 신뢰도가 높은 경로가 데이터를 통과하는 경로도 길다는 것을 발견하게 되었습니다. 이는 우리가 원했던 결과가 아니었습니다.
대신 에지 가중치를 사용하여 최단 경로를 찾는 방법을 이해해야 합니다. 수학과 컴퓨터 과학의 렌즈를 통해 경계 최소 최적화 문제를 만들고자 합니다.
이러한 의미에서 높은 신뢰도는 경로 길이와 반비례합니다. 우리는 길이가 짧으면서도 신뢰도가 높은 경로를 찾고자 합니다. 이것이 바로 이 장에서 다루고 최적화하고자 하는 어려운 이중성입니다.
챕터 미리보기: 가중치, 거리 및 가지치기 이해하기
이 장에는 세 가지 주요 섹션이 있습니다.
첫 번째 섹션에서는 최단 가중치 경로 문제를 공식적으로 정의하고 알고리즘을 살펴보겠습니다. 경로 찾기 알고리즘은 최단 가중치 경로를 찾기 위해 경로 찾기를 최적화하기 위해 폭 우선 검색을 사용합니다.
두 번째 섹션에서는 엣지 가중치 정규화 프로세스를 소개합니다. "높을수록 좋다"에서 "낮을수록 좋다"로 가중치의 척도를 이동하고 뒤집는 일반적인 프로세스를 살펴보겠습니다. 샘플 데이터 세트에 대해 계산한 새로운 가중치를 보여주고, 새로운 엣지를 생성하고, 예제에 대한 정규화된 신뢰 점수를 다시 로드합니다.
마지막 섹션에서는 정규화된 데이터에 A* 알고리즘을 사용합니다. 그렘린 쿼리 언어로 A*를 작성하고 예제 데이터에서 이를 실행하여 공개 키 1094 와 1337 로 열린 초대 사이의 최단 가중치 경로를 찾겠습니다.
이 책을 읽는 여정이 길었지만, 앞으로 소개할 사례에 대해 높은 신뢰를 보내주시기 바랍니다. 보이시죠? 이미 긴 여정을 더 높은 신뢰와 연관 짓고 계십니다.
가중치 경로 및 검색 알고리즘
저희는 이미 경로 찾기 문제에서 에지 가중치( )를 사용하려고 시도했습니다. 8장 마지막에 비트코인 OTC 트러스트 네트워크의 경로에서 신뢰 등급을 집계하는 sack() 단계를 소개할 때 이 작업을 수행했습니다.
하지만 저희가 가지고 있던 ...