Posted on 2008-10-16 09:18
歲月流逝 閱讀(147)
評論(0) 編輯 收藏 引用
第一題（共兩題100分）站點統計（50分）
題目描述：
一個Internet站點集合，可以用如下的方式來描述站點和站點之間的鏈接引用關系：
s 1 2 3 4
1 / 4 0 3
2 3 / 4 5
3 2 2 / 2
4 6 1 4 /
其中與s(site)同行和同列的數字都表示站點號，其他每個數字表示一個站點到另一個站
點的超文本鏈接數。如果站點A有到另一個站點B的直接鏈接或間接（指通過一個或多個
直接鏈接）鏈接，則稱站點A有到站點B的訪問關系，或稱站點B可以被站點A訪問到。例
如，上面描述了一個有4個站點鏈接關系的站點集合，第一行 / 4 0 3 表示站點1到站點
1，2，3，4的超文本鏈接數。
請編寫程序:
1） 將一個有N個站點的集合劃分成滿足下面所有條件的站點子集（這些子集的union組
成了該N個站點集合）：
a) 當任一子集中的站點數大于1時，該子集內至少存在一個站點有到該子集內所有
其他站點的訪問關系；
b) 當任一子集中的站點數大于1時，該子集內的任一站點至少可以被該子集內的某
一站點訪問到；
c) 兩個不同子集中的任意兩個站點之間不存在任何訪問關系。
2） 裁減這些子集內的站點之間現有的鏈接關系，使得被裁減后的各子集內的站點依然
可以滿足上述所有條件，同時使得子集內的站點之間的鏈接總數相加之和為最小。
假如上面的站點集合是這N個站點集合中的一個子集，它滿足了條件a)：4可以訪問到3，
也可以訪問到2和1；也滿足了條件b)：站點4可以被站點3訪問到，等等。對該站點集合
進行裁減使其仍然滿足條件a和b，并使得其鏈接總數之和為最小的結果為：
s 1 2 3 4
1 / 0 0 0
2 0 / 0 0
3 2 0 / 2
4 0 1 4 /
這里，站點4可以訪問到站點3和2，站點4也可以訪問到站點1（通過站點3間接訪問）；
此外，站點3可以訪問到站點4；最小鏈接總數相加為2＋2＋1＋4=9。
輸入數據：
程序讀入已被命名為sites.txt的完全如上所示的N*N矩陣的輸入數據文本文件，N不大于
10萬（N即為行數和列數），輸入文件的每一行的列和列之間用一個\\t分隔，行和行之
間用\\n分隔。
輸出數據：
按行輸出滿足題目要求的每個子集內的站點數以及裁減后的最小鏈接總數之和，數和數
之間都以一個空格分隔。如上述子集和最小鏈接總數為：
1 2 3 4 9
如果輸入數據無滿足題目要求的子集存在，則輸出NONE。
評分標準：
在結果正確的前提下，會考慮程序的運行時間。我們會用兩個不同的輸入數據文件（一
個簡單一個復雜）進行測試，簡單的輸入數據產生的程序輸出結果如果正確，獲該題滿
分的30%即15分（不處理運行時間，除非因程序錯誤引起的超時運行）；復雜的輸入數據
產生的程序輸出結果如果正確，獲50%即25分，運行時間滿分為20%即10分，按各自程序
的運行時間在所有參賽選手的程序的運行時間中所占位置獲得相應比例。請仔細閱讀并
遵守"輸入數據"和"輸出數據"中的格式要求，如不符合要求，我們的自動評分程序可能
會判定程序不正確。
第二題（共兩題100分）決策系統（50分）
題目描述：
一個智能決策系統可以由規則庫和事實庫兩部分組成，假定規則庫的形式為：
Ri C1 & C2 & … & Cn->A
表示在條件C1，C2，… 和Cn都滿足的前提下，結論A成立（即采取行動A）；Ri表示這是
規則庫中的第i條規則。事實庫則由若干為真的條件（即命題）所組成。
對一個新的待驗證的命題Q，可使用數據驅動或目標驅動兩種推理方式之一，來確認它是
否可由某規則庫和事實庫推出：
1） 數據驅動的推理是指從事實庫開始，每次試圖發現規則庫中某條能滿足所有條件的
規則，并將其結論作為新的事實加入事實庫，然后重復此過程，直至發現Q是一個事實或
沒有任何新的事實可被發現；
2） 目標驅動的推理是指從目標假設Q出發，每次試圖發現規則庫中某條含該假設的規
則，然后將該規則的前提作為子目標，確認這些子目標是否和事實庫中的事實相匹配，
如果沒有全部匹配，則重復此過程，直至發現新的子目標都為真或不能再驗證子目標是
否為真。
例如，一個規則庫為：
R1 X & B & E -> Y
R2 Y & D -> Z
R3 A->X
事實庫為：
A
B
C
D
E
如果想知道命題Z是否為真，數據驅動的推理是從A B C D E開始，依次匹配規則R3（得
到新事實X），R1（得到新事實Y）和R2，得到Z為真的事實；目標驅動的推理是從假設目
標Z開始，依次匹配規則R2（得到新的子目標Y），R1（得到新的子目標X）和R3，得到假
設Z為真的結論。
請編寫程序正確、高效的實現這兩種推理方式。
輸入數據：
程序需要兩個命令行參數：
1） <推理方式>：data|goal，分別表示程序應采用數據驅動的推理或目標驅動的推理；
2） <命題>：如Z。
此外，程序還需讀入已被命名為rules.txt的規則庫和已被命名為facts.txt的事實庫。
規則庫中的規則可能在千量級，按R1,R2,R3…依次按行排列的，每行一條規則，每條規
則都以Ri C1 & C2 & … & Cn->A的形式表示，Ri和C1之間有1個或多個空格，Ci和&之
間，Cn和->之間，以及->和A之間可以有0或多個空格。事實庫中的各事實之間用1個\\n
隔開，每行一個事實。
輸出數據：
如果Z能被推理為真，則輸出：
TRUE <推理方式：data或goal> <用空格隔開的規則序列：以在所輸入的推理方式下，推
出該命題為真的規則被激活的順序排列>
例如：TRUE goal R2 R1 R3
如果Z不能被推理為真，輸出：
UNCERTAIN
評分標準：
在結果正確的前提下，會考慮程序的運行時間。我們會用兩組不同的輸入數據文件（一
個簡單一個復雜）進行測試，簡單的輸入數據產生的程序輸出結果如果正確，獲該題滿
分的20%即10分（不處理運行時間，除非因程序錯誤引起的超時運行）；復雜的輸入數據
產生的程序輸出結果如果正確，獲40%即20分，運行時間滿分為40%即20分，按各自程序
的運行時間在所有參賽選手的程序的運行時間中所占位置獲得相應比例。兩種推理方式
各占一半的分數。請仔細閱讀并遵守"輸入數據"和"輸出數據"中的格式要求，如不符合
要求，我們的自動評分程序可能會判定程序不正確。