自動排名演算法的改良及延伸

本論文主要介紹了幾個關於鏈圖修改的問題。在我們探討的問題中會有兩個集合，一個是參加者的集合、另一個則是本次競賽的問題集合。若參賽者答對某個問題，則我們在代表該參賽者的點與代表該問題的點之間加上一條邊。因此，我們可以藉由連接到參賽者點的邊數來區分參賽者實力的強弱。在理想的狀態下，實力強的參賽者答對的題目會是實力弱者答對題目的母集合。同樣的，答對較簡單的問題的參賽者所形成的集合應該是答對較難問題的參賽者的母集合。但是在現實情況，實力強的參賽者可能因為粗心而答錯較簡單的題目，實力弱者可能因為運氣好而猜對較難的題目。而在論文中，我們假設某些問題是沒有鑑別度的，或是某些參賽者的答題情況不具有參考價值。因此，我們的目標是刪除雙分圖中最少的點數，使得此雙分圖變為有序的鏈圖。另一方面，若競賽中允許組隊，我們也提出了一個演算法來估計個隊伍最接近真實實力的排名。最後，假設各參賽者可以在各題中獲取部份分數，在本文中也提供了一個多項式時間的演算法來獲取最接近此參賽者的各提估計分數。

關鍵字

自動排名；鏈圖；非遞減數列

並列摘要

We introduce some variants of Chain Editing problem. In our version of Chain Editing, we are given a set of participants and a set of questions. If a participant answer a question correctly, we add a edge between the participant and the question. Therefore we can distinguish the participants’ ability to solve questions by the degrees of nodes. These nodes stand for the participants. In an ideal world, a stronger participant answers correctly a superset of questions that a weaker participant answers correctly. Similarly, a easier question should be answered correctly by a superset of participants who answers a more difficult question correctly. In reality, it may happen that a stronger have given a wrong answer for a easier question. We assume that some questions are not suitable for the contest. Therefore our goal is to find a perfect nesting of the participant-question relations by deleting a minimum number of questions. In addition, we introduce a variant of the Chain Editing problem for the situation that participants can forms teams for the ranking. Finally, we design an algorithm to get the nearest ideal list of points of a participant when participants can get partial points from each questions.