Abstract
由於計算機軟硬體費用的大幅下降，分散式系統已成為最主要的應用系統。在分散式系統上為了整體的績效或分散式處理的緣故，我們必須在各網路節點間傳送檔案。因此如何以最有效的方法來傳送檔案便成為一個很重要的問題，這個問題我們稱之為檔案傳送問題。基本上檔案傳送問題可定義為〞給定一組檔案和一已知網路，以最少的時間或金錢將所有檔案傳送完畢。〞先前有關檔案傳送問題的研究主要可分為兩類，第一類的研究是由〔Ｃｏｆｆｍａｎ，Ｇａｒｅｙ，Ｊｏｈｎｓｏｎ ａｎｄ Ｌａｐａｕｇｈ １９８５〕和〔Ｃｈｏｉ，Ｈａｋｉｍｉ１９８７ａ， １９８７ｂ〕所提出的，基本上他們假設檔案是不可分割的，亦即一個檔案只能經由一條路徑傳送。第二類的研究主要是由〔Ｉｔａｉａｎｄ Ｒｏｄｅｈ １９８５〕所提出的，基本上他們假設檔案是可分割的，亦即一個檔案可以分割成多個小檔案，然後再為每一個小檔案找一條傳送路徑。當檔案是不可分割的時候，檔案傳送問題已被證明是ＮＰ－ｃｏｍｐｌｅｔｅ的問題。而且即使我們假設網路上只有三個節點時，這個問題仍然是ＮＰ－ｍｏｍｐｌｅｔｅ的問題。當檔案是可分割的時候，檔案傳送問題則被證明至少比多商品流量問題（Ｍｕｌｔｉｃｏｍｍｏｄｉｔｙ ｆｌｏｗ ｐｒｏｂｌｅｍ）難。從這兩個觀查我們可知檔案傳送問題是一個困難的問題，不大可能會有好的解答存在。因此在求解的程序上，我們將找出一些重要的特例，再一一針對每一個特例找出好且快的方法來解合。在本論文中，我們找到了四種特殊重要的情況，在每一情況裡，我們都能找出好且快的解答。這四種情況列示如下。１•檔案是可分割的而且在網路中存在有一個中心點使得所有檔案的傳送都必須經過該中心點。２•檔案是可分割的而且網路是全聯網路（Ｂｕｌｌｙ－ｃｏｎｎｅｃｔｅｄ）。３•檔案是不可分割的，網路是全聯網路（Ｂｕｌｌｙ－ｃｏｎｎｅｃｔｅｄ）且任一對網路節點之間傳送任一個檔案所須要的時間是一個常數。４•一個不可分割檔案的傳送。