人工智能--问题规约求解方法

ゝ一世哀愁。 2022-01-21 05:55 855阅读 0赞

A\[toc\]

问题规约法是不同于状态空间法的另一种形式化方法，其基本思想是对问题进行分解或变换，将它转换为一系列较简单的问题。

# 问题的分解与等价变换 #

## 分解 ##

如果一个问题`P`**可以规约为一组子问题**`$P_1,P_2,...,P_n$`，并且当所有子问题`$P_i$`都有解时，原问题才有解。任何一个子问题无解都会导致原问题无解，**则称此种规约为问题的分解**，即分解所得到的子问题的“与”与原问题`P`等价。

## 等价变换 ##

如果一个问题`P`**可以规约为一组子问题**`$P_1,P_2,...,P_n$`，并且这些子问题`$P_i$`中只要有一个有解，则原问题`P`就有解，只有当所有子问题`$P_i$`都无解时，原问题才无解，则**称此类规约为问题的等价变换，简称变换**。

注：在实际问题的规约过程中，有可能需要同时采用变换和分解的方法。无论是变换还是分解，都是要将原问题规约为一系列**本源问题**。所谓本源问题是指那种不能（或不需要）再进行分解或变换，且可以直接解答的问题。本源问题可以作为终止规约的限制条件

# 问题规约的与/或树 #

把一个原问题规约为一系列本源问题的过程可以很方便的用一个与/或树来表示。

## 与树 ##

把一个原问题分解为若干个子问题可用一个“与树”来表示。在该树中，我们用相应的节点表示`P`、`$P_1$`、`$P_2$`、`$P_3$`。并用3条有向边分别将`P`和`$P_1$`、`$P_2$`、`$P_3$`连接起来，它表示`$P_1$`、`$P_2$`、`$P_3$`是`P`的三个子问题。图中还有一条连接三条有向边的小弧线。

![image][]

## 或树 ##

定义与与树类似。只是图中的有向边不用小弧线相连。

![在这里插入图片描述][20190608151820370.png]

## 与/或树 ##

如果一个问题既需要通过分解，又需要通过变换才能得到本源问题，则其规约过程可用一个“与/或树”来表示。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]

## 端节点和终止节点 ##

在与/或树中，没有子节点的节点称为端节点，本源问题所对应的节点称为终止节点。**终止节点一定是端节点，但端节点却不一定是终止节点。**

## 可解节点与不可解节点 ##

满足一下三个条件之一的节点为可解节点：

*  任何终止节点都是可解节点
 *  对“或”节点，当其子节点中至少有一个可解节点时，则该或节点就是可解节点
 *  对“与”节点，只有当其子节点全部为可解节点时，该节点才是可解节点

**仅需要对上面三句话取否定即可得到不可解节点的定义。**

## 解树 ##

由可解节点构成，并且由这些可解节点可以推出初始节点为可解节点的子树为解树。**在解树中一定包含初始节点**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]

# 例子 #

![image][image 1]  
![image][image 2]

[image]: http://note.youdao.com/yws/res/13789/79A8B9881A85434385487F91D2DCB3D3
[20190608151820370.png]: /images/20220121/67cf43f7f4d844d98b09d24b90ab1f0e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]: /images/20220121/e4950395e1dd4386ae61ad36b6c76165.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]: /images/20220121/5dcbbb9183e84bdaa99ea5c8678182d4.png
[image 1]: http://note.youdao.com/yws/res/13816/11B9B3D27AE0432C94C4A2EAD1159170
[image 2]: http://note.youdao.com/yws/res/13819/29C55117ACBC4325A29C86CD159081F8