在阅读了Stevey Yegge的" Get That Job At Google"文章之后,我发现这个小小的引用很有趣:
每当有人给你一个问题时,请考虑图表.它们是代表任何一种关系的最基本和最灵活的方式,因此任何有趣的设计问题都有一个图表涉及50-50左右.在转向其他解决方案类型之前,请确保您无法想出使用图表解决问题的方法.这个提示很重要!
有哪些问题可以通过图形数据结构/算法得到最好的表示和/或解决？
我能想到的一个例子是:导航单元(ala Garmin,TomTom),它提供从当前位置到另一个位置的道路方向,利用图形和高级路径算法.
还有什么其他的？
计算机网络:图形模型直观地模拟计算机网络和因特网.节点通常代表终端系统或路由器,而边缘代表这些系统之间的连接.
数据结构:任何利用指针将数据链接在一起的数据结构都是使用某种图形.这包括一直使用的树结构和链表.
路径和地图:尝试查找从某个位置到目的地的最短路径或最长路径,可以使用图形.这可以包括您在Google地图等应用程序中看到的路径,或计算视频游戏中AI角色的路径以及许多其他类似问题.
约束满足: AI中的一个常见问题是找到一些满足约束列表的目标.例如,对于大学设定课程安排,需要确保某些课程不会发生冲突,教授不会同时教授两门课程,讲座会在某些时段发生,等等.像这样的约束满足问题经常使用图形建模和解决.
分子:图形可用于模拟原子和分子,以研究它们之间的相互作用和结构.
我对图论非常感兴趣,并且我用它解决了很多不同类型的问题.您可以使用图解决很多Path相关问题,匹配问题,结构问题.
路径问题有很多应用.
这是职业杯的面试问题.假设您要查找子数组的最长总和.例如,[1, 2, 3, -1]具有最长的总和6.将其建模为有向非循环图(DAG),添加虚拟源,虚拟目标.使用具有与数字对应的权重的边连接每个节点.现在使用DAG中的最长路径算法来解决此问题.
同样,金融世界中的套利问题甚至是寻找最长重叠结构的几何问题也是类似的路径问题.
一些明显的问题是网络问题(您的网络可能有计算机人员,组织结构图等).
你可以搜集大量的结构信息像
哪一点将图形分成两部分
什么是连接它们的最佳方式
到达另一个地方的最佳方式是什么？
有没有办法从另一个地方到达一个地方,等等.
我用图表解决了很多与项目管理相关的问题.一系列事件可以被描绘成有向图(如果你没有周期,那就更好了).所以,现在你可以
根据事件的优先级对事件进行排序
你可以找到最重要的事件(这将免除许多其他项目)
你可以找到解决整个项目所需的持续时间(路径问题)等.
图表可以解决很多匹配问题.例如,如果您需要将处理器与工作负载匹配或将工作者与工作匹配.在我的期末考试中,我不得不将人们与餐馆的桌子相匹配.它遵循相同的原则(二分匹配 - >网络流算法).它简单而有力.
特殊图形,树,在计算机科学领域有许多应用.例如,在编程语言的语法中,或在数据库索引结构中.
最近,我还在编译器优化问题中使用了图形.我正在使用Morgan的书,它正在教我迷人的技巧.
这个清单真的一直在继续.图形是关系的一个美丽的数学抽象.如果你能正确建模,你真的可以创造奇迹.由于图论已经发现了如此多的应用,因此该领域有许多积极的研究.由于大量的研究,我们看到更多的应用正在推动研究.
如果你想开始使用图论,那就得到一本好的初学者离散数学书(罗森来到我的脑海里),你可以从像Fould或Even这样的作家那里购买书籍.CLRS也有很好的图算法.
您的源代码是树结构的,树是一种图形.每当你听到人们谈论AST(抽象语法树)时,他们都在谈论一种图形.
指针形成图形结构.任何走路指针的东西都在做某种图形处理.
网络是一个巨大的有向图.谷歌的关键洞察力导致他们在搜索中占主导地位,因为网络的图形结构与页面的文本内容具有相似或更大的重要性.
状态机是图表.状态机用于网络协议,正则表达式,游戏和各种其他领域.
很难想到你做的任何事情都不涉及某种图形结构.
大多数人都熟悉的例子:构建系统.Make是典型的例子,但几乎任何好的构建系统都依赖于Directed Acyclic Graph.基本思想是方向模拟源和目标之间的依赖关系,你应该按照一定的顺序"走"图形来正确构建 - >这是拓扑排序的一个例子.
另一个例子是源控制系统:再次基于DAG.它用于合并,例如,找到共同的父母.
好吧,编译器使用的许多程序优化算法都基于图形(例如,找出调用图,流控制,大量静态分析).
许多优化问题都基于图表.由于许多问题可以减少到图形着色和类似问题,因此许多其他问题也是基于图形的.
我不确定我是否同意图表是代表每个关系的最佳方式,我当然会尽量避免这些"得到钉子,让我们找到一把锤子"的方法.图表通常具有较差的内存表示,并且当使用矩阵,位集和其他内容实现时,许多算法实际上更有效(在实践中).
OCR.画出以一定角度扫描的文本页面,图像中有一些噪点,您必须在这里找到文本行之间的空格.一种方法是制作像素图,并找到从页面一侧到另一侧的最短路径,其中亮度差异是像素之间的距离.
这个例子来自算法设计手册,它有很多其他现实世界的图形问题例子.
京公网安备 11010802040832号 | 京ICP备19059560号-6 