슬라이딩 타일 문제에 대한 휴리스틱

Question

아이디어는 모든 오른쪽 요소를 왼쪽으로, 왼쪽을 오른쪽으로 옮기는 것입니다. 요소는 하나 또는 두 조각 위로 빈 공간으로 점프 할 수 있습니다.

LLL[ ]RRR

나는이 과제에 대한 휴리스틱을 생각하려고 노력하고있다. 휴리스틱은 가능한 해결책을 찾는 데 도움이됩니까, 아니면 실제로 여러 가지 움직임을 해결책으로 반환합니까? 그런 휴리스틱을 어떻게 표현합니까?

Answer 1

휴리스틱이 무엇인지에 대해 약간 혼란스러워하는 것 같습니다.

거친 정의는 "단순화 된 가정"또는 "괜찮은 추측"입니다.

예를 들어, 농구 팀을 구성해야한다고 가정 해 보겠습니다. 연락처 정보, 생년월일 및 높이를 나열하는 사람들에게 사실 시트가 있다고 가정 해 봅시다. 각 후보자의 특정 기술을 테스트하는 곳에서 시험을 볼 수 있습니다. 그러나 모든 후보자를 데려 오는 데 시간이 오래 걸릴 수 있습니다. 당신은 수색을 좁히기 위해 휴리스틱을 사용합니다. 키가 6'2 "이상인 사람들에게만 전화하십시오. 이것은 훌륭한 농구 선수를 무시할 수 있지만 꽤 괜찮은 추측입니다.

휴리스틱의 또 다른 예 : 청구서를 지불하기 위해 가장 적은 수의 동전을 사용하려고합니다. 휴리스틱 (단순화 접근법)은 먼저 가장 큰 가치 (나머지 청구서보다 작음)로 동전을 선택하고 청구서에서 가치를 빼고 반복하는 것입니다. 이것은 매번 일할 수있는 것은 아니지만 대부분의 시간 동안 올바른 동네로 갈 수 있습니다.

문제에 대한 휴리스틱은 "LS를 오른쪽으로 옮기지 않고 RS를 왼쪽으로 옮기지 않는다"는 것일 수 있습니다. 처음부터 일부 가능성을 제거하여 가능한 모든 움직임의 "검색 공간"을 좁 힙니다.

Answer 2

휴리스틱이나 알고리즘을 찾고 있습니까? 휴리스틱은 주어진 문제를 해결하거나 해결하지 않을 수도 있습니다. 실제로 솔루션이있을 수있는 방향을 가리키기위한 것입니다. 알고리즘은 실제로 주어진 문제를 해결해야합니다.

Answer 3

휴리스틱은 일반적으로 "힌트"이며, 일반적으로 (항상 아는 것은 아니지만) 절차를 올바른 방향으로 안내합니다. 휴리스틱을 사용하면 절차 속도 (알고리즘)가 다시 발생합니다. 대개, 항상 그런 것은 아닙니다. 그것은 알고리즘에 대한 "조언"과 같습니다.

설명이 약간 모호하기 때문에 당신이 무엇을 찾고 있는지 잘 모르겠습니다. 알고리즘을 원한다면 현재 상황에 어떤 영향을 미치는지, 매번 가능한 모든 움직임에 어떤 영향을 미치는지 연구해야합니다. 당신은 특정한 순서를 만듭니다).

당신은 또한 그것이 중요하다는 것을 알 수 있습니다 얼마나 가까이 현재 위치는 달성하고자하는 것 (원하는 최종 위치)에 대한 것입니다. 따라서 최종 상태를 찾을 때까지 초기 상태에서 가능한 모든 경로를 계산하는 대신 휴리스틱을 기반으로 알고리즘을 안내 할 수 있습니다. 원하는 상태로의 전류 상태 ""나무의 일부만을 가로 지르십시오.