[科普中國(guó)]-不可解節(jié)點(diǎn)

定義

不可解節(jié)點(diǎn)的一般定義歸納于下：

(1) 沒(méi)有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。

(2) 如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其全部后裔為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。

(3) 如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后裔至少有一個(gè)為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。2

可解節(jié)點(diǎn)定義與或圖中一個(gè)可解節(jié)點(diǎn)的一般定義可以歸納如下：

(1) 終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)(因?yàn)樗鼈兣c本原問(wèn)題相關(guān)連)。

(2) 如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其后繼節(jié)點(diǎn)至少有一個(gè)是可解的時(shí)，此非終葉節(jié)點(diǎn)才是可解的。

(3) 如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后繼節(jié)點(diǎn)全部為可解時(shí)，此非終葉節(jié)點(diǎn)才是可解的。2

節(jié)點(diǎn)的可解性判別（1）終止節(jié)點(diǎn)是可解節(jié)點(diǎn)；

（2）一個(gè)與節(jié)點(diǎn)可解，當(dāng)且僅當(dāng)其全部子節(jié)點(diǎn)可解；

（3）一個(gè)或節(jié)點(diǎn)可解，只要其子節(jié)點(diǎn)中至少有一個(gè)節(jié)點(diǎn)可解；

（4）非終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)；

（5）一個(gè)與節(jié)點(diǎn)不可解，只要其子節(jié)點(diǎn)中至少有一個(gè)節(jié)點(diǎn)不可解；

（6）一個(gè)或節(jié)點(diǎn)不可解，當(dāng)且僅當(dāng)其全部子節(jié)點(diǎn)不可解。3

有關(guān)術(shù)語(yǔ)父節(jié)點(diǎn) 是一個(gè)初始問(wèn)題或是可分解為子問(wèn)題的問(wèn)題節(jié)點(diǎn)；

子節(jié)點(diǎn) 是一個(gè)初始問(wèn)題或是子問(wèn)題分解的子問(wèn)題節(jié)點(diǎn)；

或節(jié)點(diǎn) 只要解決某個(gè)問(wèn)題就可解決其父輩問(wèn)題的節(jié)點(diǎn)集合；

與節(jié)點(diǎn) 只有解決所有子問(wèn)題，才能解決其父輩問(wèn)題的節(jié)點(diǎn)集合；

弧線 是父輩節(jié)點(diǎn)指向子節(jié)點(diǎn)的圓弧連線；

終葉節(jié)點(diǎn) 是對(duì)應(yīng)于原問(wèn)題的本原節(jié)點(diǎn)。