최단 이동 순서

Question

면책 조항 :이 문제는 과거의 AI 최종 시험에서 나왔습니다. 그리고 나는 그것을 매우 흥미로웠다. 그러나 나는 그것을 이해할 수 없었다.

설명이 있습니다. 미로를 감안할 때 인접한 흰색 셀 사이를 자유롭게 이동할 수 있지만 검은 색 셀은 차단됩니다. 위, 아래, 왼쪽, 오른쪽으로 움직일 수 있습니다. 그 방향으로 막히지 않으면 성공적으로 움직입니다. 당신이 막히면, 당신은 같은 곳에 머물러있게됩니다.

a) 어디서 시작했는지에 관계없이 G로 끝나는 것을 보장하는 가능한 가장 짧은 이동 순서를 찾습니다.

Answer 1

어떤 이동하기 전에, 당신은 어떤 위치에있을 수있다. 이동할 때마다 가능한 위치 집합이 바뀌고 가능한 위치에서 움직이면 벽에 부딪 힐 수 있습니다. 그러나 가능한 위치 집합은 결코 크기가 증가하지 않습니다.

발생할 수있는 위치 세트마다 정점이있는 유향 그래프와 각 세트를 왼쪽, 오른쪽, 위 또는 아래로 움직일 때 따라 오는 4 세트로 연결하는 직선 그래프를 가정 할 수 있습니다.

당신의 작업은 모든 위치 집합에 대한 정점에서 목표 위치만을 포함하는 단일체 집합에 대한 정점까지의 최단 경로를 찾는 것입니다.

첫 번째 시도는 적절한 측정 항목을 사용하여이 그래프에서 A *를 실행하는 것입니다. 가능한 세트의 수는 매우 많기 때문에 가능하지는 않습니다. 나는 인간의 지능을 사용하여 신속하게 작동하는 측정 항목을 선택하려고합니다.

합리적인 시간에 A *를 완료하고 A *가 메트릭에 적용하는 규칙을 준수하는 메트릭을 선택할 수 있으면 발견 한 경로가 가장 짧은 메트릭임을 입증 할 수 있습니다.

내 머리 꼭대기에서 벗어나면, 먼저 세트의 가장 먼 위치에서 최단 경로 길이를 시도합니다. 비어 있지 않은 행과 열의 총 수와 함께 사용했을 수 있습니다.

그래서 내가 할 수있는 일이지만 AI 전문가는 아닙니다. 나는 아마도 당신이이 과정을 향상시킬 수있는 수업에서 배운 뭔가가있을 것이라고 추측합니다.