2

给定一个具有 n² 路径节点的图，并且假设起始节点始终位于右上角（A 点），而结束节点始终位于右下角（B 点），我需要编写一个 C# 程序确定给定 n 的从 A 到 B 的哈密顿路径数（假设 n <=10）。换句话说，我需要找到从 A 开始到 B 结束的每条路径，其中每个节点只被访问一次，并且节点之间的移动被限制为左、右、上、下（无对角线）。

例如，如果 n = 5，则一种可能的路径将是此图像中显示的路径：

图片

理想情况下，我想开发一种利用一些启发式的智能算法，但现在我只需要开发一种蛮力方法就可以开始了。我假设我使用广度优先搜索，但我真的不知道从哪里开始使用 C# 实现它。

4

1 回答 1

0

一些蛮力的事情

构建图表。构建一个图表运行器。缓存所有运行信息。让运行者重新运行图表并从运行信息中排除所有决策。当跑步者不能再跑步时，过滤缓存的数据并计算结果。

在 C# 中实现

安装像 nunit 这样的测试框架。写下你需要的功能列表。

重复直到特征列表为空：

  • 选择最小的特征
  • 写一个失败的测试
  • 编写代码以通过测试
  • 确保所有测试通过
  • 重构以变得简洁
  • 从功能列表中清除项目

完毕

编辑回答评论中的一些问题

  • 您可以从 Internet 下载 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 并将它作为你的调试项目的目录。这样就不会出现异常并且测试变得更容易。

功能列表只是您希望软件执行的操作。在您的情况下，您会以某种形式获得给定的图表。那可能是一个文件或一张纸。因此，一个功能是加载该信息并从中制作图表。你提到的下一个特性是你的程序应该检查 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());
        }
    }

这不会编译，因为 Graph 还不存在。但是让它编译并通过测试将满足您的第一个功能，您可以通过首先编写测试来继续实现下一个功能。

于 2012-08-08T12:42:29.583 回答