如何培养算法直觉？

Question

当遇到软件问题时,我通常会立即看到解决方案.当然,我看到的通常有些偏离,我总是需要坐下来设计(诚然,我通常设计不够),但我立刻得到了一定的直觉.

我的问题是,当涉及到高级算法时,我没有得到同样的直觉.我更愿意建立另一个Facebook,然后建立另一个谷歌搜索,或音乐Genom项目.这可能是因为我一直在构建软件很长一段时间,但我对编写算法的经验不多.

我希望社区的建议是阅读什么以及为了更好地编写算法而采取哪些项目.

(这个问题与算法组合无关.好吧,几乎没有)

Answer 1

+1对于说经验的人是最好的老师.

有几个在线门户网站有很多编程问题,您可以提交自己的解决方案,并获得自动通过/失败指示.

1. http://www.spoj.pl/
2. http://uva.onlinejudge.org/
3. http://www.topcoder.com/tc
4. http://code.google.com/codejam/contests.html
5. http://projecteuler.net/
6. https://codeforces.com
7. https://leetcode.com

该USACO训练场地就是培训课程,所有的美国奥林匹克计算参与者经历.它一步一步地引入越来越复杂的算法.

Answer 2

您可能会发现在物理上执行算法很有帮助.例如,当您正在研究排序算法时,练习用一副牌进行每个算法.这将激活大脑的不同部分,而不仅仅是阅读或编程.

Answer 3

Steve Yegge 在他的一个咆哮中提到了"算法设计手册".我自己也没见过,但听起来这只是他描述的票.

我最喜欢这种面试准备的是Steven Skiena的The Algorithm Design Manual.它比任何其他书籍都更能帮助我理解图形问题是多么令人惊讶的普遍(和重要) - 它们应该成为每个工作程序员工具包的一部分.本书还介绍了基本的数据结构和排序算法,这是一个很好的奖励.但是金矿是这本书的后半部分,这是一本关于数以万计的有用问题和各种解决方法的1页的百科全书,没有太多细节.几乎每个1-pager都有一个简单的图片,使其易于记忆.这是学习如何识别数百种问题类型的好方法.

Answer 4

问题域

首先,您必须了解问题域.对于错误问题的优雅解决方案是不好的,在大多数情况下也不是解决正确问题的低效解决方案.换句话说,解决方案质量通常是相对的.如果每周计划一次计划,那么具有运行十分钟的确定性解决方案的简单调度问题可能没问题,但如果计划每天改变几次,则可能需要在几秒钟内收敛的遗传算法解决方案.

分解和映射

其次,将问题分解为子问题以及与解决方案元素相对应的已知/未知元素.有时这很明显,例如,计算小部件需要一种识别小部件的方法,一个可递增的计数器,以及一种存储计数的方法.有时它并不那么明显.有时您必须同时分解问题,域和可能的解决方案,并尝试在它们之间进行几种不同的映射,以找到导致正确结果的映射[这是一般方法].

模型

至少在头脑中对解决方案进行建模,然后浏览它以查看它是否正常工作.根据需要进行调整(参见上面的分解和映射).

组合物/接口

很多时候,您可以找到问题的元素和解决方案的元素,这些元素相互映射并产生有用的部分结果.该组合物和界面结构提供了解决方案的核心,并且还用于减少剩余问题的范围.那么你只需要一个较小的初始问题循环回到顶部,然后重复一遍.

经验

当然,经验是最好的老师,但阅读不同类型的问题和解决方案也会有所帮助.研究一些众所周知的算法及其应用同样非常有用,例如Dijkstra,Bresenham,Unification,当然还有图论.