廣播問題與行動計劃問題

Abstract

這篇論文考慮以下兩個性質類似的問題：通訊綱路的集合對集合廣播和群儲行動計劃 。 在第一部份我們考慮廣播問題。用圖的頂點表示人，邊表示兩人間的電話線。開始時 每人只知道一個消息，而且不知道其他人的消息。大家用電話傳遞消息，兩個人每通 話一次用掉一單位時間並交換所有消息。假設有兩個非空頂點集合，這部份的主要目 的在研究集合對集合的最小廣播數和最小廣播時間。我們給出公式求完備圖的最小廣 播數和提出演算法解樹形圖的最小廣播數和最小廣播時間。 在第二部份我們考慮行動計劃問題。一些物件放置在加權圖的頂點上，一輛車子穿越 圖上的邊而將物件搬運到它的目的地。車子一次只能載運一個物件，并且在結束時回 到起始點。在這問題中，緩喳點和儲存點各構成一集合，物件放置在緩喳點上須要被 運送到儲存點。這部份的主要目的在決定一個最短行程將所有物件從原先位置移到目 的地。我們提出演算法在路徑圖上解這個問題。