零、前言

在一切都由技术和数据驱动的现代世界中，人工智能变得越来越重要，它是使任何系统或流程自动化的过程，以自动执行复杂的任务和功能，从而实现最佳生产率。

面向初学者的 Java 人工智能实践解释了使用流行的基于 Java 的库和框架来构建智能应用程序的人工智能基础。

这本书是给谁的

面向初学者的 Java 人工智能实践面向希望学习人工智能基础知识并扩展其编程知识以构建更智能应用的 Java 开发人员。

从这本书中获得最大收益

这本书的先决条件是，你应该对人工智能有所了解，你应该上过人工智能的课程，你应该有 Java 的工作知识。

本书有以下软件要求:

• NetBeans 8.2
• Weka 3.8
• SWI-Prolog 7.2-7.6

本课程已在以下系统配置上进行了测试:

• 操作系统:Windows 7、Windows 10、macOS、Ubuntu Linux 16.04 LTS
• 处理器:双核 3.0 GHz
• 内存:4 GB
• 硬盘空间:200 MB

下载示例代码文件

你可以从你在www.packtpub.com的账户下载本书的示例代码文件。如果你在其他地方购买了这本书，你可以访问 www.packtpub.com/support 的并注册，让文件直接通过电子邮件发送给你。

您可以按照以下步骤下载代码文件:

1. 在www.packtpub.com登录或注册。
2. 选择支持选项卡。
3. 点击代码下载和勘误表。
4. 在搜索框中输入图书名称，然后按照屏幕指示进行操作。

下载文件后，请确保使用最新版本的解压缩或解压文件夹:

• WinRAR/7-Zip for Windows
• 适用于 Mac 的 Zipeg/iZip/UnRarX
• 用于 Linux 的 7-Zip/PeaZip

该书的代码包也托管在 GitHub 上的**GitHub . com/packt publishing/Hands-On-Artificial-Intelligence-with-Java-for-初学者** 。如果代码有更新，它将在现有的 GitHub 库中更新。

我们在也有丰富的书籍和视频目录中的其他代码包。看看他们！

使用的惯例

本书通篇使用了许多文本约定。

CodeInText:表示文本中的码字、数据库表名、文件夹名、文件名、文件扩展名、路径名、伪 URL、用户输入和 Twitter 句柄。下面是一个例子:“我们将应用的过滤器将是来自unsupervised.attribute包的一个非监督过滤器。”

代码块设置如下:

Remove rmv = new Remove();
rmv.setOptions(op);

任何命令行输入或输出都按如下方式编写:

 ?- grandfather(X, Y). 

粗体:表示一个新术语、一个重要的单词或您在屏幕上看到的单词。例如，菜单或对话框中的单词出现在文本中，如下所示。下面是一个例子:“转到 Libraries | Add JAR/Folder 并提供junit.jar文件的位置。”

警告或重要提示如下所示。

提示和技巧是这样出现的。

取得联系

我们随时欢迎读者的反馈。

总体反馈:发送电子邮件feedback@packtpub.com，在邮件主题中提及书名。如果您对本书的任何方面有疑问，请发邮件至questions@packtpub.com联系我们。

勘误表:虽然我们已经尽力确保内容的准确性，但错误还是会发生。如果你在这本书里发现了一个错误，请告诉我们，我们将不胜感激。请访问 www.packtpub.com/submit-errata，选择您的图书，点击勘误表提交表格链接，并输入详细信息。

盗版:如果您在互联网上遇到我们作品的任何形式的非法拷贝，如果您能提供我们的地址或网站名称，我们将不胜感激。请通过copyright@packtpub.com联系我们，并提供材料链接。

如果你有兴趣成为一名作家:如果有你擅长的主题，并且你有兴趣写书或投稿，请访问 authors.packtpub.com。

复习

请留下评论。一旦你阅读并使用了这本书，为什么不在你购买它的网站上留下评论呢？潜在的读者可以看到并使用您不带偏见的意见来做出购买决定，我们 Packt 可以了解您对我们产品的看法，我们的作者可以看到您对他们的书的反馈。谢谢大家！

更多关于 Packt 的信息，请访问packtpub.com。

一、人工智能和 Java 简介

在这一章中，我们将讨论什么是机器学习，为什么我们要进行机器学习，什么是监督学习，什么是无监督学习。我们还将了解分类和回归的区别。接下来，我们将开始安装 JDK 和 JRE，还将在我们的系统上设置 NetBeans。在本章的末尾，我们将下载一个 JAR 文件并用于我们的项目。

因此，我们将在本章中讨论以下主题:

• 什么是机器学习？
• 分类和回归的区别
• 安装 JDK 和 JRE
• 设置 NetBeans IDE
• 导入 Java 库并将项目中的代码导出为 JAR 文件

让我们开始，看看有监督和无监督学习相关的 AI 问题是什么。

什么是机器学习？

机器学习的能力实际上是添加新知识或提炼先前知识的能力，这将帮助我们做出最佳或最优决策。注意以下，根据经济学家和政治学家，希尔伯特·西蒙:

“学习是系统根据经验提高性能的任何过程。”

计算机科学家、卡耐基梅隆大学 ( CMU )的 E. Fredkin 大学教授 Tom Mitchell 给出了一个标准定义，如下所示:

“一个程序被认为从经验 E 中学习关于某类任务 T 和性能测量 P。如果它在 T 中的任务的性能，如 P 所测量的，随着经验 E 而提高，那么它是机器学习。”

这意味着，当我们在人类专家的帮助下拥有某些数据和经验时，我们能够对这些特定的数据进行分类。例如，假设我们有一些电子邮件。在人类的帮助下，我们可以过滤垃圾邮件、商业邮件、营销邮件等等。这意味着我们正在根据我们的经验对我们的电子邮件进行分类，任务 T 的类别是我们分配给电子邮件的类别/过滤器。

考虑到这些数据，如果我们训练我们的模型，我们可以制作一个根据我们的偏好对电子邮件进行分类的模型。这是机器学习。我们可以随时检查系统是否已经完美学习，这将被视为一种性能测量。

这样，我们将以电子邮件的形式收到更多的数据，我们将能够对它们进行分类，这将是对数据的一种改进。有了从新数据中获得的经验，系统的性能将会提高。

这是机器学习的基本思想。

问题是，我们为什么要这么做？

我们这样做是因为我们想要开发手工构建起来太困难或太昂贵的系统——无论是因为它们需要针对特定任务的具体技能或知识。这就是所谓的知识工程瓶颈。作为人类，我们没有足够的时间来为每一件事情制定规则，所以我们看数据，我们从数据中学习，以便让我们的系统根据从数据中学习来预测事情。

下图说明了学习系统的基本架构:

在上图中，我们有一个老师，我们有数据，我们给它们添加了标签，我们还有一个老师分配了这些标签。我们将它交给一个学习器组件，它将它保存在一个知识库中，从中我们可以评估它的性能并将其发送给一个性能组件。在这里，我们可以有不同的评估方法，我们将在下一章中看到，使用这些方法，我们可以向学习组件发送反馈。随着时间的推移，这个过程可以得到改进和发展。

下图展示了我们的监督学习系统的基本架构:

假设我们有一些训练数据。在此基础上，我们可以做一些预处理，并提取重要的特征。这些特征将被赋予给一个学习算法，附带一些由人类专家分配的标签。该算法然后将学习并创建一个模型。一旦模型被创建，我们就可以获取新数据，对其进行预处理，并从中提取特征；基于这些特征，我们然后将数据发送到模型，该模型将在提供决策之前进行某种分类。当我们完成这个过程，当我们有一个人给我们提供标签时，这种学习就被称为监督学习。

另一方面，还有无监督学习，如下图所示:

在无监督学习中，我们提取数据，然后在将数据交给学习算法之前对进行特征描述，但是没有任何类型的人为干预来提供分类。在这种情况下，机器会将数据分组为更小的簇，这就是模型的学习方式。下一次特征被提取并给予模型时，模型将为我们提供属于聚类 1 的四封电子邮件，属于聚类 3 的五封电子邮件，等等。这被称为无监督学习，我们使用的算法被称为聚类算法。

分类和回归的区别

在我们的分类系统中，我们有用于训练模型的数据。在将电子邮件分类成簇的情况下，离散值与数据一起提供，这被称为分类。

监督学习还有另一个方面，我们不是提供一个离散的值，而是提供一个连续的值。这被称为回归。回归也被认为是监督学习。分类和回归的区别在于，前者有离散值，而后者有连续的数值。下图说明了我们可以使用的三种学习算法:

如上图所示，我们使用了监督学习、非监督学习和强化学习。当我们谈到监督学习时，我们也使用分类。在分类中，我们执行诸如识别欺诈检测、图像分类、客户保持和诊断等任务。在回归，我们进行广告人气预测、天气预报等活动。在强化中，我们执行游戏 AI 、技能习得等等。最后，在无监督学习中，我们有推荐系统和机器学习的不同子领域，如图所示。

安装 JDK 和 JRE

由于我们将用 Java 编码，我们将需要 Java 开发工具包 ( JDK )。JDK 是一个由编译器和解释器组成的环境。编译器用于将高级语言编写的源代码转换为中间形式，即字节码。这意味着 JDK 编译整个代码并将其转换成字节码。一旦你有了字节码，你就需要一个 Java 解释器，这就是所谓的 Java 运行时环境 ( JRE )。JRE 只为您提供 Java 解释器。如果您有一个 JRE 和字节代码，您可以在您的系统上运行它，如下图所示:

我们现在将 JDK 下载到我们的系统。

打开浏览器，进入链接www . Oracle . com/tech network/Java/javase/downloads/index . html。在这里，您将获得一个下载 Java 的选项。目前，NetBeans 支持 JDK 8。我们有 JDK 10，但它不支持 NetBeans。如果您在 JDK 没有 NetBeans，请访问www . Oracle . com/tech network/Java/javase/downloads/JDK-NetBeans-JSP-142931 . html。您必须接受协议，然后根据您的系统，您可以下载 NetBeans 和 JDK，如下面的屏幕截图所示:

如果你只想安装 JDK，你得去 JDK 8 的www . Oracle . com/tech network/Java/javase/downloads/JDK 8-downloads-2133151 . html。这将带您进入下一页，在这里您还可以找到有关 JDK 8 的更多信息，如下所示:

现在，您必须再次接受协议，并根据您的系统要求下载 JDK。

一旦你下载了 JDK，就很容易安装。对于 Windows 和 macOS，你只需右击它。对于 Linux 机器，你可以在 Ubuntu 上使用sudo或apt-get命令。

设置 NetBeans IDE

我们现在将 NetBeans 下载到我们的系统中。访问 https://netbeans.org/downloads/的链接。您应该会看到类似下面的截图:

在这里，您可以找到有关当前 NetBeans 版本(NetBeans 8.2)的信息。您可以下载 Java SE、Java EE 或任何其他 NetBeans IDE 下载包。建议您下载 All bundle，因为它支持所有的技术，如前面的截图所示。你永远不知道什么时候你可能需要它们！

如右上角所示，8.2 是您将下载的当前版本。如果不想下载这个版本，可以下载它的直接前身，也就是 8.1。如果您想下载试验版本，即 alpha 或 beta 版本，请单击 Development。如果您想要下载早于 8.1 的版本，您可以转到存档，这将帮助您下载所需的版本，如下面的屏幕截图所示:

如上图所示，8.2 是 NetBeans 的最新版本。NetBeans 的后续版本有所变化，但我们将使用 8.2 版本。如果你愿意，可以下载旧版本。例如，7.1 和 7.0.1 这样的版本以不同的方式工作，但可以用于较旧的 Java 代码。

一旦你下载了 NetBeans，你会在 Windows 上得到一个.exe文件。你只需要双击它，然后按照说明安装它。在 Mac 上，它会显示为一个.dmg文件；只要点击一下就可以安装了。安装过程很简单，因为你只需按照提示。在 Linux 上，你会得到一个.sh文件。在这里，只需运行 shell 脚本并单击 Next 继续。NetBeans 现在应该已经安装在您的计算机上了！

在安装 NetBeans 之前，请确保您已经安装了 JDK。否则，您将收到一条错误消息，并且 NetBeans 不会安装在您的系统上。

导入 Java 库并将项目中的代码导出为 JAR 文件

我们现在将从互联网上下载一个 JAR 文件，并在我们的项目中使用它来为我们的项目创建一个 JAR 文件。

打开网络浏览器并搜索download a junit.jar。这将带您到一个链接，在那里您可以下载一个 JAR 文件。JAR 文件所在的地方有在线存储库。最可靠的仓库之一可以在 http://www.java2s.com/Code/Jar/j/Downloadjunitjar.htm ?? 找到，在那里你可以下载任何可用的 JAR 文件。如果你点击它，它应该带你到下面的页面:

如前面的截图所示，您会发现junit.jar文件和 JAR 文件中可用的不同类也在列表中。您可以右键单击保存(软盘)符号，将文件保存到您的系统中。

文件下载完成后，将其解压到一个junit.jar文件中。然后，您可以通过以下步骤将其添加到项目中:

1. 在 NetBeans 上创建一个新项目，例如 HelloWorld。
2. 因为新项目没有junit.jar文件，所以右键单击该项目进入 Properties，如下图所示:

3. 转到库|添加 JAR/文件夹选项，并提供此junit.jar文件的位置，如下所示:

4. 完成后，单击打开，它将被添加到您的项目中:

5. 现在 JAR 文件已经添加到项目中，我们可以在一个import语句中使用junit.jar文件。我们还可以import个人包，如下截图所示:

6. 如果您想使用framework中的所有类，您只需编写以下代码:

import junit.framework.*;

7. 现在，让我们使用下面的代码来打印输出Hello World:

package helloworld;

/**
 *
 * @author admin
 */
import junit.framework.*;
public class HelloWorld {

 /**
 * @param args the command line arguments
 */
 public static void main(String[] args) {
 // TODO code application logic here
 System.out.println("Hello World"); 
 } 
}

8. 运行上述代码后，您应该会得到类似于以下内容的输出:

如果您想为这个项目创建一个 JAR 文件，请执行以下步骤:

1. 转到 Run 并选择 Clean and Build Project(hello world)来构建您的项目:

2. 一旦构建HelloWorld项目完成，输出窗口将显示BUILD SUCCESSFUL，如下面的屏幕截图所示:

3. 要检查 JAR 文件是否已创建，请转到 Windows 资源管理器并导航到您的项目位置，这是您从前面的输出中收到的:

4. 打开项目文件夹，在我们的例子中是HelloWorld，然后进入dist文件夹，如下所示:

5. 在dist文件夹中，你会找到 JAR 文件(HelloWorld.jar)，你可以使用，那里会有一个lib文件夹。这将包含被HelloWorld.jar文件使用的junit.jar文件:

这意味着无论何时您在项目中使用任何 JAR 文件，它们都将被存储在 JAR 文件的lib文件夹中。

摘要

在这一章中，我们首先看了有监督学习和无监督学习之间的区别，然后讨论了分类和回归之间的区别。然后我们看到了如何安装 JDK，JDK 和 JRE 之间的区别是什么，以及如何安装 NetBeans IDE。我们还通过将另一个 JAR 文件导入到我们的项目中来创建我们自己的 JAR 文件。在下一章，我们将学习如何搜索和探索不同的搜索算法。

二、探索搜索算法

在这一章中，我们将看看如何执行搜索，我们将涵盖实现搜索算法的基本要求。然后，我们将通过实现 Dijkstra 的算法来练习，然后继续进行启发式搜索，展示如何在搜索算法中使用它们来提高搜索结果的准确性。

特别是，我们将关注以下主题:

• 搜索简介
• 实现 Dijkstra 的搜索
• 理解启发式的概念
• A*算法简介
• 实现 A*算法

搜索简介

让我们看看搜索是什么意思。如果我们想对任何问题进行搜索，我们将需要四个输入，它们被称为状态空间，如下所示:

【S，S，O，G】

上述输入类型可描述如下:

• 一组隐式给定的状态——在搜索过程中可能被探索的所有状态。
• s :开始符号——搜索的起点。
• O :状态转换操作符，指示搜索应该如何从一个节点进行到下一个节点，以及什么转换可用于搜索。这是一份详尽的清单。因此，状态转换操作符跟踪这些穷举列表。
• G :目标节点，指向搜索应该结束的地方。

根据前面的信息，我们可以找到以下值:

• 目标状态的最小成本事务处理
• 向最低成本目标的一系列转变
• 最低成本目标的最低成本交易

让我们考虑下面的算法，它假设所有的操作符都有一个成本:

1. 初始化:设置打开= {s} ，

关闭= {} ，设置 C(s) = 0

2. 失败:如果 OPEN = {} ，失败终止
3. 选择:选择最小成本状态， n ，形成打开，，保存关闭中的 n
4. 终止:如果 n ∈ G ，成功终止
5. 展开:使用 0 生成 n 的后继

对于每个后继者， m ，仅当 m ∉【打开∪关闭】时，在打开中插入 m

设置 C(m) = C(n) + C(n，m)

并将 m 插入开口

如果 m ∈【开∪关】

设置 C(m) = min{ C(m)，C(n) + C(m，n)}

如果 C(m) 已经减少并且 m ∈关闭移动到打开

6. 循环:转到步骤 2

前述算法的每个状态可以描述如下:

1. 初始化:我们初始化算法并创建一个名为 OPEN 的数据结构。我们将我们的开始状态 s 放入这个数据结构中，并再创建一个数据结构 CLOSE ，它是空的。我们将要探索的所有状态都将从打开进入关闭。我们将初始开始状态的成本设置为 0 。这将计算从起始状态行进到当前状态时发生的成本。从开始状态到开始状态的旅行成本是0；这就是我们将它设置为 0 的原因。

2. Fail :在此步骤中，如果 OPEN 为空，我们将失败终止。然而，我们的开不是空的，因为我们有 s 处于我们的开始状态。因此，我们不会以失败告终。

3. 选择状态:这里我们将选择最小代价后继者 n ，从打开中取出，保存在关闭中。

4. 终止:在这一步，我们将检查 n 是否属于 G 。如果是，我们将成功结束。

5. 展开:如果我们的 n 不属于 G ，那么我们需要使用我们的状态转移运算符展开 G ，如下:

   • 如果它是一个新节点， m ，并且我们没有探索它，这意味着它在打开或关闭中都不可用，我们将简单地通过计算其前任的成本加上从 n 到 m 的旅行成本来计算新后继( m )的成本，并且我们将该值放入打开
   • 如果它是打开和关闭的一部分，我们将检查哪一个是最小成本——当前成本或先前成本(我们在先前迭代中的实际成本)——并且我们将保留该成本
   • 如果我们的 m 减少，并且它属于关闭，那么我们将把它带回打开

6. 循环:我们将继续这样做，直到我们的开不为空，或者直到我们的 m 不属于 G 。

考虑下图所示的示例:

最初，我们有以下算法:

n(S) = 12 | s = 1 | G = {12}

在前面的算法中，以下情况适用:

• n(S) 是状态/节点的数量
• s 是开始节点
• G 是目标节点

箭头是状态转换操作符。让我们试着运行这个程序，以检查我们的算法是否有效。

该算法的迭代 1 如下:

第一步:打开= {1} ， C(1) = 0 | 关闭= { }；这里 C(1) 是节点 1 的成本

第二步:打开≦{ }；转到步骤 3

第三步: n = 1 | 打开= { } | 关闭= {1}

第四步:自n∉g；展开 n=1

我们得到 m = {2，5}

{2} ∉【开∪关】 | {5} ∉【开∪关】

C(2)= 0+2 = 2|C(5)= 0+1 = 1|开= {2，5}

循环至步骤 2

迭代 2 如下:

第二步:*打开≦{ }*所以第三步

第三步: n = 5 自 min{C(2)，C(5)} = C(5) ，即1|OPEN = { 2 }|CLOSE = { 1，5}

第四步: n ∉ G 所以展开一步

步骤展开 n = 5 : m = {9}

{9} ∉【开∪关】

C(9) = 1 + 1 = 2 | 开= {2，9}

循环至步骤 2

迭代 3 如下:

第二步:*打开≦{ }*所以第三步

第三步: n = 2 优先于 2(2) 既然先来了| OPEN = {9} | CLOSE = {1，5，2}

第四步: n ∉ G 所以展开一步

步长展开 n = 2 : m = {6，3}

{6} ∉【开∪关】 | {3} ∉【开∪关】

C(6)= 2+3 = 5|C(3)= 2+1 = 3|开= {9，6，3}

循环至步骤 2

迭代 4 如下:

第二步:*打开≦{ }*所以第三步

第三步: n = 9 自 min{C(9)，C(6)，C(3)} = C(9) ，即 2 | OPEN = {6，3} | CLOSE = {1，5，2，9}

第四步: n ∉ G 所以展开一步

步骤展开 n = 9 : m = {10}

{10} ∉【开∪关】

C(10) = 2 + 8 = 10 | OPEN = {6，3，10}

循环至步骤 2

迭代 5 如下:

第二步:*打开≦{ }*所以第三步

第三步: n = 3 自 min{C(6)，C(3)，C(10)} = C(3) ，即 3 | OPEN = {6，10} | CLOSE = {1，5，2，9，3}

第四步: n ∉ G 所以展开一步

步骤展开 n = 3 : m = {4}

{4} ∉【开∪关】

C(4) = 3 + 2 = 5 | OPEN = {6，10，4}

循环至步骤 2

迭代 6 如下:

第二步:*打开≦{ }*所以第三步

第三步: n = 6 优先于 6(5) 因为它先出现 | OPEN = {10，4} | CLOSE = {1，5，2，9，3，6}

第四步: n ∉ G 所以展开一步

步长展开 n = 6 : m = {5，10，7}

{ 5 }∈[开∪闭]| { 10 }∈[开∪闭]| { 7 }∉[开∪闭]

C(7) = 5 + 1 = 6 | OPEN = {10，4，7}

C(5) = min{C(5) ， C(6，5)} = min{1，5 + 5 = 10} = 1

C(10) = min{C(10)，C(6，10)} = min{10，6 + 4 = 9} = 9 | 由于 C(10) 已经减少，检查 C 是否是打开的一部分

循环至步骤 2

第 7 次迭代如下:

第二步:*打开≦{ }*所以第三步

第三步: n = 4 自 min{C(10)，C(4)，C(7)} = C(4) ，即 5 | OPEN = {10，7} | CLOSE = {1，5，2，9，3，6，4}

第四步: n ∉ G 所以展开一步

步进展开 n = 4 : m = {8}

{8} ∉【开∪关】

C(8) = 5 + 1 = 6 | OPEN = {10，7，8}

循环至步骤 2

迭代 8 如下:

第二步:*打开≦{ }*所以第三步

第三步: n = 7 自 min{C(10)，C(7)，C(8)} = C(7) ，即 6 | OPEN = {10，8} | CLOSE = {1，5，2，9，3，6，4，7}

第四步: n ∉ G 所以展开一步

步骤展开 n = 7 : m = {11}

{11} ∉【开∪关】

C(11) = 6 + 10 = 16 | OPEN = {10，8，11}

循环至步骤 2

迭代 9 如下:

第二步:*打开≦{ }*所以第三步

第三步: n = 8 自 min{C(10)，C(8)，C(11)} = C(8) ，即 6 | OPEN = {10，11} | CLOSE = {1，5，2，9，3，6，4，7，8}

第四步: n ∉ G 所以展开一步

步长展开 n = 8 : m = {12，7}

{12} ∉【开∪关】| {7} ∈【开∪关】

C(12) = 6 + 15 = 21 | OPEN = {10，11，12}

C(7) = min{C(7)，C(8，7)} = min{6，6 + 5 = 11} = 6

循环至步骤 2

第 10 次迭代如下:

第二步:*打开≦{ }*所以第三步

第三步: n = 10 自 min{C(10)，C(11)，C(12)} = C(10) ，即 9 | OPEN = {11，12} | CLOSE = {1，5，2，9，3，6，4，7，8，10}

第四步: n ∉ G 所以展开一步

步进展开 n = 10 : m = {11}

{11} ∈【开∪关】

C(11) = min{C(11)，C(10，11)} = min{16，9 + 3 = 12} = 12

循环至步骤 2

第 11 次迭代如下:

第二步:*打开≦{ }*所以第三步

第三步: n = 11 自 min{C(11)，C(12)} = C(11) ，即 12 | OPEN = {12} | CLOSE = {1，5，2，9，3，6，4，7，8，10，11}

第四步: n ∉ G 所以展开一步

步骤展开 n = 11 : m = {12}

{12} ∈【开∪关】

C(12) = min{C(12)，C(11，12)} = min{21，12 + 1 = 13} = 13

循环至步骤 2

第 12 次迭代如下:

第二步:*打开≦{ }*所以第三步

第三步: n = 12 | OPEN = {} | CLOSE = {1，5，2，9，3，6，4，7，8，10，11，12}

第四步: n ∈ G 因此成功终止

由于 n 属于我们的目标节点，我们将以成功结束，这将结束我们的搜索。

实现 Dijkstra 的搜索

现在，我们将看看 Dijkstra 搜索算法的代码，我们在搜索简介一节中讨论过。

让我们直接进入代码，看看它是如何工作的。在上一节中，我们首先展示的是顶点；每个顶点都有特定的属性。我们现在将创建一个Vertex类，如下所示:

public class Vertex {
    final private String id;
    final private String name;

    public Vertex(String id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((id == null) ? 0 : id.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Vertex other = (Vertex) obj;
        if (id == null) {
            if (other.id != null)
                return false;
        } else if (!id.equals(other.id))
            return false;
        return true;
    }
@Override
    public String toString() {
        return name;
    } 
}

Vertex类将接受两个值:id和name。然后，我们将包含一个构造函数(用来赋值)和hashCode()方法(用来打印值)。

然后，我们将覆盖一个equals对象，看看我们的两个对象是否相等。如果一个对象是null，我们将返回false；否则，我们就返回true。如果我们没有那个特定的类，或者如果我们没有这个类的对象，我们将返回false。这样做是为了检查我们的位置(我们是否在图的末端)，是否有更多的输出节点，等等。

方法将打印顶点的名称。

然后，我们将拥有Edge类，如下所示:

public class Edge {
    private final String id;
    private final Vertex source;
    private final Vertex destination;
    private final int weight;

Edge类有一个开始顶点和一个结束顶点。因此，我们现在将有一个开始顶点(source)和一个结束顶点(destination)，并且每个Edge将有一个id。每个Edge也将有一个特定的值(与之相关的成本)，我们将把它存储在weight变量中，如下所示:

    public Edge(String id, Vertex source, Vertex destination, int weight) {
        this.id = id;
        this.source = source;
        this.destination = destination;
        this.weight = weight;
    }
    public String getId() {
        return id;
    }
    public Vertex getDestination() {
        return destination;
    }

    public Vertex getSource() {
        return source;
    }
    public int getWeight() {
        return weight;
    }
    //@Override
    public String toString() {
        return source + " " + destination;
}
}

Edge类构造函数将初始化getId()、getDestination()、getSource()和getWeight()的值，它们都将打印出它们对应的值。然后我们将覆盖toString()方法，在这里我们将在目标destination中打印source。

完成后，我们将创建一个Graph类，如下所示:

import java.util.List;

public class Graph {

    private final List<Vertex> vertexes;
    private final List<Edge> edges;

    public Graph(List<Vertex> vertexes, List<Edge> edges) {
        this.vertexes = vertexes;
        this.edges = edges;
    }

    public List<Vertex> getVertexes() {
        return vertexes;
    }

    public List<Edge> getEdges() {
        return edges;
    }

}

Graph类将导入util.List类，它将在vertexes和edges变量中分配一个List<Vertex>和一个List<Edge>。Graph类构造函数将初始化这些值，getVertexes()方法将返回vertexes。getEdges()方法将返回edges，它将是List C类型的Vertex类型。

我们现在准备实施我们的 Dijkstra 算法。我们将import下面的类:

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

然后，我们将使用List和edges创建约束，如下所示:

public class DijkstraAlgorithm {

    private final List<Vertex> nodes;
    private final List<Edge> edges;
    private Set<Vertex> close;
    private Set<Vertex> open;
    private Map<Vertex, Vertex> predecessors;
    private Map<Vertex, Integer> distance;

我们已经为两个数据结构open和close创建了一组顶点(Set<Vertex>)。然后，我们有了Map，在这里我们将记录当前节点的所有前任。所以我们会有Map<Vertex, Vertex>，会花predecessors，也会有成本(distance)。因此，我们将拥有Vertex和Integer，它们将记录特定Vertex的成本。

this构造函数将初始化ArrayList<Vertex>(graph.getVertexes())和ArrayList<Edge>(graph.getEdges())的值，并将graph作为一个对象。graph对象将返回我们的顶点和边，getVertexes()将返回我们的顶点和边，它们将被转换成一个ArrayList并被分配给nodes和edges:

    public DijkstraAlgorithm(Graph graph) {
        // create a copy of the array so that we can operate on this array
        this.nodes = new ArrayList<Vertex>(graph.getVertexes());
        this.edges = new ArrayList<Edge>(graph.getEdges());
    }

close和open对象属于HashSet类型，并且distance被初始化为HashMap值。我们将初始化这些值；最初，我们将put的source值作为0，并且我们将把这个起始点分配给一个open数据结构，或者一个open集合。我们将这样做，直到我们的open集合不为空。如果我们的open集合不为空，我们将创建一个Vertex类型的node，我们将得到所有节点的最小值。因此，getMinimum()将遍历open中的顶点，以找到最小值。一旦我们有了来自open的node，我们将把它分配给close，并且我们将把它从open中移除。然后，我们将找到我们特定的node的后代，我们将找到它们的最小值，如下所示:

    public void execute(Vertex source) {
        close = new HashSet<Vertex>();
        open = new HashSet<Vertex>();
        distance = new HashMap<Vertex, Integer>();
        predecessors = new HashMap<Vertex, Vertex>();
        distance.put(source, 0);
        open.add(source);
        while (open.size() > 0) {
            Vertex node = getMinimum(open);
            close.add(node);
            open.remove(node);
            findMinimalDistances(node);
        }
    }

以下代码将查找最小值并将这些值添加到目标中:

    private void findMinimalDistances(Vertex node) {
        List<Vertex> adjacentNodes = getNeighbors(node);
        for (Vertex target : adjacentNodes) {
            if (getShortestDistance(target) > getShortestDistance(node)
                    + getDistance(node, target)) {
                distance.put(target, getShortestDistance(node)
                        + getDistance(node, target));
                predecessors.put(target, node);
                open.add(target);
            }
        }
    }

getDistance()方法获取特定node的距离，以及从node到target的距离。因此，我们将传递这两个值，node和target，这些值将被添加到weight。getWeight()方法将获得weight，并且它将被赋予相同的值。我们将它们添加到target，然后我们将得到node值加上它自己的weight，这将通过getWeight()方法获得:

    private int getDistance(Vertex node, Vertex target) {
        for (Edge edge : edges) {
            if (edge.getSource().equals(node)
                    && edge.getDestination().equals(target)) {
                return edge.getWeight();
            }
        }
        throw new RuntimeException("Should not happen");
    }

我们还有getNeighbors()方法。这里，将打印所有的邻居，如下所示:

    private List<Vertex> getNeighbors(Vertex node) {
        List<Vertex> neighbors = new ArrayList<Vertex>();
        for (Edge edge : edges) {
            if (edge.getSource().equals(node)
                    && !isSettled(edge.getDestination())) {
                neighbors.add(edge.getDestination());
            }
        }
        return neighbors;
    }

getMinimum()方法将检查open中的所有可用值，并将该值传递给vertexes。从vertexes开始，我们将检查minimum值，然后我们将return它:

    private Vertex getMinimum(Set<Vertex> vertexes) {
        Vertex minimum = null;
        for (Vertex vertex : vertexes) {
            if (minimum == null) {
                minimum = vertex;
            } else {
                if (getShortestDistance(vertex) < getShortestDistance(minimum)) {
                    minimum = vertex;
                }
            }
        }
        return minimum;
    }

    private boolean isSettled(Vertex vertex) {
        return close.contains(vertex);
    }

我们还有getShortestDistance方法。这将从一个特定的节点获得最短的距离，并通过它。有了结果，我们可以检查最小距离:

    private int getShortestDistance(Vertex destination) {
        Integer d = distance.get(destination);
        if (d == null) {
            return Integer.MAX_VALUE;
        } else {
            return d;
        }
    }

类似地，getPath方法将从一个节点获得最佳路径，如下所示:

    public LinkedList<Vertex> getPath(Vertex target) {
        LinkedList<Vertex> path = new LinkedList<Vertex>();
        Vertex step = target;
        // check if a path exists
        if (predecessors.get(step) == null) {
            return null;
        }
        path.add(step);
        while (predecessors.get(step) != null) {
            step = predecessors.get(step);
            path.add(step);
        }
        // Put it into the correct order
        Collections.reverse(path);
        return path;
    }

}

现在，我们将创建我们的Test类，其中我们将import以下类:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertTrue;

为了将junit包中的assertNotNull和assertTrue类import，我们需要导入junit.jar和hamcrest-core-1.3.jar包。我们将通过进入我们的项目并右键单击它，到达属性。在“Properties”中，我们将转到“Libraries”并单击“Add JAR/Folder ”,我们将提供 JAR 文件的路径，如下面的屏幕截图所示:

首先，我们将创建nodes和edges，然后我们将初始化它们。然后，我们将提供完整的输入图，如下所示:

public class Test {

    private List<Vertex> nodes;
    private List<Edge> edges;

    public void testExcute() {
        nodes = new ArrayList<Vertex>();
        edges = new ArrayList<Edge>();
        for (int i = 0; i < 12; i++) {
            Vertex location = new Vertex("Node_" + i, "Node_" + i);
            nodes.add(location);
        }

在前面的例子中，我们有 12 个nodes，所以我们将把它们从0初始化为11。我们将使用一个从i = 0到i < 12的for循环，我们将为Vertex创建一个location对象，并将nodes添加到location。

addLane方法将具有边缘，如下面的代码片段所示:

        addLane("Edge_0", 0, 1, 2);
        addLane("Edge_1", 0, 4, 1);
        addLane("Edge_2", 1, 2, 1);
        addLane("Edge_3", 1, 5, 3);
        addLane("Edge_4", 2, 3, 2);
        addLane("Edge_5", 3, 7, 1);
        addLane("Edge_6", 4, 8, 1);
        addLane("Edge_7", 5, 4, 5);
        addLane("Edge_8", 5, 6, 1);
        addLane("Edge_9", 5, 9, 4);
        addLane("Edge_10", 6, 2, 3);
        addLane("Edge_11", 6, 10, 10);
        addLane("Edge_12", 7, 11, 15);
        addLane("Edge_13", 8, 9, 8);
        addLane("Edge_14", 9, 10, 3);
        addLane("Edge_15", 10, 11, 1);
        addLane("Edge_16", 7, 6, 5);

如你所见，在前面的代码中，我们从0到11取值；在这个例子中，我们有从1到12的边。这意味着我们拥有的第一个顶点是第 0 ^个个个顶点，我们拥有的第十二个顶点是前面代码中的第十一个顶点。上述代码片段包括以下内容:

addLane("Edge ID", source, destination, cost) 

因此，从 0 ^第个顶点到第一个顶点，代价为2，从 0 ^第个顶点到第四个顶点，代价为1，以此类推。这就是成本的定义。

接下来，我们将初始化一个graph对象，我们将把nodes和edges传递给它。然后，我们将把graph对象分配给我们的dijkstra对象，并调用dijkstra.execute方法，将第一个节点分配给execute方法。因此，getSource方法将拥有我们拥有的第一个值。最后，顶点getPath将获得整个路径，如下:

        Graph graph = new Graph(nodes, edges);
        DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(graph);
        dijkstra.execute(nodes.get(0));
        LinkedList<Vertex> path = dijkstra.getPath(nodes.get(10));

        assertNotNull(path);
        assertTrue(path.size() > 0);

        for (Vertex vertex : path) {
            System.out.println(vertex);
        }

    }

一旦我们实现了前面的代码，我们将使用addLane方法，如下所示:

    private void addLane(String laneId, int sourceLocNo, int destLocNo,
            int duration) {
        Edge lane = new Edge(laneId,nodes.get(sourceLocNo), nodes.get(destLocNo), duration );
        edges.add(lane);
    }
}

addLane方法将接受四个值并调用Edge类的一个lane对象。它将初始化lane对象，并将值传递给该对象，这将创建edges。

现在，执行代码。您将看到以下输出:

我们得到最短路径，从Node_0到Node_1到Node_5到Node_9到Node_10，第 11 个是我们的目标节点。

在介绍搜索的部分的例子中，我们有相同的路径，从顶点1到2到6到10到11，最后到12。这一节举例说明了 Dijkstra 的算法。

理解启发式的概念

让我们来看看启发法；稍后，我们将看一个例子。

启发式是一种解决问题、学习和发现的方法。当我们不确定目标应该是什么时，我们应用启发式；我们可以应用某些估计，这些估计可以帮助我们优化我们的搜索过程。如果找到最优解是不可能的或不切实际的，可以使用启发式方法来加快找到满意解的过程。

所以，让我们看一个使用启发式的例子。

假设我们有一个由八块瓷砖组成的拼图，按初始状态立方体所示排列，我们想按它们在目标状态立方体中的样子排列它们:

为了使 1 从其初始状态到其目标状态，我们必须将 1 从第一行的第一个图块移动到最后一个图块。

我们还必须移动至少两条边(即 2 和 3 )，这样才能让 1 到达它的目标状态位置。

可能有两种价值:高估和低估。高估是解，是机制，低估是从实际值中得到最小值的机制。因此，我们可以有把握地说，我们需要移动至少两块瓷砖才能将 1 移动到它的实际位置:

类似地，我们需要移动至少一个方块来使 2 到达其实际位置:

我们还可以得到启发值——所有牌的低估值。例如，如果我们想将 8 移动到它的目标状态，我们需要将 1 和 2 移动至少两块瓷砖。这些是我们瓷砖的启发值，这就是启发的工作方式。

A*算法简介

我们现在来看看 A*算法是如何工作的。在这个算法中，我们将计算两个成本。我们将接受四个输入:我们的起始状态(一组隐式给定的状态)、状态转换操作符、目标状态和每个节点的启发值。基于这些，我们将计算我们的实际成本， g(n) (我们也在我们的 Dijkstra 算法中计算过)。除了实际成本，我们还将计算另一个成本:最终成本( f(n) )。最终成本将是实际成本加上启发式成本( h(n) )。公式如下:

在前面的公式中，以下内容适用:

• g(n) 是从初始状态遍历到状态 n 的实际代价
• h(n) 是从状态 n 到达目标的估计成本

我们得到了以下信息:

【S，S，O，G，h】

在前面的语句中，以下内容适用:

• S 是一组隐式给定的状态
• s 是开始状态
• O 是状态转换运算符
• G 是目标
• h 是我们图上的启发函数

我们的目标是找到最小成本，这意味着我们的目标是找到从开始状态到目标状态的最小成本的事务序列。我们的算法将包括以下步骤:

1. 初始化:

设置打开={s} 、
关闭= {} 、设置 f(s) = h(s) 、 g(s) = 0

2. 失败:

如果 OPEN = {} ，以失败终止

3. 选择:

选择最小成本状态， n ，形成打开，保存关闭中的 n

4. 终止:

如果 n ∈ G ，成功终止

5. 展开:

使用 O 生成 n 的后继者。对于每个继任者， m ，仅在开口中插入 m :

设置 g(m) = g(n) + C(n，m)

设置 f(m) = g(m) + h(m)

将 m 插入开口

设置 g(m) = min{g(m)，g(n) + C(m，n)}

设置 f(m) = g(m) + h(m)

如果 f(m) 已经减少并且 m ∈关闭将其移动到打开

6. 循环:

转到步骤 2。

上述算法包括以下步骤:

1. 我们将开始状态导入到 OPEN 中，并创建一个名为 *CLOSE 的空白数据结构；*我们计算 s 的最终状态作为启发式代价，我们的初始，实际代价是 0 。由于我们的实际成本是 0 ，我们的启发式成本将是最终成本。

2. 如果我们的打开为空，我们以失败终止搜索；如果不是，我们将从打开中选择最小成本状态 n ，并将其放入关闭。我们在 Dijkstra 的搜索中也执行了这个操作。

3. 如果我们的当前状态等于目标状态，我们将成功终止。

4. 如果我们没有成功终止，我们将需要生成 n 的继任者。我们将通过两种机制生成 n 的所有继任者，如下所示:

5. 我们将继续这样做，直到我们没有失败或成功。

让我们回顾一下前面的例子。下图显示了前面的示例；这一次，我们可以看到所有节点的启发式成本:

以下是对上述算法的一个基本假设:

第一步:初始化: s=1

开{ 1(12)}
关{ 1)?? g(1)= 0，h(1)=12

因此， f(1)=12

第二步:如果*OPEN = { }；*因失败而终止

自，打开≦{ }；选择最小成本继任者并将其添加到关闭{}

关闭{1(12)}

打开{}

第三步:如果1(12)∈G；成功终止

自 1(12) ∉克

第四步:扩展 1(12) 得到它的后继， m 。

我们得到 m = 2，5

g(2)= 2；h(2)=10 。因此， f(2)= 2+10=12

g(5)= 1；h(5)=12 。因此， f(5)= 1+12=13

因此， m=2(12) 或 m=5(13)

打开{2(12)，5(13)}

转到步骤 2

自开启≦{ }

将最小成本后继 2(12) 添加到关闭

因此，关闭{1(12)，2(12)}

打开{5{13}}

自 2(12) ∉克

展开 2(12) 得到它的后继， m 。

我们得到 m = 3，6

g(3)= 3；h(3)=16 。因此， f(3)= 19

g(6)= 5；h(6)=7 。因此， f(6)= 12

因此， m=3(19) 或 m=6(12)

打开{5(13)，3(19)，6(12)}

转到步骤 2

自开启≦{ }

添加最小成本后继 6(12) 到关闭

因此，关闭{1(12)，2(12)，6(12)}

打开{5{13}，3(19)}

自 6(12) ∉克

展开 6(12) 得到它的后继， m 。

我们得到 m = 5，7，10

自7∉[open u close]:g(7)= 6；h(7)=11 。因此， f(7)= 17

自10∉[open u close]:g(10)= 9；h(10)=4 。因此， f(10)= 13

对于 m=5

由于5∈【OPEN U CLOSE】:g(5)= min { 1，10 } = 1；f(5)=13

打开{5(13)，3(19)，7(17)，10(13)}

转到步骤 2

自开启≦{ }

添加最小成本后继 5(13) 到收盘(由于 5(13) 是在 10(13) 到*开盘之前添加的，*我们会将其视为最小成本后继)

因此，关闭{1(12)，2(12)，6(12)，5(13)}

打开{3(19)，7(17)，10(13)}

自 5(13) ∉克

展开 5(13) 得到它的后继， m 。

我们得到 m = 9

自9∉[open u close]:g(9)= 2；h(9)=12 。因此， f(9)= 14

打开{5(13)，3(19)，7(17)，10(13)，9(14)}

转到步骤 2

自开启≦{ }

添加最小成本后继 10(13) 到关闭

因此，关闭{1(12)，2(12)，6(12)，5(13)，10(13)}

打开{5(13)，3(19)，7(17)，9(14)}

自 10(13) ∉克

展开 10(13) 得到它的后继， m 。

我们得到 m = 11

自11∉[open u close]:g(11)= 2+3+4+3 = 12；h(11)=1 。因此， f(11)= 13

打开{3(19)，7(17)，9(14)，11(13)}

转到步骤 2

自开启≦{ }

添加最小成本后继 11(13) 到关闭

因此，关闭{1(12)，2(12)，6(12)，5(13)，10(13)，11(13)}

打开{3(19)，7(17)，9(14)}

自 11(13) ∉克

展开 11(13) 得到它的后继， m 。

我们得到 m = 12

自12∉[open u close]:g(12)= 13；h(12)=0 。因此， f(12)= 13

打开{3(19)，7(17)，9(14)，12(13)}

转到步骤 2

自开启≦{ }

添加最小成本后继 12(13) 到关闭

因此，关闭{1(12)，2(12)，6(12)，5(13)，10(13)，11(13)，12(13)}

打开{3(19)，7(17)，9(14)}

自 12(13) ∈ G

所以我们到了目标节点，也就是 12 。

实现 A*算法

我们现在来看看如何实现 A*算法。让我们从代码开始。我们将使用 Dijkstra 搜索算法中使用的相同代码。Vertex.java文件如下:

public class Vertex {
    final private String id;
    final private String name;

    public Vertex(String id, String name) {
        this.id = id;
        this.name = name;
    }
// public String getId() {
// return id;
// }
//
// public String getName() {
// return name;
// }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((id == null) ? 0 : id.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Vertex other = (Vertex) obj;
        if (id == null) {
            if (other.id != null)
                return false;
        } else if (!id.equals(other.id))
            return false;
        return true;
    }

    @Override
    public String toString() {
        return name;
    }

在Edge.java文件中，我们通过添加一个启发式变量hval做了一个改变；我们的构造函数将接受这个值。除此之外，以下代码没有任何变化:

public class Edge {
    private final String id;
    private final Vertex source;
    private final Vertex destination;
    private final int weight;
    private final int hval;

    public Edge(String id, Vertex source, Vertex destination, int weight, int hval) {
        this.id = id;
        this.source = source;
        this.destination = destination;
        this.weight = weight;
        this.hval = hval;
    }

    public String getId() {
        return id;
    }
    public Vertex getDestination() {
        return destination;
    }

    public Vertex getSource() {
        return source;
    }
    public int getWeight() {
        return weight+hval;
    }

    //@Override
    public String toString() {
        return source + " " + destination;
    }

然后我们有了Graph.java文件，除了前面提到的启发值之外，它没有任何变化:

import java.util.List;
public class Graph {

    private final List<Vertex> vertexes;
    private final List<Edge> edges;

    public Graph(List<Vertex> vertexes, List<Edge> edges) {
        this.vertexes = vertexes;
        this.edges = edges;
    }

    public List<Vertex> getVertexes() {
        return vertexes;
    }

    public List<Edge> getEdges() {
        return edges;
    }

我们的astr.java文件也不会有任何改动。它将只计算最小距离，因为最小距离是按实际成本计算的。然后，我们有一个Test.java文件，如下所示:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertTrue;

public class Test {

    private List<Vertex> nodes;
    private List<Edge> edges;

    public void testExcute() {
        nodes = new ArrayList<Vertex>();
        edges = new ArrayList<Edge>();
        for (int i = 0; i < 12; i++) {
            Vertex location = new Vertex("Node_" + i, "Node_" + i);
            nodes.add(location);
        }

        addLane("Edge_0", 0, 1, 2, 12);
        addLane("Edge_1", 0, 4, 1, 12);
        addLane("Edge_2", 1, 2, 1, 16);
        addLane("Edge_3", 1, 5, 3, 7);
        addLane("Edge_4", 2, 3, 2, 14);
        addLane("Edge_5", 3, 7, 1, 15);
        addLane("Edge_6", 4, 8, 1, 12);
        addLane("Edge_7", 5, 4, 5, 12);
        addLane("Edge_8", 5, 6, 1, 11);
        addLane("Edge_9", 5, 9, 4, 4);
        addLane("Edge_10", 6, 2, 3, 16);
        addLane("Edge_11", 6, 10, 10, 1);
        addLane("Edge_12", 7, 11, 15, 0);
        addLane("Edge_13", 8, 9, 8, 4);
        addLane("Edge_14", 9, 10, 3, 1);
        addLane("Edge_15", 10, 11, 1, 0);
        addLane("Edge_16", 7, 6, 5, 11);

        // Lets check from location Loc_1 to Loc_10
        Graph graph = new Graph(nodes, edges);
        astr ast = new astr(graph);
        ast.execute(nodes.get(0));
        LinkedList<Vertex> path = ast.getPath(nodes.get(10));

        assertNotNull(path);
        assertTrue(path.size() > 0);

        for (Vertex vertex : path) {
            System.out.println(vertex);
        }

    }

    private void addLane(String laneId, int sourceLocNo, int destLocNo,
            int cost, int hval) {
        Edge lane = new Edge(laneId,nodes.get(sourceLocNo), nodes.get(destLocNo), cost, hval );
        edges.add(lane);
    }

现在，我们将分配一些值进行测试。这一次，我们将创建构造函数。此外，我们必须带上我们的junit.jar和hamcrest-core-1.3.jar文件；因此，我们将导入它们，在边缘，我们将分配四个值，而不是三个。我们将有一个源节点、一个目标节点(目的地)、实际成本和启发值。

运行代码，您将看到以下输出:

请注意，这一次，我们生成了更少的节点，这意味着我们以更优化的方式执行了搜索。

摘要

在这一章中，你学习了试探法，也学习了统一成本和 A*算法是如何工作的。

在下一章，你将学习游戏是如何工作的(换句话说，人工智能游戏是如何工作的)。我们将介绍基于规则的系统以及它在 Java 中是如何工作的。

三、人工智能游戏和基于规则的系统

在本章中，我们将讨论以下主题:

• 人工智能游戏如何工作
• 游戏入门
• 实施基于规则的系统
• 如何在 Java 中与 Prolog 接口

我们开始吧。

介绍最小-最大算法

为了理解最小-最大算法，你应该熟悉游戏和博弈树。玩游戏可以被分类为游戏树。什么是博弈树？一棵树由一个根节点组成，一个根节点有子节点；每个子节点被细分为多个子节点。

这就形成了一棵树，终端节点称为叶，如下图所示:

在游戏中，我们的主要目标是赢得游戏；换句话说，我们试图通过在博弈树中向前看来找到可能的最佳解决方案。玩游戏要注意的最重要的一点是，我们实际上并没有下到一个特定的节点(或者下到一棵完整的树)，我们也没有玩完整个游戏。我们处于根本位置，我们正在寻找我们可以利用的最佳选择，以便最大化我们赢得比赛的机会。

既然我们在玩游戏，我们就轮流玩，就像在下棋或玩井字游戏一样；我们转了一圈，然后我们的对手转了一圈。这意味着我们所有的孩子，或者某个特定节点的孩子，都将是我们对手的走法。我们对手的目标是让我们输，因为无论我们要开发什么样的游戏树，都会在我们的视野中。因此，从我们的角度来看，在任何一步棋中，我们的目标是赢得比赛；一旦我们的棋走完了，这将是我们对手的棋。在我们看来，对手的行动将会使我们失败。因此，在展望未来时，我们简单地搜索博弈树。

考虑具有以下类型节点的树:

• 最小节点:这些是我们对手的节点
• 最大节点数:这些是我们的节点

在 min 节点中，我们选择最小成本的后继者。在特定节点的所有后继者中，我们选择最小的。在一个 max 节点中，我们试图找出最大的后继者，因为这些节点就是我们的棋步。

现在，我们实际上并没有移动到一个特定的点；我们只是向前看，在内存中执行某些计算，并试图找到可能的最佳移动。终端节点是输赢节点，但搜索终端节点往往不可行；因此，我们应用试探法来比较非终端节点。下图说明了我们的游戏树:

我们将从根节点开始， A 。我们有两个选择:要么是右边的子树，要么是左边的子树。如果我们随机选择任何一个子树，我们输掉游戏的几率会更高。为了避免这种情况，我们将应用某些启发式方法，这样我们赢得游戏的机会就会增加。因此，我们将尝试对游戏进行建模。假设我们选择B；我们的对手可以选择 D 或 E 。如果我们的对手选择 D ，我们将可以选择 H 或 I 。如果我们的对手选择 H ，我们将可以选择 10 或 11 ，这是可以执行的最大值。我们的计算机系统没有足够的内存进行进一步的处理；因此，从这一点，我们将应用启发式。

在上图中，可以看到所有终端节点的启发式值。游戏没有结束，我们只是向前看。试探值包括我们可以向前看的最大深度；之后，我们将应用启发式。在特定的点上赢得游戏的机会是，比如说，10%，11%，9%，等等。这些是我们的终值。

现在，假设我们的对手选择了 H 节点。这是一个最小节点，一个最小节点将总是从它的后继节点中选择一个最小值。因此，如果在 10 和 11 之间选择，最小节点将总是选择 10 。如果往前走，我们有 9 和11；所以，我们的对手会选择 9 。同样，我们的对手将选择其余的节点。

现在，轮到我们了。 D 、 E 、 F 、 G 为最大节点。最大节点将总是从它们的后继节点中选择最大值。因此，我们将选择 10 、 14 、 2 和 20 作为我们的节点。现在又是我们对手的棋了，我们的对手永远会在后继者中选择最小的。这次他会选择 10 和 2 。终于轮到我们了，我们有了一个 max 节点。我们将选择最大价值接班人: 10 。下图对此进行了说明:

这就是游戏的运作方式。

实现示例最小-最大算法

在本节中，我们将实现一个最小-最大算法(井字游戏示例)。那么，让我们来看看 NetBeans。我们将有一个ArrayList，我们将应用随机化并接受输入。以下是我们将使用的四个类:

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

然后，我们必须定义x和y点。在井字游戏中，有九张牌，在与对手一对一的基础上，方块被填满，如下所示:

class Point {

    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "[" + x + ", " + y + "]";
    }
}

class PointAndScore {

    int score;
    Point point;

    PointAndScore(int score, Point point) {
        this.score = score;
        this.point = point;
    }
}

因此，我们将定义Point，以及x和y点。这将给出x和y值，我们必须在上面输入值。String将返回这些值。PointAndScore将在每个特定的方块提供point值及其score，无论它是否被填充。

Board类将定义整个九个图块并接受输入；这将给我们三个状态。要么是X赢了，要么是有X的人赢了，要么是有0的人赢了，以及可用的州，如果可用的州是Empty:

class Board {

    List<Point> availablePoints;
    Scanner scan = new Scanner(System.in);
    int[][] board = new int[3][3];

    public Board() {
    }

    public boolean isGameOver() {
        return (hasXWon() || hasOWon() || getAvailableStates().isEmpty());
    }

    public boolean hasXWon() {
        if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 1) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 1)) {
            return true;
        }
        for (int i = 0; i < 3; ++i) {
            if (((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 1)
                    || (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 1))) {
                return true;
            }
        }
        return false;
    }

    public boolean hasOWon() {
        if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 2) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 2)) {
            return true;
        }
        for (int i = 0; i < 3; ++i) {
            if ((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 2)
                    || (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 2)) {
                return true;
            }
        }

        return false;
    }

    public List<Point> getAvailableStates() {
        availablePoints = new ArrayList<>();
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] == 0) {
                    availablePoints.add(new Point(i, j));
                }
            }
        }
        return availablePoints;
    }

    public void placeAMove(Point point, int player) {
        board[point.x][point.y] = player; //player = 1 for X, 2 for O
    } 

    void takeHumanInput() {
        System.out.println("Your move: ");
        int x = scan.nextInt();
        int y = scan.nextInt();
        Point point = new Point(x, y);
        placeAMove(point, 2); 
    }

    public void displayBoard() {
        System.out.println();

        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();

        }
    } 

    Point computersMove; 

    public int minimax(int depth, int turn) { 
        if (hasXWon()) return +1; 
        if (hasOWon()) return -1;

        List<Point> pointsAvailable = getAvailableStates();
        if (pointsAvailable.isEmpty()) return 0; 

        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;

        for (int i = 0; i < pointsAvailable.size(); ++i) { 
            Point point = pointsAvailable.get(i); 
            if (turn == 1) { 
                placeAMove(point, 1); 
                int currentScore = minimax(depth + 1, 2);
                max = Math.max(currentScore, max);

                if(depth == 0)System.out.println("Score for position "+(i+1)+" = "+currentScore);
                if(currentScore >= 0){ if(depth == 0) computersMove = point;} 
                if(currentScore == 1){board[point.x][point.y] = 0; break;} 
                if(i == pointsAvailable.size()-1 && max < 0){if(depth == 0)computersMove = point;}
            } else if (turn == 2) {
                placeAMove(point, 2); 
                int currentScore = minimax(depth + 1, 1);
                min = Math.min(currentScore, min); 
                if(min == -1){board[point.x][point.y] = 0; break;}
            }
            board[point.x][point.y] = 0; //Reset this point
        } 
        return turn == 1?max:min;
    } 
}

如果X赢了，我们要检查哪些值相等，比如棋盘[0] [0]等于[1] [1]，[0] [0]等于[2] [2]。这意味着对角线相等，或者[0] [0]等于1，或者板0等于[1] [1]。要么我们有所有的对角线，要么我们有任何一条水平线，要么我们有所有三个正方形在一条垂直线上。如果出现这种情况，我们将返回true；否则，我们将检查板上的其他值。以下代码部分将检查这些值，如果它们不符合前面的条件，将返回false:

 public boolean hasXWon() {
    if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 1) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 1)) {
        return true;
    }
    for (int i = 0; i < 3; ++i) {
        if (((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 1)
                    || (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 1))) {
            return true;
        }
    }
    return false;
}

接下来我们就看0是否赢了；所以，我们会对0做同样的事情。这里，我们将检查该值是否为2。然后，如果没有人获胜，我们将检查用户的可用状态，并将它们打印出来。然后我们会有placeAMove，要么玩家1会移动，要么玩家2会移动。

接下来，我们有takeHumanInput；因此，我们将人为输入x和y点，我们将使用displayBoard方法显示棋盘；最后，我们将应用最小-最大算法。因此，我们将检查是X赢了还是0赢了；如果没有，我们将开始玩游戏，我们将打印分数位置。最后，在main类中，我们将从谁将采取第一步开始(计算机或用户)。如果我们的用户开始移动，我们必须提供x和y坐标中的值(在x和y平面中)；否则，计算机将开始移动，每次，我们都要检查X是否已经赢了。如果X赢了，我们将打印Unfortunately, you lost!如果0赢了，我们将打印You won!如果双方都赢了，那么我们将打印It's a draw!

运行程序以获得以下输出:

前面的输出是端口的初始位置。这已经在初始点打印了。现在，我们必须选择轮到我们了。假设我们输入1；我们将获得以下输出:

先轮到电脑，电脑把位置放在[0] [0]。现在，该我们行动了；所以，我们放置[0] [2]。这将在我们棋盘的最后一个位置输入2，如下图所示:

我们的2已经放在[0] [2]了。前面的截图显示了我们当前的位置。电脑在[1] [0]上做了标记。让我们在[2] [0]上做一个标记，如下所示:

我们现在位于[2] [0]上方，并封锁了电脑。现在，电脑已经在[1] [1]进入1。让我们在[1] [2]上做个标记，再次屏蔽电脑:

电脑已经在[2] [2]进入1，已经赢了比赛。

安装 Prolog

我们现在将向您展示如何在您的系统上安装 Prolog。在浏览器中，转到www.swi-prolog.org/download/stable:

如果您使用的是 Windows 操作系统，可以根据您的 Windows 版本下载 64 位版本或 32 位版本。如果你有 Mac OS，那么你可以下载 Mac 版本。您可以按如下方式安装它:

• 对于 Windows，你必须下载并运行.exe文件。单击“下一步”继续安装过程，您将能够将 Prolog 安装到您的系统上。
• 对于 Mac，你必须下载.dmg文件并解压到你的系统中。然后，将其复制到您的应用程序中，并安装它。
• 默认情况下，SWI-Prolog 是 Linux 自带的，所以在 Linux 上，您不必安装它。

用 Prolog 介绍基于规则的系统

现在，我们将看看如何在 Prolog 中创建知识库和应用推理。让我们先来看看 Prolog 环境:

• 如果您使用的是 Windows，请转到程序| Prolog
• 如果您使用的是 Mac，请转到应用程序| Prolog
• 在 Linux 中，到终端键入Prolog，环境就会出现

以下屏幕截图显示了 Windows 中的 Prolog 环境:

?-对象是 Prolog 提示符，或 Prolog 解释器。我们在这里键入的任何内容都将被执行；Prolog 将被视为一个谓词，它将以true或false的形式给出结果。因此，如果我们想要创建新的规则，我们可以转到文件，或者创建一个新的知识库(使用 new…)或编辑…现有知识库，如下所示:

如果你在 Windows 或 Mac 上工作，你将不得不在文本编辑器中打开你的知识库。你可以使用 gedit，可以在 Linux 上使用宋旻浩，也可以使用 Mac 附带的文本编辑器。我们已经创建了一个知识库，所以我们不会写规则；我们只是演示一下。下面的屏幕截图显示了我们的知识库:

假设迈克尔是维托的孩子；我们将创建一个名为child的谓词，并向它传递两个术语:一个是michael，另一个是vito。然后，假设sonny是vito的孩子，fredo是vito的孩子。我们将创建另外两个事实，如下所示:

• 安东尼是迈克尔的孩子。
• 玛丽是迈克尔的孩子。

所以，如果某人是某人的孩子，那么那个人就是那个人的父亲:X是Y的父亲。在 Prolog 中，条件部分以相反的方式工作。father(X, Y)宾语是我们需要的结果，而child(Y, Z)是它的前提。那么，如果Y是X的孩子，X就是Y的父亲:

father(X, Y) :- child(Y, X).

在 Prolog 中，我们将前面的代码理解为X是Y的父亲，前提是Y是X的孩子，我们使用句号作为语句结束符。

同样，我们正在创建一个新规则:grandfather(X, Y)。X是Y的祖父，前提是Y是Z的孩子X是Z的父亲。如果X是Z的父亲，Y是Z的孩子，那么我们就有了X和Y的关系。

让我们通过导航到 Compile | Make 来编译它:

编译完成后，我们将尝试在 Prolog 中打开知识库。为此，我们需要知道知识库存储的路径。然后，转到 Prolog 并在 path 中使用以下命令:

?- consult('C:/Users/admin/Documents/Prolog/family.pl'). 

请注意，我们必须用正斜杠替换反斜杠。

现在，我们可以向知识库提问，例如:

child(soony, vito). 

知识库将通过true或false做出响应:

它已经返回了false，也就是说我们不知道vito的孩子的名字。为了找到vito的孩子，我们使用X，如下所示:

?- child(X, vito).

大写字符(X)将被视为变量，而小写字符(以小写字母开头的单词，如vito)被视为常量。

我们得到以下结果:

现在，让我们用下面的命令再问一次:

?- child(sonny,vito).

我们得到以下输出:

之前的回答是false，因为我们提供了错误的sonny拼写。这意味着拼写应该匹配。

类似地，我们可以用下面的命令请求father:

?- father(vito, sonny)

我们得到以下输出:

我们得到true，这意味着vito是sonny的father。我们可以通过键入以下命令找到michael的孩子:

?- father(michael, X).

我们得到以下输出:

我们得到anthony是michael的儿子，mary是michael的女儿，也就是说michael是anthony和mary的父亲。

同样，我们可以要求祖父，如下:

?- grandfather(vito, X).

我们得到vito是anthony和mary的grandfather:

正如您所看到的，我们还没有为father和grandfather创建事实，但是它们已经被 Prolog 解释器推断出来，我们能够根据谓词father和grandfather得到问题的答案。

这就是我们如何将规则和事实写入知识库，并使用 Prolog 提问。如果我们想看到所有的父子关系，我们可以问以下问题:

?- father(X, Y).

我们将得到所有的父子对，如下所示:

我们得到vito是michael的父亲，vito是sonny的父亲，等等。

同样，我们可以使用grandfather关系，如下所示:

?- grandfather(X, Y).

我们得到vito是anthony的祖父，vito是mary的祖父:

用 Java 设置 Prolog

现在，您将看到如何下载 JPL 库，以及如何在 Java 中使用JPL与 Prolog 接口。

在浏览器中，转到www.java2s.com/Code/Jar/j/Downloadjpljar.htm:

这是已经创建的所有已知 JAR 文件的流行存储库之一，它保存了所有这些 JAR 文件。我们将获得这个JPL库中可用的所有信息和所有类，并在我们的代码中使用它们。点击 jpl/jpl.jar.zip(27 k)下载库。然后，您必须提取它以获得jpl.jar文件。

一旦我们提取了 JAR 文件，我们就可以检查代码看它是否工作。所以，我们就去 NetBeans。在 NetBeans 中，我们将转到我们的项目，右键单击它，然后转到“属性”选项。在“属性”中，我们将转到“库”和“添加 JAR/文件夹”选项:

在 Add JAR/Folder 中，我们必须提供我们提取了jpl.jar文件的路径。一旦我们选择了路径，我们将点击打开:

我们将把这个文件导入到 Java 代码中，如下所示:

import jpl.*;

public class JPLwJava {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        System.out.println("Hello Prolog");
    }
}

import jpl.*;命令将JPL库导入我们的代码。现在，我们将简单地打印Hello Prolog。

运行代码以获得以下输出:

Hello Prolog消息意味着我们的JPL库已经合并到我们的代码中，所以我们可以在 Prolog 和 Java 之间进行接口。

使用 Java 执行 Prolog 查询

现在，我们将看看如何在 Java 中使用 Prolog 查询。让我们来看看 Java 代码，看看这是如何做到的。

在 NetBeans 中创建一个 Java 项目，并键入以下代码:

import java.util.Map;
import jpl.Query;
import jpl.JPL;

public class ProrlogJava {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        String t1 = "consult('/Users/admin/Documents/NetBeansProjects/JPLwJava/family.pl')";
        System.out.println(t1 + " " + (Query.hasSolution(t1) ? "succeeded" : "failed"));
        String t2 = "child(sonny, vito)";
        System.out.println(t2 + " " + (Query.hasSolution(t2) ? "provable" : "not provable"));
        String t3 = "grandfather(vito, anthony)";
        System.out.println(t3 + " " + (Query.hasSolution(t3) ? "provable" : "not provable"));
    }

}

首先，我们必须通过添加jpl.jar文件来调用JPL库，如前一节所示。一旦我们有了它们，我们将从JPL包中import出两个等级:jpl.Query等级和jpl.JPL等级。

接下来，我们必须提供一个String，在这里我们将输入consult和我们的文件名。

序言文件以.pl格式或文本格式保存。

然后，我们可以调用Query.hasSolution(t1)。如果我们的知识库在 Prolog 中打开，我们将得到一条succeeded消息；否则，我们会得到一条failed消息。这是一个简单的条件运算符。

接下来我们就要查询:child(sonny, vito)。这将给我们带来provable或not provable。如果是true，会返回消息说是provable；否则，我们将得到消息not provable。同样，我们可以问:grandfather(vito, anthony)。如果这是可证明的，我们将得到provable；不然我们就拿not provable。

让我们运行它，看看会发生什么，如下所示:

我们查阅了我们的数据库，family.pl被成功加载到内存中。然后，我们问sonny是不是vito的child的问题，得到的回答是provable；同样，我们问vito是不是anthony的grandfather，果然是provable。这就是我们如何在 Java 中使用 Prolog。

摘要

在本章中，您学习了游戏如何工作，如何用 Java 实现井字游戏，如何安装 Prolog，如何下载一个JPL库，以及如何用 Java 与 Prolog 接口。

在下一章，我们将讨论 Weka 的接口。

四、与 Weka 接口

在本章中，我们将使用数据集。数据集的一般格式是一个逗号分隔值 ( CSV )文件，Weka 使用一种特殊的格式，称为属性关系文件格式 ( ARFF )文件。我们将了解如何将 CSV 文件转换为 ARFF 文件，反之亦然。

在本章中，我们将讨论以下主题:

• Weka 简介
• 安装和连接 Weka
• 读取和写入数据集
• 转换数据集

首先，我们来看一个关于 Weka 的介绍。

Weka 简介

Weka 是一套用 Java 编写的机器学习软件。它是由新西兰怀卡托大学开发的。这是一个免费软件，在 GNU 通用公共许可证 ( GPL )下可用，算法可以直接应用于数据集，也可以从我们自己的 Java 代码中调用。

当我们下载 Weka 并开始使用它时，它为我们提供了自己的 GUI。我们可以使用 GUI 来处理我们自己的数据集。如果我们想增强 Weka 的功能，我们应该在 Java 代码中使用它。Weka 的官方网站位于www.cs.waikato.ac.nz/ml/weka/。它在怀卡托大学的官方网站上。它的当前版本是 3。我们可以在其网站上找到所有关于 Weka 的信息。我们将找到各种部分，如入门、更多信息和开发人员。

在“开始”中，有以下选项可用:

• 要求:使用 Weka 的要求。
• 下载:在下载页面，我们可以去快照部分，在那里我们可以下载 Weka。
• 文档:如果我们转到文档页面，它会为我们提供很多 Weka 可用的文档。还有 Weka Wiki，在那里我们可以获得我们需要的大部分信息，软件包列表和一些视频。
• 常见问题解答:这是一些常见问题。
• 寻求帮助:如果需要，这将提供进一步的帮助。

项目页面提供了机器学习组。是怀卡托的计算机科学系机器学习小组开发了这个软件。我们还可以了解他们发展 Weka 的基本目标。

安装和连接 Weka

我们现在将学习如何下载 Weka。要下载 Weka，请访问位于www.cs.waikato.ac.nz/ml/weka/downloading.html的下载网站。访问该页面时，我们将获得有关下载的信息。如果我们向下滚动，我们将得到关于稳定版本的信息；根据我们拥有的机器，我们可以下载我们想要的 Weka 版本，有以下选项:

• 对于 Windows，该文件将是 EXE 文件；我们只需要点击它，它就会出现在我们的程序中。
• 对于 Mac，它将是一个 DMG 文件；我们将不得不提取它并粘贴到我们的应用程序中。
• 对于 Linux，在提取 TAR 文件后，我们将获得运行 Weka 所需的所有包，并且我们可以通过使用java -jar weka.jar命令使用一个weka.jar文件来运行它。

我们可以在我们的系统上运行下载的文件，并按照说明安装 Weka。安装完成后，打开它，我们将看到以下界面:

前面的屏幕截图显示了 Weka GUI。我们可以看到程序选项、可视化和工具。在工具中，我们将看到软件包管理器，在这里我们可以安装 Weka 上可用的任何软件包:

有一个非常大的可用包管理器列表，如下面的屏幕截图所示:

我们可以单击 Install 按钮，这些包将被安装。如果我们已经安装了某些软件包，我们可以点击它们并通过点击卸载按钮卸载它们。这就是我们如何安装和卸载软件包。

我们现在将转到 Weka Explorer。单击 Applications 下的 Explorer 按钮，我们将看到一个新窗口，如下面的屏幕截图所示:

首先，我们必须打开一个数据集，以便对数据集进行分类。点击打开文件…按钮。在Weka文件夹中，我们会看到一个data文件夹。data文件夹将包含可用的数据集:

如下图所示，我们可以查看数据集:

前面的数据集有五个属性。第一个属性是outlook,outlook有三个标签，在Label列下有三个不同的值:sunny，有一个Count为5；overcast，带一个4的Count；和rainy，带一个5的Count。同样，还有windy属性，windy有两种值，TRUE和FALSE，带计数，如下面截图所示:

play属性有两个不同的值，yes和no，以及它们的计数，如下面的屏幕截图所示:

outlook、windy和play对象是名义类型的数据，temperature和humidity是数值数据。

temperature属性有 12 个值，因为它是一个数值，我们可以从这些值中得到一些数值信息，比如最大值、最小值、平均值和标准偏差:

如果我们想要对特定的模型进行分类，请转到“分类”选项卡，然后单击“选择”;我们将获得选择分类器的选项，如下面的屏幕截图所示:

点击trees文件夹。假设我们想要执行一个 J48 分类:点击 J48 选项，然后点击 Start 按钮。将使用 10 重分类构建 J48 分类器，并将显示该特定数据的统计信息，如下面的屏幕截图所示:

将 Weka 环境调用到 Java 中

要在 Java 中调用 Weka 环境，请执行以下步骤:

1. 创建新项目。
2. 创建项目后，右键单击它并转到属性:

3. 在 Properties 选项卡中，选择 Libraries，点击 Add JAR/Folder，并给出weka.jar文件的路径:

4. 一旦我们有了weka.jar文件的路径，我们就可以使用 Weka。用以下代码替换项目中的代码:

package helloworld;

/**
 *
 * @author admin
 */
import weka.*;
public class HelloWorld {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        System.out.println("Hello World"); 
    }    
}

正如我们在前面的代码中看到的，我们用import weka.*;替换了import juint.framework.*;。

请注意，当我们编写前面的代码时，我们将获得 Weka 包的建议。这意味着我们可以在 Java 环境中访问 Weka。

从今以后，在所有的项目中，我们将使用weka.jar文件。因此，每次我们创建一个新的项目，我们将不得不在库窗口中import这个weka.jar文件。

现在，如果我们运行前面的代码，我们将得到以下输出:

读取和写入数据集

我们现在来看看如何读写数据集。让我们来看看 Java 代码。创建一个项目并将其命名为Datasets。现在，导入weka.jar文件，如前一节所述。一旦我们有了weka.jar文件，我们就可以读取core、Instance接口、ArffSaver、DataSource和io.File包，如下图所示:

我们从DataSource开始。DataSource是一个帮助我们打开 Weka 中可用的数据集文件的类。默认情况下，Weka 使用 ARFF 文件；请参见以下代码:

DataSource src = new DataSource("/Users/admin/wekafiles/data/weather.numeric.arff");
Instances dt= src.getDataSet();
System.out.println(dt.toSummaryString());
ArffSaver as = new ArffSaver();

正如我们在前面的代码中看到的，我们为DataSource创建了一个对象，并提供了我们需要打开的 ARFF 文件的路径。这将只提供 ARFF 文件的路径；它不会打开它。在工作内存中，有一个名为Instances的类，我们为Instances类创建了一个对象dt。我们将调用带有DataSource和src对象的getDataSet方法。这将在内存中的dt对象中打开特定的数据集。我们可以通过使用toSummaryString方法打印特定数据集中的任何可用内容。一旦它被读取和打开，我们可以通过使用ArffSaver类将它写入硬盘。我们将为它创建一个对象(as)，如下所示:

 as.setInstances(dt);

这将只把dt对象可用的所有数据分配给as对象。它不会保存它，目前为止。现在，我们必须给数据集起一个名字；因此，我们将调用setFile方法，并使用File对象将weather.arff作为文件名提供给我们的数据集:

as.setFile(new File("weather.arff"));

现在，数据集已经有了一个名称，但是它仍然没有保存在内存中。我们现在将调用一个writeBatch方法，如下所示:

as.writeBatch();

最后，所有内容都将以文件名(weather.arff)保存到内存中。当我们执行代码时，我们将看到以下输出:

它有作为weather的Relation Name，它有14实例和5属性。它显示属性的统计数据。如果我们转到 NetBeans 中的Datasets项目文件夹，我们可以检查weather.arff文件是否已经保存:

在文本编辑器中打开weather.arff文件，我们会看到数据集已经保存在文件中。下面的屏幕截图显示了 ARFF 文件的样子:

这个文件有一个relation，我们可以在这里给出文件名，它还有一个@attribute对象。@attribute对象告诉我们这些是文件的属性，在花括号中，我们可以指定分类值。例如，temperature和humidity属性是numeric值，windy是布尔值，@attribute play是可以有yes和no的类。然后，我们有@data，其中显示了所有带有属性值的元组。这就是 ARFF 档案的工作方式。

如果我们没有标题数据，那么它就是一个 CSV 文件。

转换数据集

在本节中，我们将了解如何转换数据集。我们将学习如何将 CSV 文件转换为 ARFF 文件，反之亦然。

将 ARFF 文件转换为 CSV 文件

首先，让我们看看代码。假设我们有一个weather.arff文件。我们将首先导入以下包:

import weka.core.Instances;
import weka.core.converters.ArffLoader;
import weka.core.converters.CSVSaver;
import java.io.File;

我们从ArffLoader类开始，并为它创建了一个对象loader:

ArffLoader loader = new ArffLoader();

然后，我们将文件名weather.arff分配给ArffLoader类，如以下代码所示:

loader.setSource(new File("weather.arff")); //Use the path where your file is saved.

我们还调用了loader.setSource方法，并通过使用我们的File对象给它分配了一个文件名。一旦完成，我们将把这个特定的数据集加载到我们的Instances对象data的内存中，如下所示:

Instances data = loader.getDataSet();

现在，我们需要为我们的CSVSaver类创建一个对象并实例化它:

CSVSaver saver = new CSVSaver();

现在，我们需要设置实例；因此，我们需要将我们的Instances对象的对象提供给setInstances方法，如下所示:

saver.setInstances(data);

完成此操作后，我们的 ARFF 数据集已在内存中转换为 CSV 数据集，但尚未保存到磁盘上。如果我们想把它保存到磁盘上，我们必须使用一个setFile方法并使用我们的File对象分配一个文件名:

saver.setFile(new File("weather.csv"));

File对象将被传递给setFile方法，一旦我们完成了这一步，我们已经为数据集指定了一个名称(即weather.csv)，但是我们仍然没有将它保存到磁盘上。

调用writeBatch方法后，我们的整个数据集将被保存到磁盘上:

saver.writeBatch();

让我们试着运行整个代码；我们应该得到以下输出:

现在，让我们转到磁盘，看看数据集是否已经创建，如下面的屏幕截图所示:

我们可以看到已经使用weather.arff文件创建了一个新的weather.csv文件。这是我们的 CSV 文件，可以在记事本或 Excel 中打开，如下所示:

通常，所有 CSV 文件都可以直接在任何电子表格应用程序中打开。因为 CSV 是一个逗号分隔的值，所以所有逗号分隔的值都被分配给一个特定的集合。因此，outlook、temperature、humidity、windy和play已经被分配给一个特定行中的某些单元格，并且它们的所有值已经被分配给相应的列。这就是我们的文件被转换成数据集的方式。如果我们比较 ARFF 和 CSV 文件，我们可以注意到头数据已经从 CSV 文件中删除。

如果我们想要比较这两个文件，我们可以在文本编辑器中打开这两个文件，如下面的屏幕截图所示:

在 CSV 文件中，我们只有标题值。ARFF 文件中的属性值被转换成 CSV 文件的第一行，然后，我们看到了这些值。这就是 CSV 文件的创建方式。

将 CSV 文件转换为 ARFF 文件

现在，让我们看看是否可以将 CSV 文件转换为 ARFF 文件。我们将做与上一节相反的事情。

首先，导入以下包:

import weka.core.Instances;
import weka.core.converters.ArffSaver;
import weka.core.converters.CSVLoader;
import java.io.File;

注意，这一次，我们将导入ArffSaver和CSVLoader类，而不是ArffLoader和CSVSaver类。

这一次，我们做的第一件事就是使用我们的CSVLoader对象的setSource方法，为CSVLoader类创建一个对象，并将 CSV 文件分配给CSVLoader类:

CSVLoader loader = new CSVLoader();
loader.setSource(new File("/Users/admin/Documents/NetBeansProjects/Arff2CSV/weather.csv"));

然后，我们使用一个Instances对象打开内存中的 CSV 数据集:

Instances data = loader.getDataSet();

一旦我们这样做了，我们将需要以 ARFF 格式保存它。因此，我们为ArffSaver创建了一个saver对象，然后，我们将希望保存在 ARFF 文件中的数据集赋值给Instances:

ArffSaver saver = new ArffSaver();
saver.setInstances(data);

然后，我们使用saver对象并调用setFile方法来为这个ArffSaver指定名称，如下所示:

saver.setFile(new File("weather.arff"));

setFile方法将使用File对象，我们将为其指定名称weather.arff。现在，一切都已经在内存中完成了，数据集已经在内部转换成了 ARFF 格式，我们已经给它分配了一个名字(weather.arff)；但是，我们还没有把它保存到磁盘上。

writeBatch()方法将完整的数据集保存到硬盘上:

saver.writeBatch();

运行代码以获得以下输出:

由于我们的构建已经成功，我们将我们的weather.csv转换为weather.arff。让我们去看看磁盘，看看它是否工作:

在前面的屏幕截图中，我们可以看到 ARFF 文件已经创建。我们已经展示了如何从 CSV 文件创建 ARFF 文件。我们不需要做任何手工工作来分配关系和属性，因为如果我们提供我们的 CSV 文件，它们是由 Weka 自动分配的。Weka 负责属性；它还负责处理它是什么类型的属性。例如，outlook是分类数据，因为它只有三种类型的值；因此，这些类别被分配给了outlook。由于temperature接受所有数值，它已经被 Weka 自动赋值为数值，并且由于humidity也只有数值，它也是数值。windy对象也是一个TRUE / FALSE值；因此，它也是一种分类类型的数据。play对象也只有两种类型的值，所以它也是分类数据。

这就是我们如何将数据集从 CSV 转换到 ARFF，或从 ARFF 转换到 CSV。

摘要

在本章中，我们介绍了 Weka 以及如何安装它。我们还学习了如何读写数据集，以及如何转换它们。

在下一章，我们将学习如何处理属性。