问题标签 [graph-algorithm]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
math - 计算笛卡尔平面中物体的面积
我想知道当我们知道每个点的坐标时,是否有人可以帮助我找到笛卡尔平面中二维物体的面积。例如:我想计算三角形的面积。A(12,34) B(45,89) C(25,35)
我想要一个通用算法来找到任何二维对象的区域。
谢谢你。
algorithm - How to find all paths in a graph between two nodes up to a given number of intermediate nodes?
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)?
algorithm - 图论-色度指数
我必须制作一个程序来说明图形是否可着色 - 基本上我必须检查色度指数是 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 是给定简单图形中所有顶点的最大度数,并找到一种着色...
graph-theory - 最短的方式,超过 2 点,但修复订单
首先,请原谅我英语不好。
我遇到了以下问题:我必须以固定顺序(例如 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 是更好的解决方案。
data-structures - 与列表相比,哪些算法在邻接矩阵中表现更好?
是否有邻接矩阵优于邻接列表的算法?反过来呢?
algorithm - 诱导子图;两个节点之间存在路径
对不起,文字墙,它尽可能简洁!
我有一个非常大的有向图 G 和 G 内的顶点子集 S p 和 G 中的一个顶点 q,即在诱导子图中这两个顶点之间存在一条边。这是关键;它比通常的诱导子图问题更复杂(我认为)。
我能想到的解决问题的最基本方法如下(我意识到它可能不是最有效的,如果您有其他不太复杂的建议,请告诉我): 对于 S 中的每一对顶点,在 G 中测试它们之间是否存在路径。如果存在这样的路径,则在诱导子图中插入 p 和 q 之间的边。就我的目的而言,n^2 次还不错。
所以,我想我有两个问题:1)确定两个顶点之间是否存在路径的最快方法是什么?我不需要知道路径,只需要知道它是否存在。此外,如果我可以对整个图形进行一些预处理以加快计算速度,那可能是什么,因为我必须在每对顶点之间执行此计算?
2)有没有比我建议的更快的方法来找到我描述的诱导子图的类型?
非常感谢你的帮忙!
algorithm - 将节点分配给图形的算法设计
我有一个图论(也与组合学有关)问题,如下所示,我想知道设计算法来解决它的最佳方法是什么。
给定 6 个节点的 4 个不同的图(不同,我的意思是不同的结构,例如 STAR、LINE、COMPLETE 等)和 24 个唯一对象,设计一个算法将这些对象分配给这 4 个图4 次,使得在 4 个分配上的图上重复的邻居被最小化。例如,如果对象 A 和 B 在一个分配中的 4 个图中的 1 个上是邻居,那么在最好的情况下,A 和 B在其他 3 个分配中不会再次成为邻居。
显然,这种最小化的程度取决于给定的特定图结构。但是我对这里的通用解决方案更感兴趣,因此给定任何 4 个图形结构,算法的结果可以保证这种最小化。
欢迎任何解决此问题的建议/想法,并且一些伪代码可能足以说明设计。谢谢你。
algorithm - 最小分组算法
我有一组值,每个值都有一个可能的组。该值可以重复但在不同的组中。
什么是获得最少组数的最佳算法
一个样本集:(12,b组)(38,a组)(12,a组)
预期结果:(38,a 组)(12,a 组)
(仅使用一组)
-- 编辑:我需要一个算法来从上面的示例中找到最小数量的组。如果我的算法不好,它将选择(12,b组)(38,a组)这是相同值的2组,而不是使用一个,不是我想要的
haskell - Haskell:常见的 Corecursive 谬误
所以今晚我在想一个图距离算法,在我开车的时候想出了这个:
起初,我为自己感到相当自豪,因为它看起来如此优雅。但后来我意识到它行不通 - corecursion 可能会陷入循环。
我不得不对其进行编码以说服自己:
但现在我想我已经想通了。
在处理核心递归数据时,是否有一份我可以阅读的常见错误和反模式列表,以便我可以训练我的大脑进行核心递归思考?经验已经很好地训练了我思考非核心数据的能力,但如果可以的话,我想从其他人的错误中学习。
java - 管道的路由算法
我必须为管道行业的路由目的创建一个算法。就像我们有 4 条可用管道一样,在它们之间可以注入石油,也可以在任何站点取出。如果我们有 30000 个单位的容量并且我们必须运输 35000 个(托运人的提名),那么我们需要减少提名。但是如何减少它以及如何安排以便我们可以容纳最大量?
我试图通过使用旅行商问题(TSP)和其他 NP-Hard 问题来解决它,但没有成功。