tutorial - computer algorithm




如何培養算法直覺? (4)

當遇到軟件問題時,我通常會立即看到解決方案。 當然,我看到的東西通常有些偏離,我總是需要坐下來進行設計(當然,我通常沒有足夠的設計),但是我立刻就有了一定的直覺

我的問題是,當涉及到高級算法時,我沒有得到同樣的直覺。 我覺得更多的任務是建立另一個Facebook,然後建立另一個Google搜索或音樂Genom項目 。 這可能是因為我一直在構建軟件已經有相當長的一段時間了,但我對構建算法的經驗不多。

我希望社區關於閱讀內容的建議,以及在編寫算法時要做些什麼項目。

(這個問題與算法構成無關,好吧,幾乎沒有)


問題領域

首先你必須了解問題領域。 對錯誤問題的優雅解決方案並不好,在大多數情況下,對於正確問題的解決方案也不是很好。 換句話說,解決方案的質量往往是相對的。 一個簡單的調度問題有一個確定性的解決方案,需要十分鐘的時間才能運行,如果每週計劃一次,則計劃可能會很好,但如果計劃每天改變幾次,那麼可能需要幾秒鐘收斂的遺傳算法解決方案。

分解和映射

其次,將問題分解為與解決方案元素相對應的子問題和已知/未知元素。 有時候這是顯而易見的,例如,要計算您需要的小部件,以便識別小部件,增加計數器和存儲計數的方法。 有時候並不那麼明顯。 有時你必須同時分解問題,領域和可能的解決方案,並嘗試使用它們之間的幾種不同映射來找到導致正確結果的方法[這是一般方法]。

模型

至少在你的頭上建模解決方案,然後通過它來查看它是否正常工作。 根據需要進行調整(請參閱上面的分解和映射)。

組合物/接口

很多時候,您可以找到問題的元素以及解決方案的相互映射的元素,並生成部分有用的結果。 這種組合和界面結構提供了解決方案的核心,並且還用於減少剩餘問題的範圍。 那麼你只需循環回到最上面的小問題,並再次通過它。

經驗

當然,經驗是最好的老師,但閱讀不同類型的問題和解決方案也是有幫助的。 研究一些眾所周知的算法及其應用同樣非常有用,例如DijkstraBresenhamUnification ,當然還有圖論


Steve Yegge在他的一篇咆哮中提到了“算法設計手冊” 。 我自己並沒有看到,但聽起來這只是他描述中的票。

我對這種採訪準備工作的最愛是Steven Skiena的算法設計手冊。 它比其他任何書都更能幫助我理解圖表問題是多麼令人驚訝的普遍(和重要)問題 - 它們應該成為每個正在運行的程序員工具箱的一部分。 本書還介紹了基本的數據結構和排序算法,這是一個不錯的獎勵。 但是金礦是這本書的後半部分,它是一本關於無數有用的問題和解決它們的各種方法的1頁的百科全書,沒有太多的細節。 幾乎每一頁都有一張簡單的照片,使其易於記憶。 這是學習如何識別數百種問題類型的好方法。


我不確定直覺可以培養,但我想我知道你在問什麼。 您解決的問題越多,您可以為將來的問題提供更多的信息和經驗。 所以,我只是說練習。 練習編程真實世界的應用程序,並遇到很多問題。 有時候,解決謎題也是非常有教育意義的。


當我看著一個複雜的問題時,我試圖尋找物理類比。





algorithm