TechCodeview

• Hill climb 알고리즘은 산의 정상이나 문제에 대한 최선의 해결책을 찾기 위해 고도/값이 증가하는 방향으로 지속적으로 이동하는 지역 검색 알고리즘입니다. 더 높은 값을 갖는 이웃이 없는 최고 값에 도달하면 종료됩니다.
• 언덕등반 알고리즘은 수학적 문제를 최적화하기 위해 사용되는 기술이다. 언덕 오르기 알고리즘의 가장 널리 논의되는 사례 중 하나는 세일즈맨이 이동하는 거리를 최소화해야 하는 여행-세일즈맨 문제입니다.
• 좋은 이웃 상태만 보고 그 이상은 보지 않기 때문에 탐욕스러운 지역 검색이라고도 합니다.
• 언덕 오르기 알고리즘의 노드에는 상태와 값이라는 두 가지 구성 요소가 있습니다.
• Hill Climbing은 좋은 휴리스틱이 가능할 때 주로 사용됩니다.
• 이 알고리즘에서는 단일 현재 상태만 유지하므로 검색 트리나 그래프를 유지하고 처리할 필요가 없습니다.

힐 클라이밍의 특징:

Hill Climbing 알고리즘의 주요 기능은 다음과 같습니다.

변형 생성 및 테스트:Hill Climbing은 생성 및 테스트 방법의 변형입니다. 생성 및 테스트 메서드는 검색 공간에서 이동할 방향을 결정하는 데 도움이 되는 피드백을 생성합니다.탐욕스러운 접근 방식:언덕등반 알고리즘 검색은 비용을 최적화하는 방향으로 움직입니다.역추적 없음:이전 상태를 기억하지 않으므로 검색 공간을 역추적하지 않습니다.

언덕 등반에 대한 상태공간 다이어그램:

상태공간 풍경은 다양한 알고리즘 상태와 목적 함수/비용 간의 그래프를 보여주는 언덕 오르기 알고리즘을 그래픽으로 표현한 것입니다.

맵 자바가 뭐야?

Y축에는 목적 함수 또는 비용 함수가 될 수 있는 함수를, x축에는 상태공간을 사용했습니다. Y축의 함수가 비용인 경우 검색의 목표는 전역 최소값과 로컬 최소값을 찾는 것입니다. Y축의 기능이 목적 함수인 경우 검색의 목표는 전역 최대값과 로컬 최대값을 찾는 것입니다.

상태 공간 환경의 다양한 지역:

지역 최대값: 로컬 최대값은 이웃 상태보다 나은 상태이지만, 그보다 더 높은 또 다른 상태도 있습니다.

전역 최대값: 전역 최대값은 상태 공간 환경의 가능한 최상의 상태입니다. 목적함수의 값이 가장 높습니다.

현재 상태: 현재 에이전트가 존재하는 랜드스케이프 다이어그램의 상태입니다.

이진 트리와 이진 검색 트리의 차이점

균일한 로컬 최대값: 현재 상태의 이웃 상태가 모두 동일한 값을 갖는 풍경 속의 평평한 공간이다.

어깨: 오르막이 있는 고원지대이다.

언덕 등반 알고리즘의 유형:

• 간단한 언덕 등반:
• 가장 가파른 언덕 등반:
• 확률론적 언덕 등반:

1. 간단한 언덕 오르기:

간단한 언덕 오르기(Simple Hill Climbing)는 언덕 오르기 알고리즘을 구현하는 가장 간단한 방법입니다. 한 번에 이웃 노드 상태만 평가하고 현재 비용을 최적화하는 첫 번째 노드를 선택하여 현재 상태로 설정합니다. . 하나의 후속 상태인지 확인하고, 현재 상태보다 나은 것으로 판단되면 다른 상태로 이동합니다. 이 알고리즘에는 다음과 같은 기능이 있습니다.

• 시간 소모가 적음
• 덜 최적의 솔루션이며 솔루션이 보장되지 않습니다.

간단한 언덕 등반을 위한 알고리즘:

1 단계:초기 상태를 평가하고, 목표 상태이면 성공을 반환하고 중지합니다.2 단계:솔루션을 찾거나 적용할 새 연산자가 남지 않을 때까지 반복합니다.3단계:현재 상태에 연산자를 선택하고 적용합니다.4단계:새 상태를 확인하세요.
1. 목표 상태라면 성공을 반환하고 종료합니다.
2. 그렇지 않고 현재 상태보다 나은 경우 새 상태를 현재 상태로 할당합니다.
3. 그렇지 않고 현재 상태보다 좋지 않으면 2단계로 돌아갑니다.
5단계:출구.

2. 가장 가파른 언덕 등반:

가장 가파른 오르막 알고리즘은 간단한 언덕 오르기 알고리즘의 변형입니다. 이 알고리즘은 현재 상태의 모든 이웃 노드를 검사하고 목표 상태에 가장 가까운 하나의 이웃 노드를 선택합니다. 이 알고리즘은 여러 이웃을 검색하므로 더 많은 시간을 소비합니다.

가장 가파른 언덕 등반을 위한 알고리즘:

1 단계:초기 상태를 평가하고, 목표 상태이면 성공을 반환하고 중지하고, 그렇지 않으면 현재 상태를 초기 상태로 만듭니다.2 단계:해결책을 찾거나 현재 상태가 변경되지 않을 때까지 반복합니다.
1. SUCC를 현재 상태의 후속 항목이 그 상태보다 더 나은 상태라고 가정합니다.
2. 현재 상태에 적용되는 각 연산자에 대해 다음을 수행합니다.
   1. 새 연산자를 적용하고 새 상태를 생성합니다.
   2. 새로운 상태를 평가합니다.
   3. 목표 상태라면 반환하고 종료하고, 그렇지 않으면 SUCC와 비교합니다.
   4. SUCC보다 나은 경우 새 상태를 SUCC로 설정합니다.
   5. SUCC가 현재 상태보다 좋으면 현재 상태를 SUCC로 설정합니다.
5단계:출구.

3. 확률론적 언덕 등반:

확률론적 언덕 등반은 이동하기 전에 모든 이웃을 검사하지 않습니다. 오히려 이 검색 알고리즘은 하나의 이웃 노드를 무작위로 선택하고 이를 현재 상태로 선택할지 아니면 다른 상태를 검사할지 결정합니다.

자바스크립트 변수 전역

언덕 오르기 알고리즘의 문제점:

1. 지역 최대값: 지역 최대값은 각 인접 주보다 나은 경관의 최고점 상태이지만 지역 최대값보다 높은 또 다른 상태도 존재합니다.

해결책: 역추적 기술은 상태 공간 환경에서 로컬 최대값에 대한 솔루션이 될 수 있습니다. 알고리즘이 검색 공간을 역추적하고 다른 경로도 탐색할 수 있도록 유망한 경로 목록을 만듭니다.

2. 고원: 고원은 현재 상태의 모든 이웃 상태가 동일한 값을 포함하는 검색 공간의 평평한 영역입니다. 왜냐하면 이 알고리즘으로 인해 이동할 최적의 방향을 찾을 수 없기 때문입니다. 고원 지역에서는 언덕 등반 수색이 손실될 수 있습니다.

해결책: 고원에 대한 해결책은 문제를 해결하기 위해 검색하는 동안 큰 단계 또는 아주 작은 단계를 수행하는 것입니다. 현재 상태에서 멀리 떨어진 상태를 무작위로 선택하면 알고리즘이 고원이 아닌 영역을 찾을 수 있습니다.

티스푼 vs 테이블스푼

3. 능선: 능선은 지역 최대값의 특별한 형태입니다. 주변 지역에 비해 면적이 높지만 그 자체가 경사가 있어 한 번에 이동할 수는 없습니다.

해결책: 양방향 검색을 사용하거나 다른 방향으로 이동하여 이 문제를 개선할 수 있습니다.

시뮬레이션된 어닐링:

더 낮은 값을 향해 절대 이동하지 않는 언덕 오르기 알고리즘은 로컬 최대값에 걸릴 수 있기 때문에 불완전함을 보장합니다. 그리고 알고리즘이 후속 작업을 이동하여 무작위 진행을 적용하면 완료될 수 있지만 효율적이지 않을 수 있습니다. 모의 어닐링 효율성과 완전성을 모두 제공하는 알고리즘입니다.

기계적인 용어로 가열 냉각 금속이나 유리를 고온에서 경화시킨 후 서서히 냉각시켜 금속이 저에너지 결정 상태에 도달하는 과정입니다. 알고리즘이 최상의 움직임을 선택하는 대신 무작위 움직임을 선택하는 시뮬레이션 어닐링에도 동일한 프로세스가 사용됩니다. 무작위 이동으로 인해 상태가 개선되면 동일한 경로를 따릅니다. 그렇지 않으면 알고리즘은 확률이 1보다 작은 경로를 따르거나 내리막길로 이동하여 다른 경로를 선택합니다.