통신 "웹"에서 실패 사례를 찾는 알고리즘

Question

필자는 테스트 사례 작성을 더 쉽게하기 위해 노력하고있는 시스템의 여러 가지 실패 사례를 열거하려고합니다. 기본적으로 데이터 "경로"를 통해 임의의 수의 다른 지점과 통신하는 "지점"그룹이 있습니다. 나는 ... 다음과 같은 세 가지 세트의 실패 사례와 함께 올

• 설정 한 원하는 - 시스템의 각 점 P를 들면 있도록 경로를 깰 - 개별적으로 (사소한) 각 경로
• 세트 2 브레이크 P는 시스템의 나머지 부분과 완전히 분리됩니다 (또한 간단합니다).
• 세트 3 - 시스템의 각 포인트 P에 대해 시스템이 두 개의 포인트 그룹 (A와 B, 포인트 P) 그룹 A에서 그룹 B로가는 유일한 방법은 포인트 P를 통과하는 것입니다 (즉, 포인트 P를 통해 시스템의 모든 데이터 트래픽을 강제로 유지하여 계속 유지할 수 있습니다). 특정 지점에 대해 이것이 가능하지 않으면 건너 뜁니다.

세트 3은 내가 문제가있는 것입니다. 실제로, 내가 다루고있는 시스템은 작고 단순하여 솔루션을 "무차별 적으로"만들 수 있습니다 (일반적으로 약 12 ​​포인트, 각 포인트가 1-4 포인트에 연결됨). 그러나 누군가가 시작해야 할 위치에 대한 제안이나 아이디어가있는 경우이 유형의 문제에 대한보다 일반적인 알고리즘을 찾는 데 관심이 있습니다.

Answer 1

여기에 몇 가지 psuedocode가 있는데, 경로를 가정 할 때 "경로"의 "점"과 "모서리"에 대해 노드를 "노드"로 대체하십시오. graph theory 전철기 .

for each P in nodes: 
    for each subset A in nodes - {P}: 
     B = nodes - A - {P} 
     for each node in A: 
      for each edge out of A: 
       if the other end is in B: 
        break edge 
     run test 
     replace edges if necessary 

내가 뭔가를 오해하고있어 않는 한, 문제는 당신이 nodes- {P}의 부분 집합을 생성하는 방법이 비교적 간단 보인다. 다른 검사를하지 않으면 각 파티션 [A, B]가 두 번 테스트됩니다.

Answer 2

'색칠하기'(영국 또는 미국 기사를 원하는지 여부에 따라 u 유무와 상관없이) 일반적인 알고리즘이 있습니다. 그러나 이것은 상대적으로 간단한 문제에 대한 과잉 공격입니다.

은 간단히 다음 의사 코드에서 두 세트 사이의 노드를 분할 :

foreach Node n in a.Nodes 
    foreach Edge e in n.Edges 
     if e.otherEnd in b then 
       e.break() 
       broken.add(e) 

broken.get(rand(broken.size()).reinstate() 

어느 것이 한 번 나에 대한

반복에 하나를 복원 체계적으로 복원하기 위해 깨진 링크를 chosse, 또는 할 랜드를 사용 (또는 한 방향의 끊김이 다른 방향에 영향을 주도록 구조하십시오)