나는 피라미드를 가지고 있습니다. 각 숫자는 연관된 포인트 수를 나타냅니다. 피라미드의 꼭대기에서 바닥까지 가장 낮은 비용으로 경로를 찾는 욕심 많은 알고리즘을 사용해야합니다. 나는 정보가없는 & 정보 검색 알고리즘에 대해 읽었지 만 여전히 무엇을 선택해야할지 모르겠다. 이런 종류의 문제에 가장 적합한 것은 무엇입니까? 욕심쟁이 선착순 검색/A * 검색 또는 기타? 그것은 아주 간단한 문제이지만, 최선의 옵션이 무엇인지 알기 위해 모든 알고리즘과 함께 사용하지는 않습니다. 그리고 내가 말했듯이, 그것은 탐욕스러운 알고리즘이어야합니다.최저 비용 경로를 찾기 위해 욕심 많은 알고리즘 선택
필자가 올바르게 이해하고 있다면 피라미드에서 항상 왼쪽 또는 오른쪽으로 내려갈 수있는 옵션이 있으며 맨 아래로가는 비용은 전달하는 모든 노드의 합계입니다.
이 경우 하단에서 위로 올라가면됩니다. 아래에서 두 번째 줄부터 시작하십시오. 행의 각 노드에 대해 아래 행의 왼쪽 및 오른쪽 하위를 봅니다. 저렴한 노드의 비용을 현재 노드에 추가하십시오. 루트/피크에 도달 할 때까지 행을 위로 이동하고 반복합니다. 각 노드에는 이제부터 가장 낮은 경로의 비용이 포함됩니다. 싼 비용으로 자식 노드를 선택하여 탐욕스러워집니다.
Dijkstra-Algorithm은 A * 검색보다 간단하지만 원하는 것은 DFS가 그렇게하는 것입니다. 나는 네가 정말로 원하는 것이 무엇인지 확신하지 못한다.
여기선 올바르지 않은 greedy 알고리즘을 사용해야 할 필요가없는 경우. 이런 종류의 문제에 대해 자연스럽게 "동적 프로그래밍"이라는 기술을 사용합니다.
피라미드의 모든 사각형 (무한대로 백업)을 초기화합니다. 그 자체의 값을 가진 초기 점은 제외됩니다.
그리고 위에서 아래로, 행별로 피라미드를 처리하십시오. 첫 번째 행에서 가능한 위치로 가려고합니다. (유일한 행만 있으므로) 두 번째 행의 노드를 업데이트하여 최상위 값 + 값을 부여합니다. 그런 다음 두 번째 행으로 이동하고 다음 행의 노드를 업데이트합니다.
이전에 노드에 대한 더 나은 경로를 발견 했으므로 (한 노드를 왼쪽으로 한 노드에서 이어짐) 새로 작성한 경로가 "더 빠름"경우에만 업데이트 할 수 있습니다. (무한대의 초기화를 만들었습니다. 즉, 루트가 실제로 존재하는지 여부를 알지 못한다는 것을 의미합니다.) pyradim의 레벨 처리가 끝나면, 노드에 배치 할 수있는 최상의 경로가 있음을 알게됩니다. 레벨 바로 아래.
약간 복잡한 것처럼 들리더라도 구현하기가 쉽습니다. 문제가되지 않기를 바랍니다.
그것은 내가 한 일입니다. 그냥 너무 단순 해 보였지만 적어도 필자는 피라미드의 꼭대기에서 시작하여 가능한 가장 낮은 비용으로 다음 노드를 선택할 수있었습니다. 나는 단지 내가 올바른 접근 방식을 생각하고 있는지 확인하고 싶었다. 어쨌든 고마워. – joanna
@ Joanna : 피라미드에는 각 레벨마다 4 개의 노드가 있으므로 질문을 수정하는 것이 좋습니다. 네가 원하는 것은 새끼를 낳는 사람이다. tetraeder에는 각 레벨마다 3 개의 노드가 있습니다. – Bytemain
@joanna 당신이보고있는 비용이 거기에서 최하단까지의 최단 경로 비용인지 확인하십시오. 해당 노드 자체의 비용 일 경우 알고리즘이 올바르지 않습니다. –