A* Algorithm for Optimal Intra-bay Container Pre-marshalling Plan

목표: A*알고리즘으로 각 stack의 인덱스가 내림차순으로 정렬되는 최적화 문제를 해결

Input:

A = [
        [2, 1],
        [2, 3],
        [2, 3]
    ]   

W = 3
H = 3

조건:

이 모든 조건을 다 만족시키는 알고리즘을 짜야함.

1. 작은 인덱스 위에 큰 인덱스를 옮길 수 없다.
2. 주어진 W와 H를 맞추기 위해 빈자리는 0으로 채운다.
3. 0은 빈자리 이므로 옮길 수 없다.
4. 각 stack의 0 뒤에는 어떠한 컨테이너도 올 수 없다.
5. 옮길때 마다 각 스택이 내림차순으로 정렬되어 있는지 검증하고 다시 재배치를 시작한다.
6. 1회 재배치 시, 가장 오른쪽에 있는 컨테이너(’인덱스’:’값’)만 옮길 수 있다.
7. 가장 뒤에 있는 컨테이너 중 가장 인덱스가 큰 컨테이너를 우선으로 주어진 0(빈자리) 중에 배치한다. (가중치 부여)
8. 맨 아래에 있는 0에는 가장 인덱스가 큰 컨테이너를 우선으로 가장 큰 것을 선택한다. (가중치 부여)
9. 각 열의 가장 오른쪽에 있는 0이 아닌 값만을 이동할 수 있다.
10. 각 열의 가장 오른쪽에 있는 값이 아니면 이동할 수 없다.
11. 이동할 때, 왼쪽에(밑) 0값이 있으면 이동할 수 없다.
12. 같은 행 끼리는 컨테이너를 옮길 수 없다.
13. 1회 재배치 시, 마지막으로 옮긴 컨테이너를 제외하고 옮길 컨테이너를 선택한다.

결과

시험기간에 이것만 붙잡고 3일내내 밤을 새는 수고를 한 결과..

Initial state:
[{'a': 2}, {'b': 1}, {'c': 0}]
[{'d': 2}, {'e': 3}, {'f': 0}]
[{'g': 2}, {'h': 3}, {'i': 0}]

[('e', 3)] to (2, 2). Move count: 1
[{'a': 2}, {'b': 1}, {'c': 0}]
[{'d': 2}, {'i': 0}, {'f': 0}]
[{'g': 2}, {'h': 3}, {'e': 3}]

No valid empty slot found.
[('d', 2)] to (0, 2). Move count: 2
[{'a': 2}, {'b': 1}, {'d': 2}]
[{'c': 0}, {'i': 0}, {'f': 0}]
[{'g': 2}, {'h': 3}, {'e': 3}]

[('e', 3)] to (1, 0). Move count: 3
[{'a': 2}, {'b': 1}, {'d': 2}]
[{'e': 3}, {'i': 0}, {'f': 0}]
[{'g': 2}, {'h': 3}, {'c': 0}]

[('h', 3)] to (1, 1). Move count: 4
[{'a': 2}, {'b': 1}, {'d': 2}]
[{'e': 3}, {'h': 3}, {'f': 0}]
[{'g': 2}, {'i': 0}, {'c': 0}]

No valid empty slot found.
[('d', 2)] to (2, 1). Move count: 5
[{'a': 2}, {'b': 1}, {'i': 0}]
[{'e': 3}, {'h': 3}, {'f': 0}]
[{'g': 2}, {'d': 2}, {'c': 0}]

########## Final State ##########
[{'a': 2}, {'b': 1}, {'i': 0}]
[{'e': 3}, {'h': 3}, {'f': 0}]
[{'g': 2}, {'d': 2}, {'c': 0}]
Move count: 5
All containers are suitable.

 

성공..!!

이제 진짜 시험기간이다. (실화냐)