问题标签 [graph-algorithm]

正如标题所说，我正在尝试实现一种算法，找出给定图中所有节点对之间的距离。但还有更多：（可能对您有帮助的事情）

• 该图未加权。这意味着所有边缘都可以被认为具有权重 1。
• |E| <= 4*|V|
• 该图非常大（最多〜144深度）
• 图是有向的
• 可能有循环
• 我正在用python编写我的代码（如果你引用算法，代码也会很好:)）

我知道所有对的 Johnson 算法、Floyd-Warshal和Dijkstra。但是当图有权重时，这些算法很好。

我想知道是否有更好的算法适合我的情况，因为这些算法适用于加权图。

谢谢！

首先，对于那些不知道的人 - 随时算法是一种算法，它可以输入它可以运行的时间量，它应该在那个时候给出最好的解决方案。

加权 A* 与 A* 相同，但 f 函数有一个差异：

（其中 g 是到 node 的路径成本，h 是直到达到目标的路径结束的启发式）

我的任何时候算法运行加权 A*，权重从 1 到 0.5，直到达到时间限制。

我的问题是，在大多数情况下，它需要很长时间才能找到解决方案，如果给定 10 秒之类的时间，它通常不会找到解决方案，而其他算法（如任何时间梁）在 0.0001 秒内找到一个解决方案。

有什么想法该怎么做？

我目前正在遵循 Steve Yegge 关于准备技术编程面试的建议： http: //steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

在他关于图表的部分中，他说：

在内存中表示图有三种基本方法（对象和指针、矩阵和邻接表），您应该熟悉每种表示形式及其优缺点。

CLRS 中描述了矩阵和邻接表表示的优缺点，但我无法找到将这些与对象表示进行比较的资源。

只是通过思考，我可以自己推断出一些，但我想确保我没有错过一些重要的事情。如果有人可以全面地描述这一点，或者向我指出这样做的资源，我将不胜感激。

它没有给我正确的答案。它返回一个有效的路径，是的。但是，它返回的路径并不是最短路径。问题在于粗线，如果它的总室外距离大于约束 maxDistOutdoors，我跳过路径，但我不知道如何更改它。当我删除那条粗线时，我得到了正确的最小路径，但是如果我需要在那里进行这样的检查，因为我想找到总室外距离小于 maxDistOutdoors 的最小路径。

我已经尝试过打印语句，我即将放弃。我只是不明白为什么它现在不正确。

我需要在opengl中变形网格/网格（仅在2d z中保持不变）

通过变形，我的意思是用户将使用鼠标或触摸并拖动特定的顶点，然后休息

这是一个链接（http://www.gamasutra.com/view/feature/3432/2d_surface_deformation.php），它准确地解释了我需要的东西，但我自己实现起来太难了，谁能给我指点资源或建议一种更简单的方法（通过使用一些图形库或其他东西）会很棒

Let's assume food delivery for multiple restaurants (say 20). There are (say 10) drivers available. Further, let's say we get 100 orders over a 4 hour period to deliver food from these restaurants to homes.

So drivers have to be coordinated to pickup food at a location and deliver to customers at home.

Primary goal is to minimize time to delivery, i.e. time between order and arrival at homes. The secondary goal is to maximize driver capacity (i.e., least amount of time to deliver all orders).

Bear in mind that the orders come in over a four hour period, so let's say evenly, i.e. one very 3 minutes. Also, let's assume the orders are randomly to the 20 restaurants.

Assume that I can calculate time to travel from any location to a destination to the second.

I know the location of all drivers in realtime. I also know their statuses, i.e. are they currently on their way to pick up an order (to take to a known destination), have they already picked up an order and are enroute to a known destination.

Constraints are: 1) Must pick up an order after a given time (i.e. meal preparation time for restaurant) 2) Must deliver order in under 45 mins (otherwise alert thrown) 3) Must pad time with "x" minutes to accommodate for time spent walking to store to pickup order, etc. 4) Must pad time with "y" minutes to accommodate for time spent delivering order to customer and collecting payment. 5) Drivers have only a given set of payment methods (e.g. Cash, Visa, Amex, MasterCard). We must match customer request (cash, visa, etc) with driver capability (cash, visa, amex, etc).

So for example, if I get two orders with close by destination and close by pickup locations, even if there is another "Free" driver (not doing anything), it would be more efficient to use the same driver to pickup both orders and deliver both orders.

You can assume there will be delivery zones enforced for each restaurant, meaning, most people ordering from them will most likely be close to them. Therefore, this algorithm should manage to segment drivers automatically into city zones, and favor drivers within the zone already.

给定一系列操作：

a*b*a*b*a*a*b*a*b

有没有办法获得最佳细分以启用子字符串的重用。

制造

a*b*a*b*a*a*b*a*b => c*a*c，其中 c = a*b*a*b

然后看到

a*b*a*b => d*d，其中 d = a*b

总而言之，将 8 个初始操作减少到此处描述的 4 个？

(c = (d = a*b)*d)*a*c

目标当然是最小化操作次数

我正在考虑一种后缀树。

我对线性时间启发式或解决方案特别感兴趣。'*' 操作实际上是矩阵乘法。

什么是枚举父图的所有子图的有效算法。在我的特定情况下，父图是一个分子图，因此它将被连接并且通常包含少于 100 个顶点。

编辑：我只对连接的子图感兴趣。

这个问题对于检测有向图中的循环有很好的答案。不幸的是，制作它的 Map Reduce 版本似乎并不容易。

具体来说，我对用于从有向图中删除循环的 Map Reduce 算法感兴趣。

我已经使用广度优先搜索 (BFS) 算法进行了评估，但我看到的一个问题是两个不同的边缘可能会同时被移除以切断一个循环。这种情况的影响是可以删除太多的边缘。重要的是要删除循环，同时尽量减少删除的边数。

有证据的解决方案是首选！

谢谢。

我在 python 2.6 中有一个监控应用程序，它计算队列中的条目数（queue_len）。我想创建一个简单的函数，可以使用这些 queue_len 随时间变化的速率值并从中提取趋势。

目标是根据 +ive 或 -ive 随着时间的趋势而不是触发器来启动或关闭队列处理节点。

金融领域的 MACD 看起来是我需要的，还是需要的？在这里寻求任何帮助。