이것은 숙제가 아닙니다."트리"(실제로 DAG)의 요소를 켜고 끄는 깨끗하고 효율적인 알고리즘을 찾고 있습니다.
시각적으로 보면 나무처럼 보이지만 모든 잎은 고유합니다 (데이터베이스에 고유 ID가 있음). 그 위의 계층 구조는 다소 임의적입니다. 각 확인란에는 on, off 및 partial의 3 가지 상태가 있습니다. 나뭇잎은 체크 만하거나 체크하지 않을 수 있습니다. 자녀의 상태는 부모의 상태를 운전해야합니다. 체크 박스를 클릭하면 "토글 (toggle)"하고 필요한 변경 사항을 위 또는 아래로 전달해야합니다. 부분적으로 검사 된 부모를 클릭하면 완전히 검사되어야합니다. 각 어린이는 목록에 대한 포인터를 가지고 있습니다 (나는 이 필요하다면 이것을 세트로 바꿀 수 있습니다). 각 학부모는 알파벳순으로 정렬 된 어린이 목록을 가지고 있습니다. 동시에, 디스플레이 목적으로이 구조는 아래 그림에서 볼 수 있듯이 확장 및 축소 할 수있는 트리입니다.
나는이 알고리즘이 전에 발명되었다고 확신한다. 잎의 수는 2 만개에 이르기 때문에 실제로 성능에 신경을 썼습니다. 하지만 코드를 짧고 가독성있게 희생시키면서 알고리즘의 모든 성능 저하를 막으려 고 노력하지는 않을 것입니다.
나는 원칙적으로 (어디로 가든) 내려 가서 변경해야하는 모든 나뭇잎을 식별해야한다고 생각했습니다. 그 후 나는 걸어 가야한다. 잎 세트에서 영향을받을 수있는 일련의 부모를 알아 내야합니다. 그런 다음 변경해야 할 부모 세트와 해당 값으로 필터링하십시오. 그런 다음 세트에 추가하십시오. 그런 다음 그 노드에서 걸어서 반복해야합니다. 잎과 다른 값을 바꿀 필요가있는 다른 노드가 있으면, 그걸 할 필요가있을 것입니다. 행렬 기반 표현은 너무 비싸다.
저는 C++에 MFC을 사용하여이 문제를 해킹하고 있습니다. 그러나 제 질문은 거의 언어에 구애받지 않습니다. 그러나 알고리즘에 대한 구체적인 구현을 선호합니다. Python, Perl, Scala와 같은 일부 언어는 소매에 너무 현대적인 트릭을 사용합니다. Java, C# (LINQ 빼기)와 같이 좀 더 일반적인 방식을 고수하려고합니다.
코드, 링크, 참조 및 질문을 환영합니다. 이 복잡한 이유
흠 ... 앨리스, 밥, 클레오 파트라는 독특한 문제가 아니니? 나를 혼란스럽게하는 부분은 트리 (표시 용)와 dag (트리의 잎이 완전히 새로운 대상이 아닌 ids를 포함하는)를 모두 가지고 있다는 것입니다. –
@Hamish, DAG를 다루고 있기 때문에 고유한지 여부는 중요하지 않습니다. 고유하지 않으면 집합에 삽입하면 고유 노드로 필터링됩니다. – MSN