경로 찾기 : A에서 B까지의 길이가 A에서 B가 아닌

Question

8 퍼즐의 맨하탄 거리를 사용하여 A 성급 알고리즘을 구현 중입니다. A.에 B로 갈수록 동일한 단계 번호를 가지고 있지 않습니다 A에서 B로 가고, 일부 경우

1 2 3 
8 0 4 
7 6 5 

[용액 나선 형태]

I는 않기 때문이라고 생각 동일한 비용을 가지고 동일한 노드를 확장하지 않을 때 열려있는 목록에서 동일한 상태를 선택하지 마십시오. 둘은 맨해튼 거리를 이용하여 동일한 값을 가질

7 6 4 
1 0 8 
2 3 5 



(A -> B) 

7 6 4 
1 8 0 
2 3 5 

(B -> A) 

7 6 4 
1 3 8 
2 0 5 

가입일

. 같은 값으로 모든 경로를 탐색해야합니까? 또는 휴리스틱을 변경하여 일종의 타이 브레이커를 사용해야합니까?

여기에 너무 많은 시간 나는 마침내 문제를 발견, 아무것도, 을 내 "해결"기능을 여러 가지 방법을 재 작성을 낭비 후 코드

def solve(self): 
    cost = 0 
    priority = 0 
    self.parents[str(self.start)] = (None, 0, 0) 
    open = p.pr() #priority queue 
    open.add(0, self.start, cost) 
    while open: 
     current = open.get() 
     if current == self.goal: 
     return self.print_solution(current) 
     parent = self.parents[str(current)] 
     cost = self.parents[str(current)][2] + 1 
     for new_state in self.get_next_states(current): 
     if str(new_state[0]) not in self.parents or cost < self.parents[str(new_state[0])][2]: 
      priority = self.f(new_state) + cost 
      open.add(priority, new_state[0], cost) 
      self.parents[str(new_state[0])] = (current, priority, cost) 

Answer 1

의 관련 부분이다.

def get_next_states(self, mtx, direction): 
    n = self.n 
    pos = mtx.index(0) 
    if direction != 1 and pos < self.length and (pos + 1) % n: 
     yield (self.swap(pos, pos + 1, mtx),pos, 3) 
    if direction != 2 and pos < self.length - self.n: 
     yield (self.swap(pos, pos + n, mtx),pos, 4) 
    if direction != 3 and pos > 0 and pos % n: 
    yield (self.swap(pos, pos - 1, mtx),pos, 1) 
    if direction != 4 and pos > n - 1: 
    yield (self.swap(pos, pos - n, mtx),pos, 2) 

이 기능을 사용했습니다. 마지막으로 사용 된 경우 "만약 4 POS> N :" 그래서 거기 미개척 상태 .. 이일에 대해 "-1"

은 내가 '