heuristic suite

启发式套件

重要说明

该项目不再受到维护。请访问linq以获取A*以获取最新版本。

概述

启发式套件是通用编程中一系列启发式算法的实验实现。该项目的目的是提供一个可以应用于任何难题的基础架构 - 只要可以通过算法解决难题即可。

实施算法：

• 一个*
• 迭代加深A*（IDA*）
• 最好的首次搜索
• 递归最佳首次搜索（RBFS）

该实现完全面向对象，并具有内置的.NET框架比较机制（例如ICOMPARER（T）和IEqualityComparer（T）），以与.NET标准和整个.NET生态系统创建出色的兼容性。源代码可以轻松地带到其他平台，例如Unity和Xamarin。

用算法解决难题

为了将算法应用于难题，需要以下实现：

1. 步骤定义定义拼图步骤的类型将需要实现ISTEP（TKEY）接口。 Key属性有两个目的：

   • 测试两个步骤是否等效。例如：董事会上的同一位置。
   • 比较两个步骤以确定哪些具有更好的分数。例如：位置A和目标之间的距离，以及位置B和目标之间的距离，越接近一个的距离得分更好。

2. 根据Key属性将步骤比较步骤相互比较，以确定哪些具有更好的分数。可以通过以下方式进行比较：

   • 可观的（TKEY）实现。
   • 定制的ICOMPARER（TKEY）实例。
   • 明确给定的h（n）函数，其中参数n是Key 。

3. 可以通过实现INextStepFactory(TKey, TStep)接口或提供NextStepFactory委托来提供当前步骤下一步信息的可用步骤。

之后，可以通过from参数为目标步骤来调用FindSolution方法和goal步骤来运行该算法。如果解决方案存在，则可以通过调用Enumerate方法来获得每个步骤。在枚举开始之前，可以将步骤Reverse d。

启发式比较和离散启发式比较

该项目提供了HeuristicComparer和DiscreteHeuristicComparer ，以用于不同的步骤比较方案。

• 如果可以直接将Key属性相互比较而没有明确的h（n）函数，则默认情况下，将使用DiscreteHeuristicComparer Comparer进行更快的步骤比较。
• 如果要明确需要H（n）函数以比较每个步骤，则HeuristicComparer将用于执行传统估计f（n）= g（n） + h（n） 。

启发式功能偏好

HeuristicFunctionPreference输入枚举使用户能够更改估计的平衡f（n）= g（n） + h（n） 。当两个步骤评估相同的分数时，枚举决定首先考虑哪种功能G（n）或H（n） 。变化的平衡会影响启发式算法的行为。

例子

• 路径查找（algorithmforce.example.pathfinding）

  该示例展示了使用启发式算法来解决的最常见和传统难题。

• 8-Puzzle（Algorithmforce.example.eightpuzzle）

  该示例演示了如何使用启发式算法解决8个式嘴。难题的初始和目标步骤如下：

• 硬币翻转拼图（Algorithmforce.example.coinsflipping）

  此示例演示了游戏AI如何解决硬币翻转拼图。在难题中，只允许一对相邻的硬币同时翻转。所有十枚头脑都是目标。这个难题的灵感来自brine.org。

将来将添加更多示例。

平台

该项目目前针对.NET Core和.NET Framework 4.5或更高。