不可解節點

不可解節點又叫做無解節點，是與或圖中的一個相關定義，與之對應的概念是可解節點。

在圖解搜尋的“與或”圖建立過程中，每擴展一個節點，就要判定哪些節點是不可解節點。

基本介紹

• 中文名：不可解節點
• 外文名：unsolvable node

定義

不可解節點的一般定義歸納於下：

(1) 沒有後裔的非終葉節點為不可解節點。

(2) 如果某個非終葉節點含有或後繼節點，那么只有當其全部後裔為不可解時，此非終葉節點才是不可解的。

(3) 如果某個非終葉節點含有與後繼節點，那么只要當其後裔至少有一個為不可解時，此非終葉節點才是不可解的。

可解節點定義

與或圖中一個可解節點的一般定義可以歸納如下：

(1) 終葉節點是可解節點(因為它們與本原問題相關連)。

(2) 如果某個非終葉節點含有或後繼節點，那么只有當其後繼節點至少有一個是可解的時，此非終葉節點才是可解的。

(3) 如果某個非終葉節點含有與後繼節點，那么只要當其後繼節點全部為可解時，此非終葉節點才是可解的。

節點的可解性判別

（1）終止節點是可解節點；

（2）一個與節點可解，若且唯若其全部子節點可解；

（3）一個或節點可解，只要其子節點中至少有一個節點可解；

（4）非終止節點的端節點是不可解節點；

（5）一個與節點不可解，只要其子節點中至少有一個節點不可解；

（6）一個或節點不可解，若且唯若其全部子節點不可解。

有關術語

父節點 是一個初始問題或是可分解為子問題的問題節點；

子節點是一個初始問題或是子問題分解的子問題節點；

或節點只要解決某個問題就可解決其父輩問題的節點集合；

與節點只有解決所有子問題，才能解決其父輩問題的節點集合；

弧線是父輩節點指向子節點的圓弧連線；

終葉節點是對應於原問題的本原節點。