如何查找使用R的有向圖中兩個頂點之間的行進時間

Question

我試圖解決一個關於電話調用模擬的非常簡單的問題。我可以只介紹所有的數據並寫出一個非常冗長的代碼，但我試圖用圖形解決它，也許在R（或類似的東西）上的包「igraph」，但我從來沒有用過它。

爲簡單起見，我想打從紐約到莫斯科的一個電話，到達莫斯科，信號可經過3個城市有不同的概率：

• 呼叫將經過倫敦一個0.2的概率
• 巴黎用0.3概率
• 柏林0.5概率

的時間的城市之間旅行的信號遵循正態分佈。爲了簡單起見，說所有的時間都遵循標準的正態分佈。因此，例如，該標誌使用0.2分鐘從倫敦前往莫斯科。

所以，我有這樣的畫面在腦海：

http://i.imgur.com/X4WnyxO.jpg

邊緣上的數字是，信號將遵循該路徑的概率。

現在，我將不得不模擬信號的旅行時間，並說從紐約到莫斯科的平均時間是多少。

我的問題是如何編程這個問題，因爲我不知道如何獲得兩個權重的邊緣，我不知道如何循環通過頂點。

任何建議，你可以給我會很有幫助。

Answer 1

這樣做的一種方法是使用蒙特卡洛模擬。下面的例子只是爲了讓你開始。

假設您有三個城市L，P和B.呼叫路由分別爲（0.2,0.3,0.5）。呼叫通過給定城市所花費的時間通常以平均值取決於城市，標準偏差= 1（例如毫秒）。在本例中，我將L，P，B的平均時間分別定義爲（30 ms，20 ms，10 ms）。這是關於定義在城市中旅行需要多長時間的意見。

然後，我們使用下面的代碼進行模擬。

Monte.Carlo <- function(df) { 
    set.seed(1) 
    path <- sample(df$cities, 1000, p=c(0.2,0.3,0.5), replace=T) 
    mu  <- df[match(path,df$cities),]$t.mean 
    time <- sapply(mu,function(mu)rnorm(1,mu)) 
} 
par(mfrow=c(3,1)) 
cities <- c("L","P","B") 
t.mean <- c(30,20,10) 
df  <- data.frame(cities,t.mean) 
hist(Monte.Carlo(df), breaks=50, xlim=c(5,35),main="(L,P,B)=(30,20,10)") 
t.mean <- c(25,20,15) 
df  <- data.frame(cities,t.mean) 
hist(Monte.Carlo(df), breaks=50, xlim=c(5,35), main="(L,P,B)=(25,20,15)") 
t.mean <- c(22,20,18) 
df  <- data.frame(cities,t.mean) 
hist(Monte.Carlo(df), breaks=50, xlim=c(5,35), main="(L,P,B)=(22,20,18)") 

仿真過程如下：

1. 定義path向量其指示哪個城市的呼叫被路由通過，對於每個1000級的呼叫。這是一個「L」，「P」或「B」的隨機向量，其中有問題陳述中給出的概率。
2. 使用df中的定義將城市「名稱」映射爲平均時間。
3. 對於path中的每個呼叫，計算路由時間作爲具有適當均值的正態分佈的單個隨機樣本。

然後，我們使用不同的平均佈線時間定義運行模擬三次。在第一種情況下請注意大部分通話需要大約10ms。這是因爲根據我們的定義，通過B（erlin）的路由平均需要10ms，並且平均有50％的呼叫通過柏林。