單機半在線排序算法競爭比分析.pdf

1、排序算法的競爭比分析是排序問題對算法風(fēng)險的一種評估和保障，具有重要的理論意義和實用價值。在排序問題中，半在線排序所需的信息介于完全在線和完全離線的排序之間，比較符合實際應(yīng)用中的情況。近幾十年來，其研究得到了一定進展，形形色色的半在線排序問題和算法不斷涌現(xiàn)，但對于這些問題算法的競爭比分析幾乎處于空白。本文在經(jīng)典在線排序模型的基礎(chǔ)上，通過增加額外信息構(gòu)成半在線排序問題，借助一般在線算法性能分析的手段和方法，通過特有的實例轉(zhuǎn)換和分析，對單機最

2、小化完工時間問題、最小化加權(quán)完工時間問題和最小化折扣加權(quán)完工時間問題的半在線排序算法的性能進行了理論分析。首先，通過構(gòu)造極端最差實例的方法，分別得到了三種半在線排序問題的競爭比下界，從而確定了半在線排序算法針對這三種問題所能達到的性能極限。然后，對最小化完工時間證明了算法性能隨著實例空間的縮小而提升；對最小化加權(quán)完工時間問題，分析了哪些信息有助于改善算法性能；針對最小化折扣加權(quán)完工時間問題，設(shè)計了一個半在線排序算法，推導(dǎo)出該算法的競爭比

3、，證明了該算法在三類特殊的極限情況下是最優(yōu)算法。本文的主要研究成果包括：1)對基于經(jīng)典在線排序問題1| rj |？ Cj的半在線排序問題完善了一種半在線排序算法競爭比分析的證明過程，通過限制實例空間，證明了隨著實例空間的減小，算法性能會進一步提高。2)針對經(jīng)典在線問題，研究了該問題在已知未來多步到達時間，加工時間具有上下界限制，以及兩者情況皆已知條件下任意半在線算法的競爭比下界。證明了未來多步到達時間對競爭比下界沒有改善，但是加工時間限