Permutation 그룹에서

우리는 종종 permutation이 작동하는 타겟 그룹의 원소 A를 그룹의 원소 B로 바꾸는 변환 원소를 찾고 싶어함.

예를 들어 루빅 큐브를 예로 들면 잘 섞인 루빅 큐브를 풀 때, 이것을 우측 회전, 윗면 회전, 앞면 회전 등의 변환 (generator)의 합성으로 생각하는 것과 같음.

그러면 우리는 케일리 그래프를 생각하여 현재 큐브의 상태를 노드, 간선을 generator로 생각해서 경로를 찾는 문제와 같아짐.

한편 이러한 generator의 숫자가 많기 때문에 노드의 간선의 차원이 굉장히 높아지고, 이로인해 직접적으로 경로를 찾는 방법이 힘들어짐.

이는 NP-Hard 로 증명된 문제.

한편, 최단경로 탐색 문제에서는

이러한 간선의 복잡성을 휴리스틱하게 이웃과 거리를 기준으로 가지를 치거나, 출발점과 도착점 사이에 랜드마크 (중간지점)을 설정함으로써 문제의 복잡성을 낮춤.

상용화 된 큐브 풀이에서도 이러한 큐브의 중간 지점을 설정하여 푸는 방식으로 해결하는데,

1. 문제는 이러한 중간 지점이 먼저 최적의 중간지점이 아님.

휴리스틱한 풀이로 인간의 문제에 대한 직관이 반영된 중간 지점임.

보통 이 중간 지점으로 만드는 방법이 확실히 존재하고, 이 중간지점부터 최종 답까지 만들 수 있는 패턴유형이 정해질 때 사용함.

2. 큐브의 모양이 달라지면, 이런 휴리스틱한 방법은 확장이 어려움.

이러한 문제에 호기심을 느끼고 최근 그룹 이론을 찾아봤는데.

결론은 그룹 이론에서는 이러한 랜드마크를 가상의 추상화된 x1, x2, x3 등으로 놓고, 이를 사용하여 그룹을 chain 으로 분할하여 순열을 generator로 분해하는 것을 함.

결국 이러한 x1, x2, x3를 선택하게 되면 그룹 이론에서의 응용은 휴리스틱한 solver를 이론적으로 기술한 것이고, 그대로 알고리즘으로 옮기면 좀 더 비효율적이 됨.

대수학은 마치 수영장에
단계별로 올라가는 계단을 만든 것 같은 느낌.헤엄쳐서 올라가면 더 빠른데, 수영장 안에서 계단을 밟고 올라가는 기분.