基于分治法的循環日程賽系統的研究

摘 要：本文針對以往傳統的日程賽安排系統容易受到參賽規模問題變復雜的不利因素，提出了一種利用分治思想和循環賽安排方法相融合的算法，有效地提高了比賽日程安排的準確率。

關鍵詞：分治法;循環日程賽;算法分析

近幾年來，由于賽事日程安排制度的不斷改革，各級日程安排崗位對日程安排信息管理信息化的需求與日俱增。因為對大多數的循環賽日程管理者而言，如何有效地管理循環賽的日程安排，使其發揮最大的效率，是每位循環賽日程管理者所面臨的難題及挑戰。所以日程安排管理系統成了循環賽日程管理的重中之重。

在以人為本的理念下，循環賽安排管理在賽事組織中的作用日益突出。但是，人員的復雜性和組織的公正、公開使得日程安排的管理成為難題。基于現今對循環賽事要求越來越高的趨勢，日程安排管理系統將成為循環賽日程管理的一個非常重要的內容。日程安排管理系統的作用之一是規劃日程安排，幫助管理者建立日程安排檔案。它很好地利用分治的思想，使賽事安排變得合理、簡單。它的出現使得日程安排檔案查詢、調用的速度加快，也使得精確分析大量參賽隊員的知識、經驗、技術、能力成為可能。所以，實現循環賽日程安排管理系統的公正化、數字化、科學化和網絡化是非常有必要的。

一、分治思想

1.分治思想的概念

對于一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小）則直接解決，否則將其分解為k個規模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設計策略叫做分治法。如果原問題可分割成k個子問題，1lt;k≤n，且這些子問題都可解，并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。分治與遞歸像一對孿生兄弟，經常同時應用在算法設計之中，并由此產生許多高效算法。

2.分治法的適用條件

用分治法求解的問題一般都滿足以下幾個條件：（1）該問題的規模縮小到一定的程度就可以容易地解決。（2）該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質。（3）利用該問題分解出的子問題的解可以合并為該問題的解。能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動態規劃。（4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。這條特征涉及分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然也可用分治法，但一般用動態規劃較好。

3.分治法的求解步驟

首先，分解子問題。如果問題規模很小，直接就能求出問題的解，可以不用分解問題，否則就以遞歸方式不斷分解子問題，直到每個子問題都能直接求解為止。然后，遞歸地求解子問題。最后，合并子問題的解，分治法的合并步驟是算法的關鍵所在。有些問題的合并方法比較明顯，有些問題合并方法比較復雜，或者是有多種合并方案，或者是合并方案不明顯。究竟應該怎樣合并，沒有統一的模式，需要具體問題具體分析。

二、算法設計

1.日程賽問題概述

設有n=2k個運動員要進行網球循環賽。現要設計一個滿足要求的比賽日程表。（1）每個選手必須與其他n-1個選手個比賽一次;（2）每個選手一天只能賽一次;（3）循環賽一共進行n-1天。按此要求可將比賽日程設計成有n行和n-1列的表。在表中的第i行和第j列處填入第i個選手在第j天遇到的選手。

2.算法應用

按分治策略，我們可以將所有的選手分為兩半，則n個選手的比賽日程表可以通過n/2個選手的比賽日程表來決定。遞歸地用這種一分為二的策略對選手進行劃分，直到只剩下兩個選手時，比賽日程表的制定就變得很簡單。這時只要讓這兩個選手進行比賽就可以了。

分析過程具體如下：

若n=1，賽程表如表1。

表1

[1]

若n=2，賽程表如表2。

表2

[1][1][2][2]

若n=3，則：（1）添加一個虛擬選手4號，構成n+1=4。（2）因為4/2=2，所以把參賽選手分兩組，每組各自安排（1 2），（3 4）。每組跟另一組分別比賽（拷貝），四個選手比賽的賽程如表3。

" " " " 表3

以此類推，若n=8，那賽程如表4。

表4

歸納起來，算法步驟如下：

（1）如果n為偶數，可分為兩個n/2人的組分別比賽，然后兩組間比賽;如果n/2為偶數，左下角為左上角加n/2來得到，然后左下角拷貝到右上角，左上角拷貝到右下角;如果n/2為奇數，先安排左下角（除0外都加n/2），然后把同一天都有空的選手安排比賽。然后，右上角要按規則一來完成，右下角由規則二來定。

（2）如果n為奇數，則加1個選手使n+1成為偶數。轉化成偶數名選手的賽程安排問題來解決。最后把虛擬選手n+1號所在位置上的值置為0，即完成安排。

三、結論

在本文中，筆者提出了一種基于分治思想的循環日程賽安排問題的算法，將分治思想應用在日程賽安排問題中。由于分治法的分解、求解、合并能讓復雜的問題簡單化，賽程安排問題的求解難度取決于參賽規模，為了有效實現賽程安排，我們設計了一種將分治思想與賽程安排方法相融合的算法。本文算法可以用網絡軟件開發成系統，推廣應用于各種競賽活動中。

參考文獻：

[1]汪力君.分治算法在排課系統中的分析與應用[J].安徽建筑工業學院學報（自然科學版），2007，15（6）.

[2]霍紅衛.算法設計與分析[M].西安：西安電子科技大學出版社，2005.

[3]王海源.分治算法的兩種思路和形式[J].上海師范大學學報（自然科學版），2003（1）.