Abstract
本文嘗試研究在單一匯流排傳播通訊模型上，如何設計分散式的分支界定計算方法。此模型可應用在區域網路上。由匯流排連接各獨立電腦系統，並以傳播法作為各電腦之間的通訊。我們分割求解問題的解答域，將之分配於各電腦同時進行計算。對解答域如何分割，我們提出一不同於傳統的選取法則，以期使解答域中的臨界節點能儘量平均分配到各電腦中。在求極小值的問題中，分支界定計算方法有一上界值，能夠隨時界定各分支，避免無用的計算。但在本文的模型與計算方法中，各電腦並不需隨時傳播此上界值，亦能達到最好的結果。我們證明了這一點，使得整個計算方法所需的通訊時間減至最低的固定時間。在分支界定計算方法中，若使用不同的選取法則，將產生不同結構的解域二元樹，其計算所需時間也可能不相同。何者為優，何者為劣，並無定論。我們提出一個多種選取法則的方法。利用多處理器的優點，再靠匯流排傳播上界值，以增快計算速度。實驗結果證明分割解域的方法可達到很好的結果。而多種選取法則的方法只對某些特殊的問題有改善。