최대

Question

는 예를 들어,이 노드 가중 된 그래프를 가지고 노드 가중치 그래프 연결된 서브 그래프을 N은-noded :

• 정확히 하나의 노드를 포함하는 최대 서브 그래프 (및 '시작점') 것 정확히 2 노드 (및 '진입 점')를 포함하는 최대 부분 그래프는 14/9가됩니다.
• 정확히 3 개의 노드 (및 '진입 점')를 포함하는 최대 부분 그래프는 3/19 /15
• 정확히 4 노드를 포함하는 최대 서브 그래프 (그리고 '진입 점') 1분의 14/7/240

내가 얻을 수있는 bruteforce보다 더 나은 방법을 생각하고 관리 할 수있을 것 최대 부 그래프.
알려진 효율적인 알고리즘이 없다면, 유전자 알고리즘이 그 경우에 발견 될 것입니까? (교차는 까다로워 보입니다)?

Answer 1

이 문제를 해결하기 위해 Dijkstra's algorithm을 수정할 수 있다고 생각합니다.

Dijkrasta의 알고리즘을 사용하면 최단 경로를 해결할 수 있습니다. 그것을 변경하여 최대 경로를 찾으십시오. 그래프에서 1,2,3 노드로만 제한하려면 "방문"할 때 각 노드에 도달하는 데 필요한 노드 수를 추적하십시오. 찾고있는 노드 수보다 적은 수의 다른 노드가 없을 때 중지하십시오.