각 벡터에 음수가 아닌 항목 만있는 벡터 가중치가있는 강하게 연결된 다이 그래프가 있습니다. 가중치의 합과 대각선 벡터 ([1, 1, 1, ... 1]) 사이의 각도가 최소화되도록 사이클을 찾고 싶습니다. 이런 종류의 알고리즘에 대한 알고리즘이 있습니까?그래프 이론 : 벡터 가중치가있는 최단 경로
은 내가 벨만 - 포드 형 알고리즘은 나에게 매우 좋은 해결책을 줄 것이다 매우 확신 해요,하지만 나는 그것이 -... - 최고의까지 내가 이해로
호를 여러 번 사용할 수 있으므로이 문제는 quadratic program으로 공식화 할 수 있습니다. 인스턴스가 크지 않다면 Wikipedia가 링크하는 솔버 중 하나를 시도해 보는 것이 좋습니다.
가능한 순환을 순환 X, 즉 단순 사이클의 양의 선형 조합으로 보겠습니다. A를 호에서 벡터로의 선형 맵을 나타내는 행렬이라고합시다. 작은 대수학으로 입증 된 한 가지 트릭이 있습니다 : 모든 것 벡터에 대한 Ax의 각도를 최소화하는 대신 Ax의 길이와 모든 1의 벡터가 1 인 제약 조건에 따라 Ax의 길이를 최소화합니다.
이제 2 차 프로그램을 작성할 수 있습니다.
는minimize y1^2 + ... + yn^2 (positive semidefinite objective)
subject to
Ax - y = 0
x is a circulation
마지막 제약 정점 들어가는 호에 x 값의 합이 이탈 호에 x 값의 합에 해당된다는 각 정점 선형 제약 x >= 0과 같이 분해.
아, 좋은 오래된 이차 프로그래밍. 어떻게 수학 학위를 받았으며이 문제를 결코 접할 수 없었습니까? 고마워, 가장 도움이되었다.이것이 제대로 작동 할 것이라고 확신하지만 읽는 사람들에게는 조금 다른 방식으로 접근 할 것입니다. M = [A | d는 [1, 1, ..., 1]^T이고 y = [x^T, k]^T 일 때 완벽하게 정렬 된 해는 M * y = = 0은 항상 해결책이있는 것은 아니기 때문에 M * y = r 및 y> = 0 일 때 rr을 최소화 할 수 있다고 지시합니다. – DomJack
@DomJack 순수한 수학인가요? 적용된 유형과는 달리 컴팩트 세트에서 연속 기능을보고 하루를 호출하는 경향이 있습니다. –
음수, 적용됩니다. '그래프 이론'과 '분석'과 같은 용어는 들었지만 모델링에 중점을 두었습니다. 그래도 여전히 유용합니다. 오해하지 마세요. 제가 지금 읽고있는 대부분의 위키피디아 페이지의 기본 개념을 실제로 파악할 수 있습니다. 검색 용어가 무엇인지 모를 때 저를 잘 알려진 크리크에 올려 놓습니다. ;) – DomJack
될 것이라고 확신 아니에요 Bellman-Ford Algo Dijkstra 최단 경로 Algo도 마찬가지입니다. 그러나 그것은 욕심 많은 행동의 길이다.
편집 : Dijkstra는 음수가 아닌 항목에서만 작동합니다. 그러나 그것은 당신의 문제에 맞을 것입니다.
아니, 그렇지 않을 것이다. 벡터의 모든 엔트리가 양수이지만, 합계 사이의 각도는 다른 벡터의 추가로 감소 할 수 있습니다. [1, 0]과 [0, 1] 벡터의 경우를 생각해 보자. ([0, 1]과 [1, 1]) 사이의 각도 = pi/4 각도 (([0,1] + [1, 0])와 [1, 1])의 각도 = 0 참고 위의 예는 분명히 2D이지만 ND로 일반화 할 수 있기를 원합니다. – DomJack
공통 버텍스를 공유하는 두 사이클을 고려해보십시오. 양수 p와 q가 있다는 것은 완전히 가능합니다. 그래서 p 번째 사이클에 대한 벡터는 q 번째 사이클에 추가되고 두 번째 사이클에 대한 벡터는 (1,1, ..., 1)의 배수와 정확하게 같습니다. 따라서 간단한 주기로 제한하지 않으면 빠른 알고리즘이 있다고 생각하지 않습니다. 간단한 사이클로 제한하더라도 벡터 x에 해당하는 사이클의 일부와 벡터 c (1,1, ..., 1) -x와 동일한 나머지 사이클을 가질 수 있습니다. 아마도 모든 사이클을 열거하고 확인 만하지 않으면 아마 이것을 알 수있는 방법이 없을 것입니다. 따라서 최적의 솔루션을 원한다면 혹독한 힘을 열거하는 것이 문제를 해결할 수있는 유일한 방법 일 수 있다고 생각합니다.
답변 해 주셔서 감사합니다. 나는 무차별 대입 접근법을 시도했지만 그 결과로 무엇을해야하는지조차 알지 못한다. 그래프에서 모든 단순 사이클을 찾고 관련 에지 벡터를 더할 수 있습니다. (그리고 그 사이클 주변에서 임의의 수의 트립을 수행 할 수 있기 때문에 사이클 간 이동은 무시할 수 있습니다). 각 사이클 벡터 xi에 대해, 합계 (ai * xi) = k * d가되도록 N의 ai를 찾으십시오. 여기서 d = [1,1,1,1]^T 또 다른 방법은 다음과 같습니다. X = [x0, x1, x2, x3, ...]와 a = [a0, a1, a2, ...]의 [X, -d] [ak]^T의 널 공간을 찾는 것입니다. ]^T. – DomJack
이것은 그 자체로는 꽤 사소한 (또는 적어도 문학에서 다루기는 쉽지만), 그러나 여전히 널 공간 벡터를 많이 남겨두고있다. (나의 특별한 문제는 2.5m - 16/approx의 결과로 길이 16의 ~ 2.5m주기 벡터를 가진다. 2.5m 영 공간 벡터). 불행히도 이러한 nullspace 벡터는 적어도 하나의 음수 값을 가지므로 모든 양수 값을 결과로 가져 오는 벡터의 선형 조합을 찾을 필요가 있음을 의미합니다 (나중에 소수점 합리적인 값은 괜찮습니다. 나중에 솔루션을 확장 할 수 있기 때문에). – DomJack
항상 단순한 무차별 대입 접근법이 있습니다. 모든 벡터의 모든 조합을 시도해보십시오.하지만 이것은 엄청나게 비쌉니다. 순환 수에있어 계승 (factorial)인데, 그 자체가 꼭지점 수에 지수 적입니다. 나는 O ((e^N)!) ~ O (e^(N^2)) 알고리즘을 완료 할 수있는 가능성을 공상하지 않는다 ... 그래서 나는 stackoverflow가 무엇을 말해야하는지 생각했다. – DomJack
"벡터와 [1, 1, ..., 1] 사이의 각도가 최소화됩니다."확실히 최적 성 기준을 지정하는 이상한 방법입니다. 약간의 대수 (algebra) 후에 이것은 "sum (x_i)^2/sum (x_i^2) is maximized"와 동등합니다. 이것은 알고리즘으로 이어질 가능성이 더 큽니다. (가장자리를 추가하면 분자보다 분모가 팽창 할 수 있기 때문에 보통의 그래프 검색 알고리즘에는 여전히 적합하지 않지만 ...) –
좋은 지적. 나는이 양식을 사용하고 있었지만 그렇게 생각하지는 않았습니다. 더 깊이 고려해 볼 때, 언제든지 참조 프레임을 회전시킬 수 있습니다. 즉, [1, 0, 0, 0, ..., 0]과 같은 벡터에 대한 투영을 최소화 할 수 있습니다. 지불하는 가격은 이제 벡터 항목이 음수 일 수 있습니다. 따라서 우리는 xi^2/sum (xi^2)을 최소화 한 채로 있습니다. 하나의 합계를 저장합니다. – DomJack
나는 '충분히 좋은'근사를 위해 불평등을 남용 할 때가 왔다는 느낌이 든다. Cauchy-Swarz는 2-norm 계산을 1norm으로 줄이고, 삼각형 부등식은 1-norms의 합을 나타냅니다. – DomJack