Artificial Intelligence With Python 简明教程

AI with Python – Heuristic Search

启发式搜索在人工智能中扮演着关键角色。在本章中，您将详细了解它。

Heuristic search plays a key role in artificial intelligence. In this chapter, you will learn in detail about it.

Concept of Heuristic Search in AI

启发式是一种经验法则，它将我们引向可能的解决方案。人工智能中的大多数问题本质上呈指数增长并且有很多可能的解决方案。您不知道哪些解决方案是正确的，并且检查所有解决方案将非常昂贵。

Heuristic is a rule of thumb which leads us to the probable solution. Most problems in artificial intelligence are of exponential nature and have many possible solutions. You do not know exactly which solutions are correct and checking all the solutions would be very expensive.

因此，使用启发式可以缩小搜索范围并消除错误的选项。使用启发式引导搜索空间中的搜索的方法称为启发式搜索。启发式技术非常有用，因为在使用它们时可以增强搜索。

Thus, the use of heuristic narrows down the search for solution and eliminates the wrong options. The method of using heuristic to lead the search in search space is called Heuristic Search. Heuristic techniques are very useful because the search can be boosted when you use them.

Difference between Uninformed and Informed Search

有两种控制策略或搜索技术：无信息的和有信息的。这里对其进行详细解释 −

There are two types of control strategies or search techniques: uninformed and informed. They are explained in detail as given here −

Uninformed Search

它也被称为盲目搜索或盲目控制策略。之所以这么命名是因为只有关于问题定义的信息，并且没有其他关于状态的额外信息。此类搜索技术将搜索整个状态空间以获取解决方案。广度优先搜索 (BFS) 和深度优先搜索 (DFS) 是无信息搜索的示例。

It is also called blind search or blind control strategy. It is named so because there is information only about the problem definition, and no other extra information is available about the states. This kind of search techniques would search the whole state space for getting the solution. Breadth First Search (BFS) and Depth First Search (DFS) are the examples of uninformed search.

Informed Search

它也被称为启发式搜索或启发式控制策略。之所以这么命名是因为有一些关于状态的额外信息。此额外信息有助于计算要探索和扩展的子节点之间的偏好。每个节点将有一个启发式函数。最佳优先搜索 (BFS)、A*、平均值和分析是有信息搜索的示例。

It is also called heuristic search or heuristic control strategy. It is named so because there is some extra information about the states. This extra information is useful to compute the preference among the child nodes to explore and expand. There would be a heuristic function associated with each node. Best First Search (BFS), A*, Mean and Analysis are the examples of informed search.

Constraint Satisfaction Problems (CSPs)

约束意味着限制。在人工智能中，约束满足问题是必须在某些约束下解决的问题。解决此类问题时，重点必须是不违反约束。最后，当我们达到最终解决方案时，CSP 必须遵守该限制。

Constraint means restriction or limitation. In AI, constraint satisfaction problems are the problems which must be solved under some constraints. The focus must be on not to violate the constraint while solving such problems. Finally, when we reach the final solution, CSP must obey the restriction.

Real World Problem Solved by Constraint Satisfaction

前几节讨论了如何创建约束满足问题。现在让我们将其应用到现实世界的问题中。以下是通过约束满足解决的现实世界问题的示例 −

The previous sections dealt with creating constraint satisfaction problems. Now, let us apply this to real world problems too. Some examples of real world problems solved by constraint satisfaction are as follows −

Solving algebraic relation

在约束满足问题的帮助下，我们可以解决代数关系。在本例中，我们将尝试解决一个简单的代数关系 a*2 = b 。它将在我们定义的范围内返回 a 和 b 的值。

With the help of constraint satisfaction problem, we can solve algebraic relations. In this example, we will try to solve a simple algebraic relation a*2 = b. It will return the value of a and b within the range that we would define.

完成此 Python 程序后，您将能够了解使用约束满足解决问题的基础知识。

After completing this Python program, you would be able to understand the basics of solving problems with constraint satisfaction.

请注意，在编写程序之前，我们需要安装名为 python-constraint 的 Python 包。您可以借助以下命令安装它 −

Note that before writing the program, we need to install Python package called python-constraint. You can install it with the help of the following command −

pip install python-constraint

以下步骤向您展示了一个使用约束满足解决代数关系的 Python 程序 −

The following steps show you a Python program for solving algebraic relation using constraint satisfaction −

使用以下命令导入 constraint 包 −

Import the constraint package using the following command −

from constraint import *

现在，创建一个名为 problem() 的模块对象，如下所示 −

Now, create an object of module named problem() as shown below −

problem = Problem()

现在，定义变量。请注意，这里我们有两个变量 a 和 b，并且我们定义 10 作为它们的范围，这意味着我们在前 10 个数字中找到了解决方案。

Now, define variables. Note that here we have two variables a and b, and we are defining 10 as their range, which means we got the solution within first 10 numbers.

problem.addVariable('a', range(10))
problem.addVariable('b', range(10))

接下来，定义我们想要应用于此问题的特定约束。请注意，这里我们使用约束 a*2 = b 。

Next, define the particular constraint that we want to apply on this problem. Observe that here we are using the constraint a*2 = b.

problem.addConstraint(lambda a, b: a * 2 == b)

现在，使用以下命令创建 getSolution() 模块的对象 −

Now, create the object of getSolution() module using the following command −

solutions = problem.getSolutions()

最后，使用以下命令打印输出 −

Lastly, print the output using the following command −

print (solutions)

您可以观察到上述程序的输出如下 −

You can observe the output of the above program as follows −

[{'a': 4, 'b': 8}, {'a': 3, 'b': 6}, {'a': 2, 'b': 4}, {'a': 1, 'b': 2}, {'a': 0, 'b': 0}]

Magic Square

幻方是一种独特的数字排列，通常是整数，排列在一个正方形网格中，其中每一行、每一列和对角线上的数字相加都得到相同的数字，称为“幻方常数”。

A magic square is an arrangement of distinct numbers, generally integers, in a square grid, where the numbers in each row , and in each column , and the numbers in the diagonal, all add up to the same number called the “magic constant”.

以下是生成幻方的简单 Python 代码的分步执行 −

The following is a stepwise execution of simple Python code for generating magic squares −

定义一个名为 magic_square 的函数，如下所示 −

Define a function named magic_square, as shown below −

def magic_square(matrix_ms):
   iSize = len(matrix_ms[0])
   sum_list = []

以下代码显示了垂直正方形的代码−

The following code shows the code for vertical of squares −

for col in range(iSize):
   sum_list.append(sum(row[col] for row in matrix_ms))

以下代码显示了水平正方形的代码−

The following code shows the code for horizantal of squares −

sum_list.extend([sum (lines) for lines in matrix_ms])

以下代码显示了水平正方形的代码−

The following code shows the code for horizontal of squares −

dlResult = 0
for i in range(0,iSize):
   dlResult +=matrix_ms[i][i]
sum_list.append(dlResult)
drResult = 0
for i in range(iSize-1,-1,-1):
   drResult +=matrix_ms[i][i]
sum_list.append(drResult)

if len(set(sum_list))>1:
   return False
return True

现在，给出矩阵的值并检查输出−

Now, give the value of the matrix and check the output −

print(magic_square([[1,2,3], [4,5,6], [7,8,9]]))

你可以观察到，由于总和尚未达到相同的数字，因此输出将为 False 。

You can observe that the output would be False as the sum is not up to the same number.

print(magic_square([[3,9,2], [3,5,7], [9,1,6]]))

你可以观察到，由于总和是相同的数字，即此处的 15 ，因此输出将为 True 。

You can observe that the output would be True as the sum is the same number, that is 15 here.