題目 破局共享汽車
自 2015 年以來，共享汽車行業曾經“百花齊放”，多個專案獲得巨額融資，但因為模式過重、運營成本過高、無法盈利等問題，陸續有共享汽車公司因為資金鏈斷裂而倒閉，據易觀發布的《2019 中國共享汽車平臺創新白皮書》顯示，2019 年的共享汽車行業，是中小參與者不斷出局，頭部平臺拉動行業重啟增長的一年，而共享汽車增速在 2019 年 5–10 月達到 2.21%，超過網約車和線上租車，
據悉，共享汽車在市面上的停車位合作模式，主要是與停車場、小區進行合作，記者從共享汽車APP平臺上了解到，聯動云、gofun、摩范出行等共享汽車品牌都在優品匯停車場內設定停車位，從停車場的安保部門處獲悉，該處網點有二十來個共享汽車車位，采用租賃方式出租給共享汽車公司，但是由于商場位于市中心繁華地段，看似二十多個車位頗多，往往一會就停滿了，如果租賃車位已滿，共享汽車便只能再行找其他停車場了，
共享汽車在租賃停車位時，不同平臺會根據其公司戰略規劃和協商情況，在不同的網點租取不同個數的車位，一旦租的車位停滿后，用戶就無法進行還車，對于還車問題，記者通過各共享汽車品牌APP了解到，摩范出行采用“預約還車”的策略，gofun出行則采用“先到先得”的還車方式，
摩范出行的客服人員表示，“還車時需要提前預約，車位停滿后不可再停，只能去其他網點還車，”但在調查中，有用戶反映，開車到達一網點后，現場明明有還車位置，APP上卻顯示車位已滿，對此，摩范出行的客服人員做出了解釋，“因為這個車位已經被其他車主預約，即使車未到，仍然會為其保留車位，”不少用戶表示不能理解，如果預約車主最后并未選擇此處停車，就等于資源浪費，并且給其他車主帶來了不便，
gofun出行針對此情況進行了另外一種嘗試，“可以手動提前預約還車網點，但是還車網點的車位無法為用戶保留，哪位用戶先到達網點，就可先進行還車，”記者注意到，gofunAPP上除了顯示免費停車位外，也有超停還車費用的標識，對此，客服人員解釋，“即使免費停車位為0，也可以進行還車，但需要支付超停費用，價格為3-20元不等，是根據還車網點來決定的，”對于記者提出的還車難問題，客服人員表示，“確實存在這樣的情況，非常抱歉對用戶出行帶來不便，”
相較于摩范、gofun在下單前即可查看剩余車位的模式，聯動云租車APP上并未有此功能，“車位有限，只有在用戶還車時才會顯示剩余車位，用車前未下單是看不了的，”在APP上，一個停車網點上附有“部分免收取還車服務費（超停收費）”的字樣，客服人員向記者解釋，“用戶還車時，如果此網點車位已滿，就需去其他網點還車，如若停在此處，必須繳納100元超停費用，”
問題：
附件是共享汽車的位置資料集，資料集中提供了時間，經緯度等位置資訊，以及停車點上停放的車輛的數量和車輛表，請建立數學模型分析該城市的共享汽車使用分布情況，并且制定一個對企業最有利的共享汽車調度方案，
不多廢話直接上
計算程序
第1步：初始化距離，其實指與D直接連接的點的距離，dis[c]代表D到C點的最短距離，因而初始dis[C]=3，dis[E]=4，dis[D]=0，其余為無窮大，設定集合S用來表示已經找到的最短路徑，此時，S={D}，現在得到D到各點距離{D(0)，C(3)，E（4），F（），G（），B（），A()}，其中*代表未知數也可以說是無窮大，括號里面的數值代表D點到該點的最短距離，
第2步：不考慮集合S中的值，因為dis[C]=3，是當中距離最短的，所以此時更新S，S={D,C}，接著我們看與C連接的點，分別有B，E，F，已經在集合S中的不看，dis[C-B]=10，因而dis[B]=dis[C]+10=13，dis[F]=dis[C]+dis[C-F]=9，dis[E]=dis[C]+dis[C-E]=3+5=8>4(初始化時的dis[E]=4)不更新，此時{D(0)，C(3)，E（4），F（9），G（），B（13），A()}，
第3步：在第2步中，E點的值4最小，更新S={D，C，E}，此時看與E點直接連接的點，分別有F，G，dis[F]=dis[E]+dis[E-F]=4+2=6（比原來的值小，得到更新），dis[G]=dis[E]+dis[E-G]=4+8=12（更新），此時{D(0)，C(3)，E（4），F（6），G（12），B（13），A(*)}，
第4步：在第3步中，F點的值6最小，更新S={D，C，E，F}，此時看與F點直接連接的點，分別有B，A，G，dis[B]=dis[F]+dis[F-B]=6+7=13，dis[A]=dis[F]+dis[F-A]=6+16=22，dis[G]=dis[F]+dis[F-G]=6+9=15>12（不更新），此時{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.
第5步：在第4步中，G點的值12最小，更新S={D，C，E，F，G}，此時看與G點直接連接的點，只有A，dis[A]=dis[G]+dis[G-A]=12+14=26>22(不更新)，{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.
第6步：在第5步中，B點的值13最小，更新S={D，C，E，F，G，B}，此時看與B點直接連接的點，只有A，dis[A]=dis[B]+dis[B-A]=13+12=25>22(不更新)，{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.
進群討論即可
第6步：最后只剩下A值，直接進入集合S={D，C，E，F，G，B，A}，此時所有的點都已經遍歷結束，得到最終結果{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.
設Di,j,k為從i到j的只以(1…k)集合中的節點為中間節點的最短路徑的長度，
若最短路徑經過點k，則Di,j,k = Di,k,k-1 + Dk,j,k-1；
若最短路徑不經過點k，則Di,j,k = Di,j,k-1，
因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)，
在實際演算法中，為了節約空間，可以直接在原來空間上進行迭代，這樣空間可降至二維，
Floyd-Warshall演算法的描述如下：
for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
if (Di,k + Dk,j < Di,j) then
Di,j ← Di,k + Dk,j;
其中Di,j表示由點i到點j的代價，當Di,j為 ∞ 表示兩點之間沒有任何連接，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/274807.html
標籤：其他
上一篇：STM8采用按鍵的外部中斷實驗