IDA * 및 허용 가능성 중 하나는 휴리스틱 스입니까?

Question

AI에서 오래된 시험을 연습하고 도전적인 질문 하나를보고 일부 전문가의 도움이 필요합니다. ...

A는 초기 상태이고 G는 목표 상태입니다. 비용은 가장자리에 표시되며 휴리스틱 "H"값은 각 원에 표시됩니다. IDA * 한도는 7입니다. IDA *로이 그래프를 검색하고 싶습니다. 이 노드를 방문하는 순서는 무엇입니까? (자식은 알파벳순으로 선택되며 동일한 조건으로 먼저 노드가 먼저 선택됩니다.)

해결책은 A, B, D, C, D, G입니다.

내 질문이 계산 방법이며, 우리가 말할 수있는 방법이 휴리스틱 는 허용 가능하고 일관된입니까?

Answer 1

내 질문이 계산 방법이며, 우리는이 말을 할 수있는 방법 휴리스틱은 허용 가능하고 일관된입니까? 허용 무엇인지 정의하고 일관성있는 추론과

하자 처음 시작 : 목표에 도달하기 위해 추정 된 비용이 아닌, 즉

1. 허용 발견 결코, 목표에 도달하는 비용을 과대 평가하지 그래프에서 노드에서 목표 노드까지의 최단 경로 비용보다 큽니다.

   그래프에서 모든 노드에 대해 h(n)은 항상 실제 최단 경로보다 작거나 같음을 쉽게 알 수 있습니다. 예를 들어, h (B) = 0 < = 6 (B -> F -> G).

2. 하자 C (N, M)이 다른 노드에 노드 n'n 에서 그래프의 최적 경로의 비용을 나타낸다. 그래프에서 모든 노드에 대해 h(n)의 h(n) + c(n, m) <= h(n')n , n' 일 때 경험적 예상 기능이 일치합니다. 일관성의 속성을 보는 또 다른 방법은 단조 로움 (monotonicity)입니다. 일관된 경험적 함수는 부분 솔루션의 예상 최종 비용으로 인해 단조 함수라고도하며 목표까지의 최적 경로를 따라 단조롭게 감소하지 않습니다. 따라서 휴리스틱 함수가 일관성이 없다는 것을 알 수 있습니다.

   H (A) + (C) (A, B) < = h를 (B) -> 6 + 2 < = 0

나 덜 수학적 방법을 설명하기 위해 비유하자 . 친구와 함께 달릴 것입니다. 어느 시점에서 당신은 당신의 친구에게 당신의 달리기를 끝내는 데 얼마나 오래 걸릴지를 묻습니다. 그는 매우 낙관적 인 사람이며, 비록 당신이 당신의 정상에서 당신의 모든 나머지 길을 달릴지라도 당신은 당신이 할 수있는 작은 시간을 항상주고 있습니다. 그러나 그는 자신의 견적에 일관성이 없습니다. A 지점에서 그는을 실행하기 위해 적어도 1 시간 이상 이 될 것이며, 30 분 후에 다시 물어 보았다고 말했습니다. 지금, 그는 적어도 이고, 거기에서 적어도 5 분 더입니다.A 지점의 추정 은 B 지점보다 정보가 적으므로 경험있는 친구가 일치하지 않습니다.

IDA *의 실행과 관련하여, 나는 위키 피 디아에서 알고리즘 (I 테스트하지 않은)의 의사을 복사하여 붙여 넣기 :

node    current node 
g     the cost to reach current node 
f     estimated cost of the cheapest path (root..node..goal) 
h(node)   estimated cost of the cheapest path (node..goal) 
cost(node, succ) step cost function 
is_goal(node)  goal test 
successors(node) node expanding function 

procedure ida_star(root) 
    bound := h(root) 
    loop 
    t := search(root, 0, bound) 
    if t = FOUND then return bound 
    if t = ∞ then return NOT_FOUND 
    bound := t 
    end loop 
end procedure 

function search(node, g, bound) 
    f := g + h(node) 
    if f > bound then return f 
    if is_goal(node) then return FOUND 
    min := ∞ 
    for succ in successors(node) do 
    t := search(succ, g + cost(node, succ), bound) 
    if t = FOUND then return FOUND 
    if t < min then min := t 
    end for 
    return min 
end function 

은 예를 들어 실행에 따라 간단합니다. 먼저 시작 노드에 대한 휴리스틱 함수의 값으로 경계 (또는 임계 값)를 설정합니다. f 값이 경계보다 큰 지점을 제외하는 깊이 우선 검색 방법으로 그래프를 탐색합니다. 예를 들어, F (F) = g (F) + h (F) = 4 + 4> 경계 = 6.노드는 A, B, D, C, D, G 순으로 탐구됩니다. 알고리즘의 첫 번째 반복에서 노드 A, B, D가 탐색되고 경계보다 작은 옵션이 부족합니다.

바운드가 업데이트되고 두 번째 반복에서 노드 C, D 및 G가 탐색됩니다. 일단 bound (8)보다 작은 추정 (7)으로 솔루션 노드에 도달하면 최적의 최단 경로를 얻습니다.