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

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

假如上面的站點(diǎn)集合是這N個站點(diǎn)集合中的一個子集，它滿足了條件a)：4可以訪問到3，
也可以訪問到2和1；也滿足了條件b)：站點(diǎn)4可以被站點(diǎn)3訪問到，等等。對該站點(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可以訪問到站點(diǎn)3和2，站點(diǎn)4也可以訪問到站點(diǎn)1（通過站點(diǎn)3間接訪問）；
此外，站點(diǎn)3可以訪問到站點(diǎn)4；最小鏈接總數(shù)相加為2＋2＋1＋4=9。

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

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

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

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

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

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

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

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