몇 개의 셀에 유한 값이 있습니까?

Question

프로그래밍 질문이 한 번 발생했습니다.

나는 N 개의 세포가 있다고 생각해.이 세포는 정수 값이나 표현식을 가질 수있다. T 반복 횟수의 반복이있을 수 있습니다. 모든 반복에서 일부 셀을 업데이트 할 수 있습니다. 반복마다 얼마나 많은 셀이 유한 값 (결정할 수 있음)을 가지고 있는지 말해야합니다.

예를 들어, N = 5이면 5 개의 셀은 A, B, C, D, E가 될 수 있습니다. A = 4, B = D + E, C = 2 * B, D = 6, E = A + B 다음과 같은 값이 있다고 가정하십시오.이 경우 두 개의 셀 (A와 D) 4, 6입니다. B, C 및 E의 값은 결정할 수 없습니다. B는 E에 따라 달라지며 B는 순환 직접 종속성에 종속됩니다. 반면에 C는 미정 인 B에 의존한다.

이제 D를 D + E 대신 B로 10 업데이트하면 모든 셀이 유한 값을가집니다. A (4), B (10), C (20), D (6), E (14). 셀의 각 반복 값에서 변경할 수 있습니다.

제약 조건 : (1 '<'N = 200 <, 1 < 'T'= 1000 <)

내가 시도하는 것 : 모든 cell.For 위해 list.If 의존성 각각의 반복 갱신을 종속 목록을 확인 미확인 된 하나의 요소를 포함하고,이 반복에서이 셀은 유한 값을 가질 수 없습니다. 더 좋은 방법이 있습니까?

Answer 1

본능적으로, 나는 모든 방법을 사용하여 적절한 의존성 그래프를 작성했습니다. 이것은 유향 그래프입니다. 노드는 노드에 따라 다르면 다른 노드에 가장자리가 있습니다.

노드를 업데이트 할 때 아웃 바운드 가장자리를 제거하고 필요에 따라 다시 작성합니다. 실제 계산 : 각 노드에서 "알려진"것으로 표시된 노드에 마주 칠 때 종단되는 깊이 우선 탐색을 시작한 다음 마크를 뒤로 전파하기 시작합니다. 즉, 노드를 "알려진"것으로 표시합니다. 하위 노드는 이와 같이 표시됩니다.

기본적으로 이것은 솔루션과 동일하다고 생각합니다. 실제 구현에 따라 런타임 성능이 향상 될 수 있으며 시각적으로 더 깨끗한 솔루션이라고 생각합니다. 3 -

만약에 A = 2 * B와 B = A : 헨리의 주석 @에 관한

? 주기적 참조에도 불구하고 에는 A = 6, B = 3이라는 고유 솔루션이 있습니다.

업데이트 후 최적화 단계를 도입 할 수 있습니다. 우리는 사이클을 확인할 수 있습니다. 만약 우리가 사이클을 찾으면, 우리는 방정식의 시스템을 해결함으로써 그것을 해결하려고 할 수 있습니다. 멋지다.