일관된 및 허용 가능한 휴리스틱

어떠한 일관된 휴리스틱이라도 타당합니다. 그러나 언제 휴리스틱이 타당하지만 일관성(조화성)이 없는 경우인지 예시를 제공해주세요.

이러한 경우를 설명해주세요.

답변 1

이 퍼즐에서는 1-8로 번호가 매겨진 8개의 슬라이딩 타일과 하나의 빈 공간이 있습니다. 타일은 처음에 정렬되지 않은 상태입니다 (왼쪽 이미지 참조). 목표는 타일을 빈 공간으로 슬라이딩하여 오른쪽 상태와 같이 퍼즐을 완성하는 것입니다. 이 문제에 대한 전통적인 휴리스틱(각 타일의 위치로부터 맨해튼 거리)는 타당하고 일정합니다.

하지만 다른 휴리스틱도 사용할 수 있습니다. 아마도 목표 상태에서 1, 2, 3의 위치와의 맨해튼 거리 (즉, 사각형 간의 거리)만 확인하고 싶을 수도 있습니다. 이 휴리스틱은 모든 타일의 맨해튼 거리보다는 정보가 적지만, 여전히

하지만 추가적인 사각형 그룹인 5, 6 및 7을 선택한다고 가정해 보겠습니다. 그리고 각 노드에서 휴리스틱을 계산하는 방법은 이러한 세트 (1, 2 및 3) 또는 (5, 6 및 7) 중 하나를 무작위로 선택하고 그들의 목표 위치까지의 맨해튼 거리를 계산하는 것입니다. 이 휴리스틱은 아직 충분함 - 목표 상태에 도달하기 위해 필요한 움직임 수를 저절로 낮추거나 일치시킬 수 있습니다. 그러나 이제는 일관되지 않습니다 - 각 노드에서 휴리스틱 추정치 사이에 명확한 관계가 없습니다.

답변 2

일관된 및 허용 가능한 휴리스틱
일관된 및 허용 가능한 휴리스틱은 인공지능 분야에서 주로 사용되는 휴리스틱 탐색 알고리즘의 개념으로, 최적 해를 찾기 위한 예측 함수로 사용됩니다. 이번 글에서는 일관된 및 허용 가능한 휴리스틱에 대해 자세히 알아보도록 하겠습니다.
일관된 휴리스틱은 모든 상태에 대해 일관된 예측 값을 반환하는 휴리스틱 함수입니다. 즉, 같은 상태에 대해서는 항상 같은 예측 값을 내놓아야 합니다. 예를 들어, 특정 게임에서 현재 상태를 평가하는 함수가 있을 때, 이 함수가 항상 같은 점수를 도출한다면 그 함수는 일관된 휴리스틱으로 간주됩니다.
허용 가능한 휴리스틱은 실제 최적 해보다 상대적으로 높은 값을 갖는 예측 함수입니다. 이는 휴리스틱으로 사용되는 함수가 실제 해를 과도하게 고평가하지 않도록 제한하는 역할을 합니다. 허용 가능한 휴리스틱은 휴리스틱 함수의 값을 정확한 예측 값보다 높게 설정하기 때문에, 탐색 알고리즘이 훨씬 빠르게 최적 해를 찾을 수 있습니다. 따라서 허용 가능한 휴리스틱은 탐색 시간을 단축시키는 데 매우 효과적입니다.
휴리스틱은 일반적으로 최적화 문제에서 사용되며, 많은 문제에서 유용하게 적용될 수 있습니다. 예를 들어, 경로 탐색 문제에서 최단 경로를 찾는 데 사용되며, 스케줄링 문제에서 최소 시간 또는 최소 비용의 스케줄을 계획하는 데 활용됩니다. 일관된 및 허용 가능한 휴리스틱은 이러한 문제들을 해결함에 있어서 더욱 효율적인 옵션을 제공합니다.
요약하자면, 일관된 및 허용 가능한 휴리스틱은 예측 함수로써 최적 해를 찾는 데 사용되는 알고리즘입니다. 일관된 휴리스틱은 항상 같은 예측 값을 반환하며, 허용 가능한 휴리스틱은 실제 해보다 높은 값을 갖는 예측 함수입니다. 이러한 휴리스틱은 다양한 최적화 문제에서 적용될 수 있으며, 탐색 시간을 단축시킬 수 있는 강력한 도구입니다.
이상으로 일관된 및 허용 가능한 휴리스틱에 대해 알아보았습니다. 이 효과적인 알고리즘이 다양한 분야에서 사용되는 이유는 그 유용성과 효율성에 기인합니다. 앞으로도 휴리스틱 기법은 인공지능과 최적화 분야에서 계속해서 발전하고 적용될 것입니다.