问题标签 [graph-algorithm]

我想知道当我们知道每个点的坐标时，是否有人可以帮助我找到笛卡尔平面中二维物体的面积。例如：我想计算三角形的面积。A(12,34) B(45,89) C(25,35)

我想要一个通用算法来找到任何二维对象的区域。

谢谢你。

I have a huge directed graph with about a million nodes and more than ten million edges. The edges are not weighted. The graph is a small-world like graph. In fact I see that every node is (on average) connected to another node over three intermediate nodes.

Given this graph can you think of a fast algorithm that returns all paths (without cycles) between a start and a destination node, but only up to a given maximum number N of intermediate nodes (and in my case N most of the time will be between 0 and 3)?

我必须制作一个程序来说明图形是否可着色 - 基本上我必须检查色度指数是 d 还是 d+1，其中 d 是所有顶点的最大度数（维辛定理）。我知道这个问题是NP完全的，基本上它必须被暴力破解。我有一个想法，但不知道它是否正确 -

1) 找到 deg(v) = d 的顶点，并用 d 种不同的颜色为所有与 v 相关的边着色。

2) 对于所有与与 v 相邻的顶点入射的边，应用 d 组颜色中的一些颜色

3）重复2）“发现”的边缘

如果所有边都用 d 种颜色着色，则色度指数为 d，并且我有图 G 的一种着色。

如果某些边缘不能用 d 组颜色中的颜色着色，则用 d+1-st 颜色为他上色，并用 d+1 组颜色中的颜色为剩余边缘上色 - 这是问题 - 使用此方案，如果我宣布色度指数为 d+1，是否有可能与其他一些着色色度指数为 d？（对于将要着色的每个边缘，我选择一种可以使用的颜色）..

另外，哪种图形表示最适合这个问题？在输入文件中，图写在邻接矩阵中。我知道它可以通过递归来解决，但我不知道如何。我被一些过于复杂的想法所困扰：S（一些提示或伪代码将不胜感激）。

编辑：

刚想到我，我认为应该没问题（纯蛮力）。我还没有尝试实现这一点。如果您发现有问题，请发表评论。再说一遍-算法应该检查图形是否可以用 d 或 d+1 种颜色着色，其中 d 是给定简单图形中所有顶点的最大度数，并找到一种着色...

首先，请原谅我英语不好。

我遇到了以下问题：我必须以固定顺序（例如 A -> D -> F）找到 2 个以上点之间的最短路径。我熟悉 Dijkstra 的算法。但是那个只计算两点之间的最短路径。我也听说过 TSP，但这似乎也不合适。因为没有修复顺序。我已经在网上搜索了我的问题，但也许这不是一个很受欢迎的问题，或者我使用了错误的关键词。

尽管如此，还是要有一个解决方案，因为有很多路线规划器，都成功地提供了这个功能。

所以拜托，任何人都可以通过命名一个算法来帮助我解决我的问题，或者给我一些建议。

非常感谢您的帮助！你真诚的，安杰洛

//edit 呵呵，很尴尬。看来我想了很久，所以我没有描述真正的问题。就是这样：有一些票，只能从头使用。

T1：A -> B（费用 50） T2：B -> C（费用 50） T3：A -> B -> C（费用 80） 给定路线是 A -> B -> C

现在你看，如果我们将给定的路线视为两个独立的问题，我们的总成本将变为 100，但显然 Ticket T3 是更好的解决方案。

是否有邻接矩阵优于邻接列表的算法？反过来呢？

对不起，文字墙，它尽可能简洁！

我有一个非常大的有向图 G 和 G 内的顶点子集 S p 和 G 中的一个顶点 q，即在诱导子图中这两个顶点之间存在一条边。这是关键；它比通常的诱导子图问题更复杂（我认为）。

我能想到的解决问题的最基本方法如下（我意识到它可能不是最有效的，如果您有其他不太复杂的建议，请告诉我）： 对于 S 中的每一对顶点，在 G 中测试它们之间是否存在路径。如果存在这样的路径，则在诱导子图中插入 p 和 q 之间的边。就我的目的而言，n^2 次还不错。

所以，我想我有两个问题：1）确定两个顶点之间是否存在路径的最快方法是什么？我不需要知道路径，只需要知道它是否存在。此外，如果我可以对整个图形进行一些预处理以加快计算速度，那可能是什么，因为我必须在每对顶点之间执行此计算？

2）有没有比我建议的更快的方法来找到我描述的诱导子图的类型？

非常感谢你的帮忙！

我有一个图论（也与组合学有关）问题，如下所示，我想知道设计算法来解决它的最佳方法是什么。

给定 6 个节点的 4 个不同的图（不同，我的意思是不同的结构，例如 STAR、LINE、COMPLETE 等）和 24 个唯一对象，设计一个算法将这些对象分配给这 4 个图4 次，使得在 4 个分配上的图上重复的邻居被最小化。例如，如果对象 A 和 B 在一个分配中的 4 个图中的 1 个上是邻居，那么在最好的情况下，A 和 B在其他 3 个分配中不会再次成为邻居。

显然，这种最小化的程度取决于给定的特定图结构。但是我对这里的通用解决方案更感兴趣，因此给定任何 4 个图形结构，算法的结果可以保证这种最小化。

欢迎任何解决此问题的建议/想法，并且一些伪代码可能足以说明设计。谢谢你。

我有一组值，每个值都有一个可能的组。该值可以重复但在不同的组中。

什么是获得最少组数的最佳算法

一个样本集：（12，b组）（38，a组）（12，a组）

预期结果：（38，a 组）（12，a 组）

（仅使用一组）

-- 编辑：我需要一个算法来从上面的示例中找到最小数量的组。如果我的算法不好，它将选择（12，b组）（38，a组）这是相同值的2组，而不是使用一个，不是我想要的

所以今晚我在想一个图距离算法，在我开车的时候想出了这个：

起初，我为自己感到相当自豪，因为它看起来如此优雅。但后来我意识到它行不通 - corecursion 可能会陷入循环。

我不得不对其进行编码以说服自己：

但现在我想我已经想通了。

在处理核心递归数据时，是否有一份我可以阅读的常见错误和反模式列表，以便我可以训练我的大脑进行核心递归思考？经验已经很好地训练了我思考非核心数据的能力，但如果可以的话，我想从其他人的错误中学习。

我必须为管道行业的路由目的创建一个算法。就像我们有 4 条可用管道一样，在它们之间可以注入石油，也可以在任何站点取出。如果我们有 30000 个单位的容量并且我们必须运输 35000 个（托运人的提名），那么我们需要减少提名。但是如何减少它以及如何安排以便我们可以容纳最大量？

我试图通过使用旅行商问题（TSP）和其他 NP-Hard 问题来解决它，但没有成功。