8 개의 퍼즐에서 맨하탄 거리 계산하기

Question

나는 경험에 입각 한 정보 검색을 사용하여 파이썬에서 8 개의 퍼즐을 푸는 프로그램을 연구 중이다. 우리가 사용하기로되어있는 휴리스틱은 맨해튼 거리입니다. A는 보드 같은 경우 : 맨하탄 거리가 4 + 0 + 3 + 3 + 1 + 0 + 2 + 1 = 14

시각 것

State   Goal  Different Goal 
7 2 4   1 2 3   1 2 3 
5  6   8  4   4 5 6 
8 3 1   7 6 5   7 8 

, 그것은 특정 숫자가 얼마나 많은 공간 거리 계산하기 쉽지만, 파이썬에서 나는 목록으로 보드를 대표하고 위의 보드는 [7, 2, 4, 5, 0, 6, 8, 3, 1]이고 목표 상태는 [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]입니다. 나는 mod를 사용하여 작동 시키려고 노력하고 있지만 제대로 작동하지 못하는 것처럼 보였습니다. 제 선생님은 mod를 사용하는 것이 이것을하는 방법을 찾는 데 도움이 될 것이라고 말했습니다. 필자가 보았던 몇 가지 예는 abs(x_val - x_goal) + abs(y_val - y_goal)을위한 2 차원 배열을 사용했지만 목록을 사용하고 있기 때문에 이것을 구현하는 방법을 모르겠습니다. 내가 지금까지 가지고 코드는 다음과 같습니다

distance = 0 
xVal = 0 
yVal = 0 
for i in range(len(self.layoutList)): 
    pos = self.layoutList.index(i) 
    if pos i == 0 or pos i == 1 or pos i == 2: 
     xVal = pos 
     yVal = 0 
    if pos i == 3 or pos i == 4 or pos i == 5: 
     xVal = pos - 3 
     yVal = 1 
    if pos i == 6 or pos i == 7 or pos i == 8: 
     xVal = pos - 6 
     yVal = 2 

이 각 타일에 대한 X, Y 값을 생성합니다. 따라서 위의 상태는 [7, 2, 4, 5, 0, 6, 8, 3, 1]으로 표현하면 (0, 0)은 7, (2, 0)은 4 등입니다. goalstate가 x, y 좌표를 얻는 방법과 동일한 방식으로 구현할 것입니다. 그렇다면 나는 x-val의 절대 값을 취할 것입니다 - x_goal과 이것 저것. 그러나 2 개의 for 루프를 사용하여 목록을 반복하는 대신 목록에서 직접 수행하는 것이 더 효율적이며 효율적인 방법이 있습니까? 각 번호의 Manhatten에 거리 합한

Answer 1

예 :

>>> board = [7, 2, 4, 5, 0, 6, 8, 3, 1] 
>>> sum(abs((val-1)%3 - i%3) + abs((val-1)//3 - i//3) 
     for i, val in enumerate(board) if val) 
14 

은 7 (영된다) 좌표 (0, 2) = ((7-1)%3, (7-1)//3)하지만에서 (0, 0이 좌표에 속하는)이므로 abs(0 - 0) + abs(2 - 0)을 추가하십시오. 표준이 아닌 목표에

:

>>> goal = [1, 2, 3, 8, 0, 4, 7, 6, 5] 
>>> sum(abs(b%3 - g%3) + abs(b//3 - g//3) 
     for b, g in ((board.index(i), goal.index(i)) for i in range(1, 9))) 
16