제목에서 이것을 설명하는 데 정말 어려움이 있습니다. 그러나 더 긴 형식으로 진행해 보겠습니다.부정적인 순환을 활용하여 그래프의 두 노드 간의 영/음의 가중치를 찾습니다.
저는이 문제에 정말 곤두박질이났습니다. 답변을 찾는 것이 아니라 약간의 도움이나 특정 주제에 대해 알아볼 것입니다.
나는 가중치와 양수 모두 다양한 가중치의 가장자리가있는 방향성 그래프입니다. 내가하려고하는 것은 그래프에 위치한 두 개의 노드와 함께 제공되는 알고리즘을 작성하는 것입니다 (연결되어 있다고 가정하면) 경로의 총중량이 0 또는 음수가되도록 경로를 찾습니다. 경로는 노드를 여러 번 포함 할 수 있습니다 (경로가 포함 된 가장자리의 양수를 오프셋 할 수 있기를 바랍니다).
저는 현재 Russel과 Norvig의 Artificial Intelligence를 읽고 있지만, 문제의 원인에 따라 텍스트의 논리를 적용하는 방법을 찾기 위해 고심하고 있습니다. 알고리즘은 지속적으로 부정적인 사이클을 진행합니다. 나는 이것을 위해 Backtrack 및 AStar와 같은 메소드를 활용하는 방법을 완전히 이해하지 못하고있다.
누가 내 문제를 더 잘 이해하는 데 도움이 될 수있는 올바른 방향으로 나를 지적 할 수 있다면 큰 도움이 될 것이다. DFS와 BFS 및 그래프와 관련된 많은 다른 것들을 다루는 것은 괜찮지 만, 두 노드 사이의 경로를 체중 제한으로 찾아야 만하는 것이 정말 당황 스럽습니다.
덕분에 내가 샘플 그래프를 포함 시켰습니다 아래
, 나는 경로의 총 중량이 제로를 초과하지 않는 목표로 시작에서 경로를 찾을 수 있어야합니다.
예 그래프 http://i144.photobucket.com/albums/r166/ZooropaTV/bu.jpg
그냥 내 목표 중량 최단 경로를 찾는 것에 대해 필요하지 않기 때문에 내가 해왔 탐색/독서의 많은이 잘못되었습니다 것을 깨달았지만, 방문하여 노드 필요한 최소 수는 지금은 그것에 대해 다른 생각을 가질 필요가 있지만, 아직도 내가 당신이 원하는이 생각하는 어떤 조언을
'네트워크 흐름 : 이론, 알고리즘 및 응용 프로그램'이 중요 할 수 있습니다. – Stephan