什么是图形可以比替代品更好解决的问题的好例子？ [英] What are good examples of problems that graphs can solve better than the alternative?
问题描述
阅读Stevey Yegge的获得该职位后Google 的文章，我发现这个小小的引文很有趣：
每当有人给你一个问题，想想图表。它们是代表任何种类的关系的最根本和最灵活的方式，所以它是一个有效的设计问题涉及到一个50-50的镜头。绝对确定你不能想到在使用其他解决方案类型之前使用图形来解决它的方法。这个提示很重要！
什么是图形数据结构/算法最好地表示和/或解决的问题的一些例子？ / p>
我可以想到一个例子：导航单元（ala Garmin，TomTom），从当前位置向另一个地点提供路线，利用图形和高级路径算法。 p>
还有其他一些？
计算机网络： / strong>图形模型直观地模拟计算机网络和互联网。通常情况下，节点将表示终端系统或路由器，而边缘表示这些系统之间的连接。
数据结构使用任何数据结构将数据链接在一起的指针正在利用某种图形。这包括所有时间使用的树结构和链接列表。
路径和地图：尝试从某个位置找到最短或最长的路径到目的地使用图表。这可以包括像在Google地图中的应用程序中看到的路径，或计算AI角色进行视频游戏的路径，以及许多其他类似问题。
约束满意度： AI中的常见问题是找到满足约束列表的一些目标。例如，要使大学设定课程安排，需要确保某些课程不会发生冲突，教授不会同时教授两门课程，而是在某些时间段内发生演讲，等等。这样的约束满足问题通常使用图形进行建模和解决。
分子：图形可用于模拟原子和分子以研究其相互作用和结构等。
After reading Stevey Yegge's Get That Job At Google article, I found this little quote interesting:
Whenever someone gives you a problem, think graphs. They are the most fundamental and flexible way of representing any kind of a relationship, so it's about a 50–50 shot that any interesting design problem has a graph involved in it. Make absolutely sure you can't think of a way to solve it using graphs before moving on to other solution types. This tip is important!
What are some examples of problems that are best represented and/or solved by graph data structures/algorithms?
One example I can think of: navigation units (ala Garmin, TomTom), that supply road directions from your current location to another, utilize graphs and advanced pathing algorithms.
What are some others?
Computer Networks: Graphs model intuitively model computer networks and the Internet. Often nodes will represent end-systems or routers, while edges represent connections between these systems.
Data Structures: Any data structure that makes use of pointers to link data together is making use of a graph of some kind. This includes tree structures and linked lists which are used all the time.
Pathing and Maps: Trying to find shortest or longest paths from some location to a destination makes use of graphs. This can include pathing like you see in an application like Google maps, or calculating paths for AI characters to take in a video game, and many other similar problems.
Constraint Satisfaction: A common problem in AI is to find some goal that satisfies a list of constraints. For example, for a University to set it's course schedules, it needs to make sure that certain courses don't conflict, that a professor isn't teaching two courses at the same time, that the lectures occur during certain timeslots, and so on. Constraint satisfaction problems like this are often modeled and solved using graphs.
Molecules: Graphs can be used to model atoms and molecules for studying their interaction and structure among other things.
这篇关于什么是图形可以比替代品更好解决的问题的好例子？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
