[發案] 最短路徑論文實驗演算法實作
凡是「*[30m」開始的行，都請使用 Ctrl + y 刪除。
如果對於發案文章格式有不清楚的地方，請參考置底文章：[發案] 發案範例
發案人：林映君
聯絡方式1：lin915@purdue.edu
聯絡方式2：
所在地區 ：中研院資訊所
有效時間：9/22
專案說明：
這個論文主要是在探討有限制的最短路徑(constrained shortest path)相關的演算法,而
這些演算法主要的概念與流程跟著名的Dijkstra algorithm大致上相似,另外加一些
Dynamic Programming的概念在演算法的實作過程中,這個專案主要包含三大部分: (1)最
短路徑演算法實作, (2)最短路資料儲存結構實作, (3)比較方法輸入輸出格式處理。
(1) 最短路徑演算法實作
這個部分會有兩個演算法需要實作,大致上資料結構已經處理完成(python classes),部分
小function也都有現成的code可以使用,只需要按照既定的資料結構(或者自己想設計更好
的資料結構),然後依照演算法的pseudocode完成實作即可。
(2) 最短路徑資料結構儲存
配合之前寫好的演算法,為了加速演算法的執行時間,我們另外設計了新的儲存結構,基本
上此結構(indexing structure)儲存了一些預先已知的資訊，使得線上計算最短路徑的時
候可以快速透過此結構得到我們想要的答案，這部分的實作也會有pseudocode可以參考,
一樣依據pseudocode實作即可。
(3) 比較方法輸入輸出格式處理
完成實驗會需要和幾個比較方法進行效能上的比較，因此需要修改幾個比較方法以達成我
們的目標，這部分皆有source code(C++)，我們只需要將我們的輸入各式改成別人的輸入
格式，再將別人的輸出格式，經過一些額外的計算，成為我們自己的輸出結果。
預算：12000 - 20000 (此預算為參考價格,有討論空間)
接案者要求：
1. 熟悉C++ 和 python
2. 熟悉最短路徑演算法(Dijkstra)
3. 熟悉Dynamic Programming
4. 有學生身分尤佳
附註：
有意者請將CV或者說明程式方面相關經驗寄信至 lin915@purdue.edu
謝謝大家
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 128.10.15.120
※ 文章網址: https://www.ptt.cc/bbs/CodeJob/M.1505756800.A.88B.html
→
09/19 22:41, , 1F
09/19 22:41, 1F
→
09/22 21:52, , 2F
09/22 21:52, 2F