3
프로젝트에서 작업하면서 그래프 알고리즘 문제가 발생했습니다. 을 풀지 못했습니다. 다음 문제는 :이송 에지에 제약 조건이있는 최단 경로
당신은 감독, 가중 그래프를 가지고 있고 시작 노드와 (매우 Find the shortest path in a graph which visits certain nodes 같은) 노드를 지정 방문하는 동안 끝 노드 사이의 최단 경로를 찾고 싶어요. 그러나 노드와 가장자리와 함께이 그래프에는 노드에있는 "항목"이라는 개념 ( )이 있으며 해당 노드를 입력 할 때 "픽업"합니다. 이제 해당 가장자리에 대해 이라는 필요한 항목을 얻은 경우에만 가장자리가 이 될 수있는 추가 제한 조건이 있습니다. 문을위한 열쇠라고 생각하십시오. 너는 이 문을 통과하기 전에 열쇠를 얻어야한다.
나는 급격하게 폭발하는 무차별 방식 만 생각할 수 있습니다. 누구든지 더 나은 점을 생각하거나이 문제가 해결되는 곳으로 안내 할 수 있습니까? 아니면 이것이 "어렵다"(Computational Speaking)라고 나에게 확신시켜 주겠습니까? 어떤 도움을 주셔서 감사합니다!
얼마나 많은 항목이 있습니까? – templatetypedef
게임의 종류는 게임에 따라 다르지만 (비디오 게임을 탐색하는 데 사용되는 것으로 짐작할 수 있겠지만) 30-40 정도라고합니다. – maxnelso
항목에 좋은 일종의 주문이 있습니까? 즉, 항목은 대략 선형 진행을 따릅니 까? – templatetypedef