시작점과 끝점이 주어진 그래프에서 해밀턴 경로 수를 찾는 프로그램

Question

n2 경로 노드가있는 그래프가 주어지고 시작 노드가 항상 오른쪽 상단 (점 A)에 있고 끝 노드가 항상있는 경우 오른쪽 아래 모서리 (B 점), A에서 B까지 주어진 해밀턴 경로의 수를 결정하는 C# 프로그램을 작성해야합니다 (n은 < = 10으로 가정). 즉, A에서 시작하여 B로 끝나는 모든 경로를 찾아야합니다. 각 경로는 한 번만 방문되며 노드 사이의 이동은 왼쪽, 오른쪽, 위, 아래 (대각선 없음)로 제한됩니다. 예를 들어

, 만약 N = 5, 다음 하나 개의 가능한 경로를 이미지로 도시 한 것이다 : I 어떤 추론을 이용하는 지능형 알고리즘을 개발하고자, 이상적

하지만 지금은 그냥 시작하는 무차별 방식을 개발해야합니다. 폭 넓은 첫 번째 검색을 사용한다고 가정하지만 실제로 C#을 사용하여 구현할 위치를 알 수 없습니다.

Answer 1

일부 무언가의 것

그래프를 작성하십시오. 그래프 러너를 작성하십시오. 모든 실행 정보를 캐시하십시오. 러너가 그래프를 다시 실행하고 Runinformation에서 모든 결정을 제외시킵니다. 주자가 더 이상 실행할 수 없으면 캐시 된 데이터를 필터링하고 결과를 계산합니다.

C에서 구현

nunit과 같은 testframework를 설치하십시오. 필요한 기능 목록을 작성하십시오.

반복 featurelist이 비어 때까지

• 모든 테스트 pritty을 할
• 리팩토링을 통과 할 수 있도록 테스트를
• 을 통과
• 가 실패한 테스트를
• 쓰기 코드를 작성하는 가장 작은 기능을 선택
• 기능 목록의 항목 지우기

는

• You can download nunit from the internet.
  이 원하는 폴더에 압축을 풉니 다 코멘트에 몇 가지 질문에 대답 편집

  ---

  을 수행.
• 빈 콘솔 응용 프로그램을 만듭니다.
• 프레임 워크를 찾으려면 NUnit 디렉토리를 탐색하고 해당 프레임 워크를 프로젝트에 추가하십시오.
• NUnit 디렉토리를 탐색하여 GUI 러너를 찾고 프로젝트에 추가하십시오.
• 우리는 실제로 콘솔로 프로젝트를 실행하고 싶지 않습니다. 폼을 자동 생성하고 속성을 열고 프로젝트를 다시 만들어서 Windows 응용 프로그램으로 만들려하지 마십시오.
• program.cs를 아래 코드로 바꿉니다.
• 컴파일하고 실행하십시오.

  using System; 
  using NUnit.Framework; 
  namespace EC_Connect_Test 
  { 
      class Program 
      { 
       [STAThread] 
       static void Main(string[] args) 
       { 
        string fullPath = System.Reflection.Assembly.GetAssembly(typeof(Program)).Location; 
        NUnit.Gui.AppEntry.Main(new string[] { fullPath }); 
       } 
      } 
       public class MathClass 
       { 
        internal static double Divide(int A, int B) 
        { 
         if (B == 0) throw new DivideByZeroException(); 
         return (Double)A/(Double)B; 
        } 
       } 
  
       [TestFixture] 
       class MyFirstTestClass 
       { 
        [Test] 
        public void DividingTwoIntegersResultIsDouble() 
        { 
         Double expected = 3.3; 
         Double actual = MathClass.Divide(33, 10); 
         Assert.AreEqual(expected, actual); 
        } 
  
        [Test] 
        public void DividingByZeroShouldThrow() 
        { 
         Assert.Throws<DivideByZeroException>(
          () => { MathClass.Divide(33, 0); } 
         ); 
        } 
       } 
  
      } 
  

  또한 외부 NUNIT를 시작하고 그것에게 당신의 debugproject를 제공 할 수 있습니다 : - 예외가

• 축하 오면 GUI 및 F5 키를 눌러 실행을 클릭 방금 NUNIT
여기

을 사용하면 프로그램입니다 디렉토리로. 그런 식으로 예외가 나오지 않고 테스트가 쉬워집니다.

기능 목록은 소프트웨어에서 수행하기를 원하는 기능입니다. 귀하의 경우에는 어떤 형태로 주어진 그래프가 제공됩니다. 파일이나 종이 일 수 있습니다. 그래서 하나의 기능은 그 정보를 로딩하고 그것으로부터 그래프를 만드는 것입니다. 당신이 언급 한 다음 기능은 프로그램이 n < = 10을 확인하고 그것이 작동하지 않으면 기능도 있다는 것입니다. 또 다른 방법은 주어진 인터페이스를 통해 결과를 반환하는 것입니다. 마지막으로 모든 연결을 실제로 찾을 수있는 능력이 가장 중요합니다. 그것들을 스스로 나열하면 가장 쉬운 것으로 생각되는 것을 선택하고 그 것으로 시작하십시오.

테스트 할 때 알려진 케이스의 종단 간 테스트를 만드는 것을 잊지 마십시오. 그래서 고정 된 그래프, 알려진 숫자 밖으로. 그래프는 아직 존재하지 않기 때문에

[TestFixture] 
    class graphloadingSpex 
    { 
     String[] lines = new String[] { 
     "2,3,4", 
     "1", 
     "1,4", 
     "1,3" 
     }; 

     [Test] 
     public void ShouldShowConnectionsAfterLoading() 
     { 
      Graph tested = new Graph(lines); 
      Assert.AreEqual(new String[] { "2", "3", "4" }, tested["1"].GetConnextions()); 
      Assert.AreEqual(new String[] { "1"}, tested["2"].GetConnextions()); 
      Assert.AreEqual(new String[] { "1", "4" }, tested["3"].GetConnextions()); 
      Assert.AreEqual(new String[] { "1", "3" }, tested["4"].GetConnextions()); 
     } 
    } 

이 컴파일되지 않습니다 :이 같은 테스트를 작성할 수있는 그래프는 각 라인의 목록을 다른 라인에 대한 연결을 인도 표준시 TEXTFILE에있는 야생 가정을 사용

. 그러나 컴파일하고 테스트를 통과하면 첫 번째 기능을 만족할 수 있으며 테스트를 먼저 작성하여 다음 기능을 구현할 수 있습니다.