2

n² パス ノードを持つグラフがあり、開始ノードが常に右上隅 (点 A) にあり、終了ノードが常に右下隅 (点 B) にある場合、C# プログラムを作成する必要があります。与えられた n (n <=10 と仮定) で、A から B へのハミルトニアン パスの数を決定します。言い換えると、A で始まり B で終わるすべてのパスを見つける必要があります。ここで、各ノードは 1 回だけアクセスされ、ノード間の移動は左、右、上、下 (対角線なし) に制限されます。

たとえば、n = 5 の場合、考えられるパスの 1 つは、次の図に示すパスになります。

画像

理想的には、いくつかのヒューリスティックを利用するインテリジェントなアルゴリズムを開発したいと考えていますが、今のところ、最初は力ずくの方法を開発する必要があります。幅優先検索を使用すると仮定していますが、C# を使用してそれを実装するためにどこから始めればよいか本当にわかりません。

4

1 に答える 1

0

総当たり攻撃

グラフを作成します。グラフランナーを作成します。すべての実行情報をキャッシュします。ランナーにグラフを再実行させ、実行情報からすべての決定を除外します。ランナーが実行できなくなったら、キャッシュされたデータをフィルタリングして結果をカウントします。

C＃での実装

nunitのようなテストフレームワークをインストールします。必要な機能のリストを作成します。

機能リストが空になるまで繰り返します。

  • 最小の機能を選択します
  • 失敗したテストを書く
  • テストに合格するためのコードを書く
  • すべてのテストに合格することを確認します
  • prittyにするためのリファクタリング
  • 機能リストからアイテムをクリア

終わり

コメントのいくつかの質問に答えるために編集されました

  • nunitはインターネットからダウンロードできます。お好みのフォルダに解凍してください。
  • 空のコンソールアプリケーションを作成します。
  • NUnitディレクトリを調べてフレームワークを見つけ、そのフレームワークをプロジェクトに追加します。
  • NUnitディレクトリを調べてGUIランナーを見つけ、プロジェクトに追加します。
  • 実際には、コンソールでプロジェクトを実行する必要はありません。フォームを自動作成し、プロパティを開いて、プロジェクトをWindowsアプリケーションとして再宣言するだけです。
  • program.csを以下のコードに置き換えます。
  • コンパイルして実行します。GUIで[実行]をクリックし、例外が発生した場合はF5キーを押します
  • おめでとうございます-あなたはちょうどnunitを使用しました

プログラムは次のとおりです。

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を指定することもできます。そうすれば、例外が発生せず、テストが簡単になります。

機能リストは、単にソフトウェアに実行させたいことです。あなたの場合、あなたは何らかの形で与えられたグラフを提供されます。それはファイルまたは一枚の紙である可能性があります。したがって、1つの機能は、その情報をロードし、そこからグラフを作成することです。あなたが言及した次の機能は、プログラムがn <= 10をチェックし、そうでない場合は動作を拒否する必要があるということです。これも機能です。もう1つは、特定のインターフェイスを介して結果を返すことです。そして最後に重要なのは、実際にすべての接続を見つける機能です。それらを自分でリストする場合は、最も簡単だと思うものを選択して、その1つから始めることができます。

テストするときは、既知のケースのエンドツーエンドのテストを作成することを忘れないでください。グラフを固定し、既知の数を出力します。

ワイルドな仮定を使用すると、グラフはテキストファイルにあり、各行には他の行への接続が一覧表示され、次のようなテストを記述できます。

    [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());
        }
    }

グラフがまだ存在しないため、これはコンパイルされません。ただし、コンパイルしてテストに合格させると、最初の機能が満たされ、最初にテストを記述して次の機能を実装し続けることができます。

于 2012-08-08T12:42:29.583 に答える