BFS는 얕은 복사

Question

나는 루빅스 큐브 해결사를 만들기 위해 BFS를 사용하기 위해 노력하고있어 목표
의 결과로 큐 를 사용하여 검색 할 수 있습니다. 나는 그것이 그것이 대체 될 수있는 모든 방법으로 아마 느릴 것이라는 것을 안다. 누군가가 궁금해하는 경우를 대비해서 학교를위한 것이 아닙니다.

아마-쉬운 수정 문제 나는 그냥 얕은 사본, 루빅 큐브의 다른 국가가 추가되도록되어 일단 queue<array>에 스크램블 매직 큐브의 또 다른 상태를 가져온 거에요 때마다
큐의 이전 상태는 실제로 변경되어 더 새로운 상태와 일치합니다. 즉, queue<array> 안에있는 모든 요소가 동일하게 유지되도록하려면 어떻게해야합니까? 내가 넣어 전에

나는 그것이 큐에서 나오는 때 기본적으로이 코드를 사용
https://stackoverflow.com/a/129395/984680
이 큐브의 새 복사본을 만들 해결하기 위해 만들었습니다 시도하고, 그 다음 나는 또 다른 새로운 복사본을 생성 큐에 다시 넣습니다 (다른 상태에서). 아래 코드는 새 복사본이 대기열에 삽입되기 전에 어떻게 만들어 지는지 보여줍니다.

//make deep copy of ccube (char array) 
    char[][][] newcube = DeepClone(ccube); 
    buffer.Enqueue(new State(newcube, calg + face + " ")); //even though newcube gets put into array, it ends up changed after ccube changes 

그리고 이것은 배열이 큐의 앞쪽에서 빠져 나올 때 만들어지는 딥 카피입니다. 나는에 추가 할 새로운 국가가 여전히 이전의 상태와 동일합니다 (뭔가 나에게 말한다 내가 너무 많은 복사본을 만들 필요가 없습니다) 배열 그렇게 여러 번 복제 비록

ccube = DeepClone(buffer.Peek().cube); 

. 매 큐브의 모든면을 매번 모든면에서 만들었지 만 큐의 내부에는 2 개의 별개 요소가 있기 때문에 이것을 알고 있습니다.

도움을 줄 수있는 사람에게 미리 감사드립니다.

Answer 1

문제는 배열이 C#에서 변경 가능하다는 것입니다. 즉, 새 배열을 생성하는 대신 기존 배열을 수정하려는 위치에서 요소를 변경할 때입니다. C#에서 불변이며, 이미 char[][][]로 그 큐브를 대표하기 때문에 당신이 그 사실을 활용할 수

문자열. 경계가있는 직교 3D 공간은 바운드 된 1D 공간에 일차적으로 매핑 (1 : 1)됩니다. 즉, char[][][]은 문자열에 매핑 가능합니다 (큐브의 수명 동안 큐브의 크기가 변경되지 않는 한). 문자열을 사용하면 큐브를 쉽게 깊게 복제 할 수 있습니다. 당신이 이전에 전혀 관련이없는 새로운 큐브를 얻을 것이다 aCube.Clone() 전화, 그래서 당신은 버퍼에 그것을 대기열에 있습니다 때마다

public class Cube 
{ 
    public int Width { get; private set; } 
    public int Height { get; private set; } 
    public int Depth { get; private set; } 

    private string _data; 

    public Cube(int width, int height, int depth) 
    { 
     Width = width; 
     Height = height; 
     Depth = depth; 
     _data = "".PadRight(Width*Height*Depth); 
    } 

    public char Get(int x, int y, int z) 
    { 
     return _data[(Width*Height*z) + (Width*y) + x]; 
    } 

    public void Set(int x, int y, int z, char c) 
    { 
     var sb = new StringBuilder(_data); 
     sb[(Width*Height*z) + (Width*y) + x] = c; 
     _data = sb.ToString(); 
    } 

    public Cube Clone() 
    { 
     return new Cube(Width, Height, Depth) { _data = this._data }; 
    } 
} 

등