그래프에서 걷기 목록이있는 경우 에지 가중치 결정

Question

이 질문은 일련의 데이터를 연속적으로 수행되는 작업 목록과이를 완료하는 데 필요한 총 시간으로 간주합니다. 나는 그들이 적절한 영역 지식에 기초한 몇 가지 초기 추측과 함께 작업의 길이에 관한 유용한 것들을 결정하는 것이 가능한지 궁금해왔다. 나는 그래프 이론이 추상적으로이 문제에 접근 할 수있는 방법이 될 것이라고 생각해 왔으며, 기본적인 것들을 잘 이해하고 있지만, 내가 올바른 방향에 있는지 확실하게 알 수는 없다. 게다가, 나는 그것을 해독하는 것이 꽤 흥미로운 질문이라고 생각한다. 그래서 여기에 우리가 간다 :

1. 는이 가능합니다 감독 가중 그래프에 에지의 가중치를 결정하기 위해, 사이드 산책의 길이 (합계 중량)와 그 그래프의 산책의 목록 주어진? 나는 산책로에서 걸리는 순열의 양과 질이 가능한 모든 대답의 질을 결정할 것이라고 생각하지만 가능한 모든 산책과 길이를 가정 해 봅시다. 명확한 대답이 가능하지 않다면 어떤 종류의 것들이 일 수 있습니까? 그래프에 대해 결론 지어야합니까? 그 결론에 어떻게 도달하겠습니까?

2. 아마도 길이가 다른 여러 개의 유사한 산책이 있었다면 어떻게 될까요? 취할 다른 경로에 대해 충분한 순열이 주어지면 각 에지에 대해 적절한 평균 (또는 다른 예시적인 측정치)을 계산할 수 있습니까? 사용 가능한 데이터 집합에서 일부 순열을 어떻게 할인하여 계산의 정확도에 영향을 줍니까?

3. 마지막으로, 가중치에 대한 초기 추측 세트가 있고 주어진 산책을 사용하여이를 수정해야한다면 어떻게 될까요? 귀하의 추측 능력을 향상시키고 추가 정보를 어떻게 적용 할 수 있습니까?

편집 : 일반 선형 대수 접근의 어려움에 대한 설명. 다음과 같은 일련의 작업을 고려하십시오.

a = 5 
b = 4 
b + c = 5 
a + b + c = 8 

이 값을 사용하는 행렬 방정식은 해결할 수 없지만 조건을 추정하고 싶습니다. 시나리오 3과 같이 유용한 초기 데이터가있을 수 있으며, 어떤 경우에는 업무의 길이가 부정적 일 수 없다는 것과 같은 현실 세계에 대한 지식을 적용 할 수 있습니다. 우리가 합리적인 견적을 얻는 방법에 대한 아이디어가 있는지, 그리고 우리가 알지 못하는 것을 알고 있는지, 예를 들어 알고 있는지 알고 싶습니다. ~에서 알 수있는 데이터가 충분하지 않은 경우 b.

Answer 1

선형 대수학의 응용 프로그램처럼 보입니다.

해결해야 할 선형 방정식이 있습니다. 변수는 태스크의 길이 (또는 에지 가중치)입니다.

예를 들어 작업 길이가 3 작업의 경우 t1, t2, t3 인 경우.

그리고 당신은

t1 + t2 = 2 (task 1 and 2 take 2 hours) 

t1 + t2 + t3 = 7 (all 3 tasks take 7 hours) 

t2 + t3 = 6 (tasks 2 and 3 take 6 hours) 

해결 주어진다는 t1 = 1, t2 = 1, t3 = 5을 제공합니다.

임의의 선형 대수 기술 (예 : http://en.wikipedia.org/wiki/Gaussian_elimination)을 사용하여 이러한 문제를 해결할 수 있습니다. 이는 고유 솔루션, 솔루션 또는 무한한 수의 솔루션이 있는지를 알려줍니다 (다른 가능한 방법은 없음).

선형 방정식에 해가 없다면 행렬의 작업 가중치/계수 중 일부에 매우 작은 난수를 추가하고 다시 해보기를 시도 할 수 있습니다.(나는 Perturbation Theory에 해당한다고 믿는다). 행렬은 값의 작은 변화로 급격하게 변화하는 동작으로 유명하기 때문에 대략적인 답변을 합리적으로 얻을 수 있습니다.

어쩌면 각각의 걷기에 (즉, 더 많은 변수를 추가하여) 느슨한 작업이 몇 가지 선형 제약 조건을 만족시키는 새로운 방정식에 대한 해결책을 고를 수 있습니다 (예 : 0 < s_i < 0.0001 및 s_i의 합을 최소화하십시오.) Linear Programming 기술을 사용하십시오.

Answer 2

각 가장자리를 나타낼 수있는 임의의 문자가 무제한이라고 가정합니다.

(0, a, b, c, d 등)

w는 0, a, b, c, d, e 등의 모든 산책의 목록입니다.

I = 1

#W가 [I]가 1 ~ = 다음

승 바꾸면 [2] w의 길이와 [I], 마이너스 w 다른 모든 값.

영원히 반복하십시오.

예 :

0, A, B, C, D, E 50

0, A, C, B, E 20

0, C, E 10

따라서 :

가 첫 번째입니다. "a"의 모든 인스턴스를 50, -b, -c, -d, -e로 바꿉니다.

새로운 데이터를, 하나의 값이 남아까지

50, 50

50, -b, -d, 20

0, C, E 10

하고, 반복 너 끝나고! 또는 첫 번째 숫자는 각 산책 길이에서 간단히 뺄 수 있습니다.

Answer 3

내가 벡터로 작업 목록을 그래프 잊고 치료 것 -. 구성 요소로 표현되는 모든 작업을 동일한 값으로이 경우 완료하는 데 비용 (시간에 작업에

는 처음에 다른 orderes에, 여기서 도메인 지식을 사용하여 정규 형식으로 변환하고 도메인 지식을 통해 비용의 비율이 주문/타이밍에 의해 일정한 영향을 받게된다고 알려주면 승수를 할당 할 수 있습니다. 타이밍은 암시적인 초기 주문이지만 시간의 함수를 만들어야 할 수도 있습니다 (점심 시간 대 자정에 운전). 기능은 표 형식/이형 형식 일 수 있습니다. 일반적으로 비율과 상대적인 편향 (무언가를하는 것)을 평가하는 것이 훨씬 쉽습니다. 반복을 수행하려면 기능적 언어가 필요할 수 있습니다 d는 로맨틱 지식과 규칙이 바뀔 수있을 때까지 벡터를 다시 작성합니다.

cannonical vector를 사용하면 작업의 유무 (이 반복에 대해 단지 0 | 1)를 고려하고 최소한의 차이 (단일 작업 diffs 먼저)를 찾아보고 작은 수의 추정치를 제공합니다. 이것을 재귀 적으로 계속하고, 추적하고, 선량이나 견적의 질에 대한 경험적 규칙을 지금까지 추적 할 준비를하십시오. 당신이 추적 한 좋은 "라운드"를 추적하십시오.

최소 기약 상태에 도달하면 모든 벡터가 동일한 나머지 작업을 수행 할 수 있습니다. 그런 다음 분산, 평균, 중앙값과 같은 기본 통계를 수행하고 큰 이상 치와 초기 도메인을 개선하는 방법을 찾을 수 있습니다 지식 기반 견적은 cannonical 양식으로 이어집니다. 당신이 많은 것을 열심히하고 새로운 규칙을 추론 할 수 있다면, 처음부터 모든 과정을 시작하고 시작하십시오.

예, 비용이 많이들 수 있습니다 .-)