什么是图表可以解决比替代问题更好的问题的好例子?

阅读Stevey Yegge的“ 获得工作”在Google的文章中,我发现这个有趣的小引语:

每当有人给你一个问题,想想图。 他们是代表任何一种关系的最基本和最灵活的方式,所以任何一个有趣的devise问题都会涉及一个图表。 请确保在转向其他解决schemetypes之前,无法想象使用图解解决此问题的方法。 这个提示很重要!

graphics数据结构/algorithm最能代表和/或解决哪些问题的例子是什么?

我可以想到的一个例子是:导航单元(ala Garmin,TomTom),提供从当前位置到另一个位置的路线方向,利用graphics和高级pathalgorithm。

还有其他什么?

计算机networking:graphics模型直观地模拟计算机networking和互联网。 节点通常代表terminal系统或路由器,而边代表这些系统之间的连接。

数据结构:利用指针将数据链接在一起的任何数据结构都是利用某种graphics。 这包括始终使用的树结构和链接列表。

Pathing和Maps:试图从某个位置到目的地find最短或最长的path,并使用graphics。 这可以包括像在Google地图这样的应用程序中看到的path,或计算AIangular色在video游戏中的path,以及许多其他类似的问题。

约束满意度: AI中的一个常见问题是find满足一系列约束条件的目标。 例如,大学要设定课程时间表,需要确保某些课程不冲突,教授不是同时教两门课程,讲课是在某些时间段进行的,等等。 像这样的约束满足问题通常使用图来模拟和解决。

分子:图表可以用来模拟primefaces和分子,研究它们之间的相互作用和结构。

我对图论非常感兴趣,并且使用它解决了许多不同的问题。 你可以用图来解决很多Path相关的问题,匹配问题,结构问题。

  • path问题有很多应用。

    这是在一个职业杯的面试问题。 假设你想find一个子数组的最长和。 例如, [1, 2, 3, -1]的总和最长为6.build模为有向非循环图DAG ),添加一个虚拟源,虚拟目标。 将每个节点连接到一个与数字相对应的边。 现在使用DAG中的最长pathalgorithm来解决这个问题。

    同样,金融世界中的套利问题甚至是find最长的重叠结构的几何问题也是类似的path问题。

  • 一些明显的问题networking问题 (你的networking可能有电脑人员,组织结构图等)。
    你可以收集许多结构信息

    • 该点将graphics分成两部分
    • 连接它们的最好方法是什么?
    • 什么是最好的方式来到另一个地方
    • 有没有办法从另一个地方到达一个地方等
  • 我用图解解决了很多与项目pipe理有关的问题。 一系列的事件可以被描绘成一个有向图 (如果你没有周期,那么它就更好)。 所以,现在你可以

    • 根据优先级对事件进行sorting
    • 你可以find最关键的事件(那就是免费的很多其他项目)
    • 你可以find解决整个项目所需的时间(path问题)等
  • 很多匹配问题可以通过图来解决。 例如,如果您需要将处理器与工作负载匹配或将工作人员与其工作匹配。 在我的期末考试中,我不得不把人们和餐馆里的餐桌相匹配。 它遵循相同的原则(双向匹配 – >networkingstreamalgorithm)。 它简单而强大。

  • 一个特殊的graphics, ,在计算机科学世界有很多应用。 例如,在编程语言的语法中,或在数据库索引结构中。

  • 最近,我还在编译器优化问题中使用了图表。 我正在使用摩根的书,这是教我迷人的技术。

这份名单确实在继续。 图是关系的一个美好的math抽象。 如果你能正确地build模,你真的可以创造奇迹。 而且由于图论发现了如此多的应用,所以在这个领域有许多积极的研究。 而且由于大量的研究,我们看到更多的应用正在加速研究。

如果你想开始使用图论,可以买一本好的初学离散math书( Rosen在我脑海中),你可以从FouldEven这样的作家那里买书。 CLRS也有很好的graphicsalgorithm。

您的源代码是树状结构,树是一种graphics。 每当你听到人们在谈论AST(抽象语法树)时,他们正在谈论一种graphics。

指针形成graphics结构。 任何指针都在做某种graphics操作。

networking是一个巨大的有向图。 谷歌关键的洞察力,导致他们在search中占主导地位的是,networking的graphics结构比页面的文本内容具有可比性或更大的重要性。

状态机是图。 状态机用于networking协议,正则expression式,游戏等各个领域。

想想你做的不涉及某种graphics结构的东西是相当困难的。

大多数人都很熟悉的例子:构build系统。 Make是一个典型的例子,但是几乎任何一个好的构build系统都依赖于一个有向无环图。 其基本思想是,方向模拟源和目标之间的依赖关系,并且应该按照一定的顺序“走”图来正确构build事物 – >这是拓扑sorting的一个例子。

另一个例子是信源控制系统:再次基于一个DAG。 它用于合并,例如,find共同的父母。

那么编译器使用的许多程序优化algorithm都是基于graphics的(例如,找出调用图,stream量控制,大量的静态分析)。

许多优化问题都是基于graphics的。 由于许多问题都可以通过graphics着色和类似的问题来减less,所以许多其他的问题也是基于graphics的。

我不确定我是否同意图表是expression每一个关系的最好方式,我当然试图避免这些“弄明白,让我们find一把锤子”的方法。 图表通常具有较差的内存表示,而且在使用matrix,位集和其他东西实现时,许多algorithm实际上更有效(实际上)。

OCR。 在一个angular度扫描文本的页面,在图像中有一些噪声,在这里你必须find文本行之间的空间。 一种方法是制作像素图,找出从页面一侧到另一侧的最短path,其中亮度差异是像素之间的距离。

这个例子来自algorithmdevise手册 ,其中有许多其他现实世界的graphics问题的例子。

一个stream行的例子是垃圾收集。

收集器以一组引用开始,然后遍历它们引用的所有对象,然后遍历所有引用的对象等等。 它find的所有东西都被添加到可达对象的graphics中。 所有其他对象无法访问和收集。

了解两个分子是否可以合在一起。 当开发药物时,人们往往对药物分子是否能够适应体内较大的分子感兴趣。 确定这是否可能的问题是分子不是静态的。 分子的不同部分可以围绕它们的化学结合物旋转,使得分子可以变成相当多的不同形状。

每个形状可以说是代表一个由形状组成的空间中的一个点。 解决这个问题涉及通过这个空间find一条path。 你可以通过创build一个空间的路线图,这本质上是一个graphics组成的法律形状,并说形状可以变成一个形状。 通过使用这个路线图的A *图searchalgorithm,您可以find一个解决scheme。

好吧,这可能是不是很容易理解或清楚。 但是我的观点是图表出现了各种各样的问题。

恕我直言,我们在正常应用中使用的大多数域模型都是在某些方面的graphics。 已经看过UML图的人可以注意到,有了一个有向标记的图,你可以很容易地将它们转换成一个持久化模型。 Neo4j有一些例子

干杯

/彼得

图表非常适合pipe理依赖关系。

我最近开始使用Castle Windsor容器,在检查内核之后,我find了一个GraphNodes属性。 温莎城堡使用图来表示对象之间的依赖关系 ,以便注入将正确工作。 看看这篇文章 。

我也使用简单的图论来开发一个插件框架,每个图节点代表一个插件,一旦定义了依赖关系,我可以遍历该图创build一个插件加载顺序。

我正在计划改变algorithm来实现Dijkstra的algorithm,以便每个插件都使用特定的版本进行加权,因此一个简单的更改只会加载最新版本的插件。

我和我早已经发现了。 我喜欢这句话“每当有人给你一个问题,想想图表。” 我绝对认为这是事实。

你可以看一下Neo4j wiki中的一些例子,

http://wiki.neo4j.org/content/Domain_Modeling_Gallery

和Neo4j被使用的项目(已知的)

http://wiki.neo4j.org/content/Neo4j_In_The_Wild

否则,推荐algorithm很适合Graphs,请参阅PageRank和其他内容

http://wiki.github.com/tinkerpop/gremlin/pagerank

以下是基于图论:

  • 二叉树和其他树木,如红黑树,斜张树等
  • 链接列表
  • 任何build模为状态机(GUI,networking堆栈,CPU等)
  • 决策树(用于AI和其他应用程序)
  • 复杂的类inheritance

graphics不是数据结构。 他们是关系的math表示。 是的,你可以用图表思考和理论化问题,关于它的理论有很多。 但是当你需要实现一个algorithm时,你正在select数据结构来最好地代表问题,而不是graphics。 有很多数据结构代表一般的graphics,甚至更多的特殊的graphics。

在你的问题中,你混合了这两个东西。 同样的理论解决scheme可能是graphics方面,但实际的解决scheme可能使用不同的数据结构来表示graphics。

人与人之间的社交联系是一个有趣的图表例子 我试图使用传统的RDMS在数据库级build立这些连接的模型,但是发现它太难了。 我最终select了一个graphics数据库,这是一个不错的select,因为它可以很容易地跟踪人(节点)之间的连接(边缘)。

任何可以在关系数据库中作为键build模的东西本质上都是图中的节点

也许这会帮助你考虑一些例子,因为大多数事情都可以在RDBMS中很容易地build模。

在代码中进行性能分析和/或基准testingalgorithm和实现。

分析数据库理论中的事务可序列性。

您可以在任何可以将问题域对象定义为节点的位置使用graphics,并将解决scheme用作节点间的控制和/或数据stream。

考虑到树实际上是连通的 – 非循环图的事实,有更多的领域可以使用图论。

基本上几乎所有常见的数据结构,如树,列表,队列等,都可以被认为是图的types,一些具有不同types的约束。

根据我的经验,我在networkingstream量问题中大量使用了图表,在电信networking路由优化,工作负载分配匹配供应链优化公共交通规划等许多领域都有使用。

另一个有趣的地方就是前面提到的答案是社交networkingbuild模

还有更多,如集成电路优化等。