糖果傳遞問題之研究與推廣
n個人圍成一圈,面向圓心,且逆時針編號1,2,……,n。一開始每人手中有一個糖果,由1號開始,逆時針分別給右邊的人一個、兩個、一個、兩個……糖果,手上沒有糖果的人必須退出。我們將此傳遞規則定義為T_1,2,同理T_(1,2⋯,p)。這個傳遞遊戲,最終會有兩種情形,第一種是由一人獨得所有糖果(成功狀態),第二種是數人間傳遞糖果且形成循環(循環狀態)。 研究後得知,在傳遞規則T_(1,2⋯,p) (p≥2)下,若p=〖p_1〗^(α_1 ) 〖p_2〗^(α_2 )⋯〖p_i〗^(α_i )⋯〖p_j〗^(α_j ) ( 為p的相異質因數),任意的n值(n≥p+1)均可唯一表示成n=(p)^t×(〖p_1〗^(s_1 ) 〖p_2〗^(s_2 )⋯〖p_i〗^(s_i )⋅m)+q (t,m∈N, p ∤〖p_1〗^(s_1 ) 〖p_2〗^(s_2 )⋯〖p_i〗^(s_i ), (m,p)=1, q=1,2,⋯,p),令S=(p^t (p-q)+(pq-1))/(p-1)+R⋅p^t,則當m=1時,最終為成功狀態,且獨得糖果者的初始編號為S;當m≥2時,最終為循環狀態,且由m人循環傳遞糖果,而此m人的初始編號是S, S+p^t 〖p_1〗^(s_1 ) 〖p_2〗^(s_2 )⋯〖p_i〗^(s_i ), ⋯⋯ , S+(m-1)⋅p^t 〖p_1〗^(s_1 ) 〖p_2〗^(s_2 )⋯〖p_i〗^(s_i )。上述公式中的R值,可透過我們研究出來的「R值迭代法」求得。更進一步,我們也找出達到成功狀態或循環狀態的最小傳遞數。
Reduction of traffic congestion in España Boulevard using graph theory
There have been numerous studies exploring the applications of graph theory in traffic management, often finding ways to reduce traffic congestion and make traveling more efficient. Such studies will be beneficial when applied to heavily congested areas such as España Boulevard, one of the busiest thoroughfares in Manila. This paper aimed tooptimize the road map of España Boulevard using graph theory. The current road map of España Boulevard was represented as a directed graphand subjected to the mutation method of edge removal, wherein an edge isremoved in each mutation based on a computed fitness function, F(G),which depicts better efficiency at lower values. Edges were removed until the graph got disconnected, which was tested using the Floyd-Warshall algorithm. The 28th mutation resulted in a minimum F(G) value of 144.4; this is a 50.18% decrease from the F(G) of the original graph, which is 290. After the 28th mutation, the removals resulted in an increase in the F(G). As a result, the final mutation resulted in an F(G) of 311.89, which characterized a less efficient graph. This study was able to apply graph theory concepts to optimize the España Boulevard road map using the mutation method, minimizing its F(G) by at most 50.18%. For future studies, the practicality of the alternate road map may be tested in simulations to examine its efficiency when other factors, such as traffic volume, are introduced.