最小化的總線改變的數量以矩陣

[ 42, 45, 47, x, x] -> stop1 to stop2 
[ 45, 47, 42, 88, x] -> stop2 to stop3 
[ 21, 77, 42, x, x] -> stop3 to stop4 
[ 22, 47, 42, 88, x] -> stop4 to stop5 
[ 23, 47, 42, x, x] -> stop5 to stop6 
[ 24, 47, 42, 8, 91] -> stop6 to stop7 
[ 25, 13, 42, 3, 84] -> stop7 to stop8 
[ 26, 10, 11, 4, 54] -> stop8 to stop9 
[ 27, 9, 8, 88, 71] -> stop9 to stop10

x is there just for formatting. The first row means that there are only three buses from stop1 to stop2(42, 45, 47).最小化的總線改變的數量以矩陣

我有這樣的矩陣狀的結構，其中每一行代表了從總線一站式到另一個。我需要儘量減少一個人從停車1轉到停車10所需的公交車數量。

例如，其中一個輸出應該是42,42,42,42,42,42,42,26,27，另一個可以是42,42,42,42,42,42,42,10,9。如果更改次數超過三次，我可以放棄結果。

什麼是實現這一目標的蠻力通過它迫使最優化的方式是非常效率不高的權利嗎？

來源

2017-06-15 Angersmash

我認爲這是可行的，通過形成一個公交車站作爲頂點和不同公共汽車作爲這些頂點之間的邊緣的圖形，讓我試試看:) – zenwraight

@zenwraight這實際上是一個圖形數據庫的結果查詢。我們需要減少節點之間的邊緣數量，所以儘管我們可以處理初始結果（上面的矩陣），以最小化一個人不得不做出的總線變化數量。 – Angersmash

Ohk順便說一下，在兩個輸出中，您錯過了從停止點7到停止點8的公共汽車路線......請檢查它，所以您需要一種方法來預處理此輸入，以減少圖形數據庫查詢的計算時間嗎？嗯 – zenwraight

您可以通過陣列一次，並保留一套共同的訪問停靠站。一旦找不到這樣的公交車，就拿上一組公交車，從中選擇一輛公交車，然後用那輛公交車把結果填入這麼多站。

然後把所有的公交車停在當前的停車位上，並重復後續停車等操作。

這是在ES6 JavaScript中編碼的算法。它使用Set來允許對其存儲的項目（總線）進行恆定時間訪問。

// Helper function: given a reduced set of buses, and a count, 
 
// add one of those buses as the bus to take during that many stops 
 
function addToResult(common, count, result) { 
 
    let bus = common.values().next().value; // pick any available bus 
 
    while (count > 0) { 
 
     result.push(bus); 
 
     count--; 
 
    } 
 
} 
 

 
// Main algorithm 
 
function getBusRide(stops) { 
 
    if (stops.length === 0) return []; 
 

 
    let result = [], 
 
     count = 0, 
 
     common; 
 
    for (let buses of stops) { 
 
     if (count == 0) { // First iteration only 
 
      common = new Set(buses); // all buses are candidate 
 
      count = 1; 
 
     } else { 
 
      let keep = new Set(); 
 
      for (let bus of buses) { 
 
       // Only keep buses as candidate when they 
 
       //  are still served here 
 
       if (common.has(bus)) keep.add(bus); 
 
      } 
 
      if (keep.size == 0) { // Need to change bus 
 
       addToResult(common, count, result); 
 
       count = 0; 
 
       keep = new Set(buses); // all buses are candidate 
 
      } 
 
      common = keep; 
 
      count++; 
 
     } 
 
    } 
 
    addToResult(common, count, result); 
 
    return result; 
 
} 
 

 
// Sample input 
 
const stops = [ 
 
    [ 42, 45, 47], 
 
    [ 45, 47, 42, 88], 
 
    [ 21, 77, 42], 
 
    [ 22, 47, 42, 88], 
 
    [ 23, 47, 42], 
 
    [ 24, 47, 42, 8, 91], 
 
    [ 25, 13, 42, 3, 84], 
 
    [ 26, 10, 11, 4, 54], 
 
    [ 27, 9, 8, 88, 71] 
 
]; 
 

 
// Apply the algorithm 
 
console.log(getBusRide(stops));

.as-console-wrapper { max-height: 100% !important; top: 0; }

該算法在運行爲O（n），其中Ñ是在輸入值的總數，因此，在該示例N = 37。

來源

2017-06-15 20:44:51 trincot

謝謝，這是非常有幫助的。我正在瞄準這樣的事情。 – Angersmash

您可以通過模擬它作爲一個圖搜索解決這個問題。

想象一下，你是一個人，你想從A點到達B點與你最相關的信息是

您當前所在，並
其中公交線路，如果有的話，你目前在。

因此，您可以將一個人的狀態建模爲一對位置（公共汽車站）和公共汽車線（當它們開始或結束時可能「不在一條線上」）。因此，爲位置和總線的每個組合創建一個節點的圖形。

在此圖中的邊對應於在狀態改變。您可以通過

停留在你目前的公交線路，並打算改變狀態無論是什麼地方，或
切換公交線路。

如果您當前在公交線路上，則可以保持該線路從一個位置移動到另一個位置，如果線路從第一個位置移動到第二個位置。因此，如果總線行從位置1變爲位置2，則創建邊（（位置1,行），（位置2,行））。這不涉及轉移，所以給這條邊的0

成本或者，您也可以隨時下車，巴士或從截止巴士到是在公共汽車上走。所以添加的每一行的邊緣（（位置，線），（位置，免費）），並且每個位置（你總是要下車公交線路的選擇），並給它的成本爲0，因爲這並未不涉及改變線條。類似地，在給定位置處可用的每條總線線添加邊緣（（位置，免費），（位置，線））。給它1美元的成本以表明這需要你上車。

現在，想象一下你找到一個從（A點免費）在該圖路徑（點B，免費）。這對應於在A點開始並在B點結束的一系列公交車上下車，並且成本將是您最終上車的不同公交車的數量。如果你在這個圖中運行最短路徑算法（比如說Dijkstra算法），你可以找到從開始到結束點的路徑，以最小化總線傳輸數量！

來源

2017-06-15 16:09:41 templatetypedef

最小化的總線改變的數量以矩陣

回答

相關問題