第一題（共兩題100分）站點(diǎn)統(tǒng)計(jì)（50分）

  題目描述：
一個(gè)Internet站點(diǎn)集合，可以用如下的方式來(lái)描述站點(diǎn)和站點(diǎn)之間的鏈接引用關(guān)系：
   s 1 2 3 4
   1 / 4 0 3
   2 3 / 4 5
   3 2 2 / 2
   4 6 1 4 /
其中與s(site)同行和同列的數(shù)字都表示站點(diǎn)號(hào)，其他每個(gè)數(shù)字表示一個(gè)站點(diǎn)到另一個(gè)站
點(diǎn)的超文本鏈接數(shù)。如果站點(diǎn)A有到另一個(gè)站點(diǎn)B的直接鏈接或間接（指通過(guò)一個(gè)或多個(gè)
直接鏈接）鏈接，則稱站點(diǎn)A有到站點(diǎn)B的訪問(wèn)關(guān)系，或稱站點(diǎn)B可以被站點(diǎn)A訪問(wèn)到。例
如，上面描述了一個(gè)有4個(gè)站點(diǎn)鏈接關(guān)系的站點(diǎn)集合，第一行 / 4 0 3 表示站點(diǎn)1到站點(diǎn)
1，2，3，4的超文本鏈接數(shù)。
請(qǐng)編寫(xiě)程序:
1） 將一個(gè)有N個(gè)站點(diǎn)的集合劃分成滿足下面所有條件的站點(diǎn)子集（這些子集的union組
成了該N個(gè)站點(diǎn)集合）：
   a) 當(dāng)任一子集中的站點(diǎn)數(shù)大于1時(shí)，該子集內(nèi)至少存在一個(gè)站點(diǎn)有到該子集內(nèi)所有
其他站點(diǎn)的訪問(wèn)關(guān)系；
   b) 當(dāng)任一子集中的站點(diǎn)數(shù)大于1時(shí)，該子集內(nèi)的任一站點(diǎn)至少可以被該子集內(nèi)的某
一站點(diǎn)訪問(wèn)到；
   c) 兩個(gè)不同子集中的任意兩個(gè)站點(diǎn)之間不存在任何訪問(wèn)關(guān)系。
2） 裁減這些子集內(nèi)的站點(diǎn)之間現(xiàn)有的鏈接關(guān)系，使得被裁減后的各子集內(nèi)的站點(diǎn)依然
可以滿足上述所有條件，同時(shí)使得子集內(nèi)的站點(diǎn)之間的鏈接總數(shù)相加之和為最小。

假如上面的站點(diǎn)集合是這N個(gè)站點(diǎn)集合中的一個(gè)子集，它滿足了條件a)：4可以訪問(wèn)到3，
也可以訪問(wèn)到2和1；也滿足了條件b)：站點(diǎn)4可以被站點(diǎn)3訪問(wèn)到，等等。對(duì)該站點(diǎn)集合
進(jìn)行裁減使其仍然滿足條件a和b，并使得其鏈接總數(shù)之和為最小的結(jié)果為：
   s 1 2 3 4
   1 / 0 0 0
   2 0 / 0 0
   3 2 0 / 2
   4 0 1 4 /
這里，站點(diǎn)4可以訪問(wèn)到站點(diǎn)3和2，站點(diǎn)4也可以訪問(wèn)到站點(diǎn)1（通過(guò)站點(diǎn)3間接訪問(wèn)）；
此外，站點(diǎn)3可以訪問(wèn)到站點(diǎn)4；最小鏈接總數(shù)相加為2＋2＋1＋4=9。

  輸入數(shù)據(jù)：
程序讀入已被命名為sites.txt的完全如上所示的N*N矩陣的輸入數(shù)據(jù)文本文件，N不大于
10萬(wàn)（N即為行數(shù)和列數(shù)），輸入文件的每一行的列和列之間用一個(gè)\\t分隔，行和行之
間用\\n分隔。
  輸出數(shù)據(jù)：
按行輸出滿足題目要求的每個(gè)子集內(nèi)的站點(diǎn)數(shù)以及裁減后的最小鏈接總數(shù)之和，數(shù)和數(shù)
之間都以一個(gè)空格分隔。如上述子集和最小鏈接總數(shù)為：
1 2 3 4 9
如果輸入數(shù)據(jù)無(wú)滿足題目要求的子集存在，則輸出NONE。

評(píng)分標(biāo)準(zhǔn)：
在結(jié)果正確的前提下，會(huì)考慮程序的運(yùn)行時(shí)間。我們會(huì)用兩個(gè)不同的輸入數(shù)據(jù)文件（一
個(gè)簡(jiǎn)單一個(gè)復(fù)雜）進(jìn)行測(cè)試，簡(jiǎn)單的輸入數(shù)據(jù)產(chǎn)生的程序輸出結(jié)果如果正確，獲該題滿
分的30%即15分（不處理運(yùn)行時(shí)間，除非因程序錯(cuò)誤引起的超時(shí)運(yùn)行）；復(fù)雜的輸入數(shù)據(jù)
產(chǎn)生的程序輸出結(jié)果如果正確，獲50%即25分，運(yùn)行時(shí)間滿分為20%即10分，按各自程序
的運(yùn)行時(shí)間在所有參賽選手的程序的運(yùn)行時(shí)間中所占位置獲得相應(yīng)比例。請(qǐng)仔細(xì)閱讀并
遵守"輸入數(shù)據(jù)"和"輸出數(shù)據(jù)"中的格式要求，如不符合要求，我們的自動(dòng)評(píng)分程序可能
會(huì)判定程序不正確。

第二題（共兩題100分）決策系統(tǒng)（50分）

  題目描述：
一個(gè)智能決策系統(tǒng)可以由規(guī)則庫(kù)和事實(shí)庫(kù)兩部分組成，假定規(guī)則庫(kù)的形式為：
   Ri C1 & C2 & … & Cn->A
表示在條件C1，C2，… 和Cn都滿足的前提下，結(jié)論A成立（即采取行動(dòng)A）；Ri表示這是
規(guī)則庫(kù)中的第i條規(guī)則。事實(shí)庫(kù)則由若干為真的條件（即命題）所組成。
對(duì)一個(gè)新的待驗(yàn)證的命題Q，可使用數(shù)據(jù)驅(qū)動(dòng)或目標(biāo)驅(qū)動(dòng)兩種推理方式之一，來(lái)確認(rèn)它是
否可由某規(guī)則庫(kù)和事實(shí)庫(kù)推出：
1） 數(shù)據(jù)驅(qū)動(dòng)的推理是指從事實(shí)庫(kù)開(kāi)始，每次試圖發(fā)現(xiàn)規(guī)則庫(kù)中某條能滿足所有條件的
規(guī)則，并將其結(jié)論作為新的事實(shí)加入事實(shí)庫(kù)，然后重復(fù)此過(guò)程，直至發(fā)現(xiàn)Q是一個(gè)事實(shí)或
沒(méi)有任何新的事實(shí)可被發(fā)現(xiàn)；
2） 目標(biāo)驅(qū)動(dòng)的推理是指從目標(biāo)假設(shè)Q出發(fā)，每次試圖發(fā)現(xiàn)規(guī)則庫(kù)中某條含該假設(shè)的規(guī)
則，然后將該規(guī)則的前提作為子目標(biāo)，確認(rèn)這些子目標(biāo)是否和事實(shí)庫(kù)中的事實(shí)相匹配，
如果沒(méi)有全部匹配，則重復(fù)此過(guò)程，直至發(fā)現(xiàn)新的子目標(biāo)都為真或不能再驗(yàn)證子目標(biāo)是
否為真。

例如，一個(gè)規(guī)則庫(kù)為：
   R1 X & B & E -> Y
   R2 Y & D -> Z
   R3 A->X
事實(shí)庫(kù)為：
   A
   B
   C
   D
   E
如果想知道命題Z是否為真，數(shù)據(jù)驅(qū)動(dòng)的推理是從A B C D E開(kāi)始，依次匹配規(guī)則R3（得
到新事實(shí)X），R1（得到新事實(shí)Y）和R2，得到Z為真的事實(shí)；目標(biāo)驅(qū)動(dòng)的推理是從假設(shè)目
標(biāo)Z開(kāi)始，依次匹配規(guī)則R2（得到新的子目標(biāo)Y），R1（得到新的子目標(biāo)X）和R3，得到假
設(shè)Z為真的結(jié)論。

請(qǐng)編寫(xiě)程序正確、高效的實(shí)現(xiàn)這兩種推理方式。

  輸入數(shù)據(jù)：
程序需要兩個(gè)命令行參數(shù)：
1） <推理方式>：data|goal，分別表示程序應(yīng)采用數(shù)據(jù)驅(qū)動(dòng)的推理或目標(biāo)驅(qū)動(dòng)的推理；
2） <命題>：如Z。
此外，程序還需讀入已被命名為rules.txt的規(guī)則庫(kù)和已被命名為facts.txt的事實(shí)庫(kù)。
規(guī)則庫(kù)中的規(guī)則可能在千量級(jí)，按R1,R2,R3…依次按行排列的，每行一條規(guī)則，每條規(guī)
則都以Ri C1 & C2 & … & Cn->A的形式表示，Ri和C1之間有1個(gè)或多個(gè)空格，Ci和&之
間，Cn和->之間，以及->和A之間可以有0或多個(gè)空格。事實(shí)庫(kù)中的各事實(shí)之間用1個(gè)\\n
隔開(kāi)，每行一個(gè)事實(shí)。
  輸出數(shù)據(jù)：
如果Z能被推理為真，則輸出：
TRUE <推理方式：data或goal> <用空格隔開(kāi)的規(guī)則序列：以在所輸入的推理方式下，推
出該命題為真的規(guī)則被激活的順序排列>
例如：TRUE goal R2 R1 R3
如果Z不能被推理為真，輸出：
UNCERTAIN

  評(píng)分標(biāo)準(zhǔn)：
在結(jié)果正確的前提下，會(huì)考慮程序的運(yùn)行時(shí)間。我們會(huì)用兩組不同的輸入數(shù)據(jù)文件（一
個(gè)簡(jiǎn)單一個(gè)復(fù)雜）進(jìn)行測(cè)試，簡(jiǎn)單的輸入數(shù)據(jù)產(chǎn)生的程序輸出結(jié)果如果正確，獲該題滿
分的20%即10分（不處理運(yùn)行時(shí)間，除非因程序錯(cuò)誤引起的超時(shí)運(yùn)行）；復(fù)雜的輸入數(shù)據(jù)
產(chǎn)生的程序輸出結(jié)果如果正確，獲40%即20分，運(yùn)行時(shí)間滿分為40%即20分，按各自程序
的運(yùn)行時(shí)間在所有參賽選手的程序的運(yùn)行時(shí)間中所占位置獲得相應(yīng)比例。兩種推理方式
各占一半的分?jǐn)?shù)。請(qǐng)仔細(xì)閱讀并遵守"輸入數(shù)據(jù)"和"輸出數(shù)據(jù)"中的格式要求，如不符合
要求，我們的自動(dòng)評(píng)分程序可能會(huì)判定程序不正確。