알고리즘 번호를 정렬

Question

I 0

으로 얻어진 수를 각각의 수를 교환하여 오름차순으로 정렬 될 필요가 상이한 수치 예에 대한 0

각 번호를 교환에서만 얻어야했다

, 3x3 행렬을 가지고 있습니다.

3 4  1 
    2 5  0 
    6 8  7 

위의 행렬에서 숫자를 오름차순으로 바꾸려면 숫자를 0으로 바꿔야합니다. 위부터는 첫 번째 단계에서 5,7 및 1 만 0으로 바꾼다. 최종 결과물은 다음과 같아야합니다.

1 2  3 
    4 5  6 
    7 8  0 

이 작업을 수행하는 최적의 솔루션은 무엇입니까?

감사

Answer 1

이 유명한 15-puzzle의 쉬운 버전입니다.

이러한 문제에 접근하기위한 일반적인 방법은 주 그래프, 타겟 (정렬 판)의 소스 (주어진 보드)에서 경로를 찾기 위하여 shortest-path 알고리즘을 실행으로 모델이다.

상태 그래프는 G=(V,E)입니다. 여기서 : V= { all possible boards } 및 E = {(u, v) | 하나의 스왑으로 보드 u를 v로 바꿀 수 있습니다.

당신은 실행할 수 있습니다 BFS 또는 bi-directional BFS 솔루션을 얻을 스왑의 시리즈를 나타내는 상태 그래프의 경로를 찾기 위해, 또는 적절한 허용 휴리스틱 기능도 A* Algorithm (당신은 하나의 소스와 하나 개의 목표를 가지고 있기 때문에).