인공 지능의 고차원 계획을위한 알고리즘

Question

현재 상담원이 상자를 원래 위치에서 특정 목표 위치로 밀고 당길 필요가있는 인공 지능 프로젝트를 진행 중입니다. 프로젝트는 여러 에이전트를 포함하도록 확장 될 것이므로 에이전트는 실제 구현을 처리하는 동시에 "높은 수준"의 목표를 관리하는 관리자를 보유하게됩니다.

사실상 관리자는 상자를 목표 위치에 놓아야하는 순서를 결정해야합니다. 실제로, 목표 위치에 상자를 넣으면 다른 목표로가는 경로가 차단 될 수 있습니다.

이 문제를 해결하기위한 첫 번째 방법은 "절단 위치"를 고려하는 것입니다. 어떤 위치는 걷기 공간을 두 개의 부분 집합으로 나눈다. 하나는 우리가 대리자를, 다른 하나가 하나 이상의 목표를 가지고있다. 예를 들어, 다음 레벨을 고려하는 "X"는 "A"및 "B"가 박스이다 에이전트이며에서 "A"와 "B"는 각각의 목표 위치에있는이 경우

+++++++++++++++++++++++++++++++++++++++++ 
x      a    b+ 
+++++ +++++++++++++++++++++++++++++++++ 
    +AB + 
    +++++ 

목표 "a"의 위치는 잘린 위치입니다. 상자가 놓여지면 상담원이 목표 "b"에 도달 할 수 없기 때문입니다.

잘라 내기 위치를 계산하는 빠른 알고리즘을 제안 할 수 있으며 각 절단 위치가 차단하는 목표 수를 반환 할 수 있습니까?

Answer 1

는 컷 정점 또는 일반 그래프 조음 포인트이라고합니다. Wikipedia :

특히, 잘라내 기 꼭지점은 연결 요소의 수가 증가하는 모든 꼭지점을 제거한 것입니다.

그리고 조금 더 아래 동일한 문서 :

가

인해 존 홉 크로프트 및 로버트 타잔 (1973)에 접속 무향 그래프 biconnected 성분을 계산하기위한 고전 순차 알고리즘 [1]에서 실행 선형 시간이며, 깊이 우선 검색을 기반으로합니다. 이 알고리즘은 알고리즘 소개 (두 번째 및 세 번째 에디션)의 22-2 번 문제로도 설명됩니다.

두 연결 요소를 결정하면 명료도 점을 쉽게 결정할 수 있습니다. 두 개 이상의 상호 연결된 구성 요소에 포함 된 모든 노드는 관절 지점입니다.

Answer 2

방향을 지정하지 않은 그래프에 영역을 넣을 수 있습니다. 각 노드는지도의 위치이고 위치가 서로 인접하면 두 개의 노드가 연결됩니다. 그런 다음 그래프에서 '자르기 위치'를 표시하고 절단 위치의 상자에 의해 차단되는 모든 경로를 볼 수 있습니다. 당신이 당신의 그리드 단어를 절단 위치를 부르는