그래프와 트리를 사용하면 어떤 문제를 더 쉽게 해결할 수 있습니까?[닫은]
https://stackoverflow.com/questions/2988
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
이 두 가지 데이터 구조로 해결할 수 있는 가장 일반적인 문제는 무엇입니까?
다음과 같은 책에 대한 추천도 있으면 좋을 것 같습니다.
- 구조 구현
- 이를 사용하는 알고리즘의 추론을 구현하고 설명합니다.
해결책
이 질문을 읽으면서 가장 먼저 생각나는 점은 다음과 같습니다. 어떤 유형의 것들이 그래프/트리를 사용합니까? 그런 다음 그것을 어떻게 사용할 수 있는지 거꾸로 생각합니다.
예를 들어 트리의 두 가지 일반적인 용도를 살펴보겠습니다.
- DOM
- 파일 시스템
해당 문제에 대한 DOM 및 XML은 트리 구조와 유사합니다.
그것도 의미가 있습니다. 이 데이터를 정렬하는 방법 때문에 의미가 있습니다..파일 시스템도 마찬가지입니다.UNIX 시스템에는 루트 노드가 있고 아래로 분기됩니다.새 장치를 마운트하면 트리에 연결됩니다.
당신은 또한 스스로에게 다음과 같이 질문해야 합니다.데이터가 이러한 유형의 구조에 속합니까?문제에 적합한 데이터 구조를 생성하면 나머지도 따라옵니다.
더 쉽다는 것은 상대적이라고 생각합니다.트리/그래프를 순회하는 재귀 함수에 능숙합니까?트리의 균형을 맞춰야 한다면 어떻게 해야 할까요?
단어 검색 퍼즐을 푸는 프로그램을 생각해 보세요.단어 검색의 모든 문자를 그래프로 매핑하고 주변 노드를 확인하여 해당 문자열이 단어와 일치하는지 확인할 수 있습니다.하지만 단일 배열로도 동일한 작업을 수행할 수는 없나요?실제로 해야 할 일은 인덱스를 이동하여 문자를 왼쪽과 오른쪽으로 확인하고, 너비만큼 문자의 위와 아래를 확인하는 것입니다.그래프를 사용하여 이 문제를 해결하는 것은 어렵지 않지만 그래프 사용이 불편할 경우 많은 추가 작업과 어려움이 발생할 수 있습니다. 물론 그래프를 사용하는 것을 포기해서는 안 됩니다. 특히 그래프를 배우고 있는 경우에는 더욱 그렇습니다. 그들을.
이것이 여러분이 이러한 구조에 대해 생각하는 데 도움이 되기를 바랍니다.책 추천을 받으려면 다음과 같이 해야 합니다. 알고리즘 소개.
다른 팁
회로도.
컴파일(방향성 비순환 그래프)
지도.그래프로서 매우 컴팩트합니다.
네트워크 흐름 문제.
결정 나무 전문가 시스템의 경우(sic)
결함 발견, 프로세스 개선, 안전 분석을 위한 피쉬본 다이어그램.보너스 포인트를 얻으려면 오류 복구 코드를 다음과 같은 개체로 구현하세요. ~이다 생선뼈 다이어그램.
거의 모든 문제는 그래프 이론의 관점에서 다시 작성될 수 있습니다.농담이 아닙니다. NP 완전 문제에 관한 책을 보면 그래프 작업을 위한 좋은 도구가 있기 때문에 그래프 이론으로 바뀌는 꽤 엉뚱한 문제가 있습니다...
알고리즘 설계 매뉴얼 그래프를 창의적으로 활용한 흥미로운 사례 연구를 담고 있습니다.제목에도 불구하고 이 책은 매우 읽기 쉽고 때로는 재미있습니다.
제가 다니는 대학에는 다음과 같은 강좌가 있습니다. CSE 326.나는 이 책이 그다지 유용하다고 생각하지 않았지만, 프로젝트는 재미있고 일부 간단한 구조를 구현하는 방법을 상당히 가르쳐줍니다.
예를 들어, 나무로 해결되는 가장 일반적인 문제(사용자 수 기준) 중 하나는 휴대폰 문자 입력 문제입니다.반드시 바이너리가 아닌 트리를 사용하여 사용자가 매우 빠르게 입력하는 주어진 숫자 목록에서 나올 수 있는 가능한 단어의 공간을 나타낼 수 있습니다.
Java용 알고리즘:5부 Robert Sedgewick의 저서는 그래프 알고리즘과 데이터 구조에 관한 모든 것입니다.이 책은 일부 그래프 알고리즘을 구현하려는 경우 처음으로 읽어볼 수 있는 좋은 책이 될 것입니다.
게임이나 멀티미디어 애플리케이션에서 그래픽을 그리기 위한 장면 그래프는 트리와 그래프를 많이 사용합니다.노드는 렌더링할 개체, 변환, 컨트롤, 그룹 등을 나타냅니다.
장면 그래프에는 일반적으로 여러 레이어와 속성이 있습니다. 즉, 지정된 순서(레이어)로 그래프의 일부 노드(속성)만 그릴 수 있습니다.장면 그래프의 종류에 따라 두 가지 병렬 구조를 가질 수 있습니다.선언과 인스턴스화.목
@DavidJoiner / 모두:
이전:새로운 버전의 알고리즘 설계 매뉴얼 지금은 언제라도 종료될 예정입니다.
Skiena 교수가 이 책을 개발한 전체 과정은 웹에서도 볼 수 있습니다.
http://www.cs.sunysb.edu/~algorith/video-lectures/2007-1.html
트리는 재귀적 특성으로 인해 함수형 프로그래밍 언어에서 더 많이 사용됩니다.
또한 그래프와 트리는 많은 AI 문제를 모델링하는 좋은 방법입니다.
게임은 종종 게임 세계에서 경로를 쉽게 찾기 위해 그래프를 사용합니다.세계의 그래프 표현에는 경로를 찾기 위해 너비 우선 검색 또는 A*와 같은 알고리즘이 있을 수 있습니다.
그들은 또한 종종 나무를 사용하여 세계 내의 엔터티를 나타냅니다.수천 개의 엔터티가 있고 특정 위치에서 엔터티를 찾아야 하는 경우 목록을 선형으로 반복하는 것은 특히 자주 수행해야 하는 경우 비효율적일 수 있습니다.따라서 해당 영역을 트리로 세분화하여 보다 빠르게 검색할 수 있습니다.선형 공간을 이진 검색으로 효율적으로 검색할 수 있는 것처럼(따라서 이진 트리로 나눌 수 있음), 2D 공간도 다음과 같이 나눌 수 있습니다. 쿼드트리 그리고 3D 공간을 옥트리.
