使用 A 星寻找路径的启发式函数
我正在尝试为以下问题找到最佳解决方案 每个节点内表示的数字表示为(x,y). 一个节点的相邻节点总是有一个 y 值，即(当前节点 y 值 +1). 当我们从一个节点到其相邻节点时，x 值的变化成本为 1 如果 x 的值没有变化，则从节点到其相邻节点没有成本. 没有 2 个具有相同 y 值的节点被认为是相邻的. 最优方案是成本最低的方案，我正在考虑使用 A* 寻路算法来寻找最优方
..
graph-algorithm相关内容
AStar - 名称解释
我正在寻找为什么 AStar/A* 算法被称为 AStar 的解释.所有相似的(最短路径问题)算法通常都以其开发者的名字命名，那么 AStar 代表什么? 解决方案 有称为 A1 和 A2 的算法.后来证明A2是最优的，实际上也是最好的算法，所以他给它取了个名字A*，象征性地包含了所有可能的版本号. 来源: 1964 年，Nils Nilsson 发明了一种基于启发式的方法来提
..
适用于非常大图的 A* 算法，对缓存快捷方式有什么想法吗?
我正在 OpenStreetMap 地图上编写快递/物流模拟，并意识到如下图所示的基本 A* 算法对于大型地图(如大伦敦)来说不够快. 绿色节点对应的是放在开放集/优先级队列中的节点，由于数量庞大(整个地图大约有 1-2 百万个)，找到图中的路线需要 5 秒左右.不幸的是，每条路线 100 毫秒大约是我的绝对限制. 目前，节点既存储在邻接列表中，也存储在空间 100x100 二维数组中
..
如何使用 A 星算法找到前 100 条最短路径?
如何使用 A 星算法找到前 100 条最短路径? 解决方案 求第k条最短路径的问题是NP-Hard，因此对 A-Star 所做的任何修改都可以满足您的要求 - 输入的大小将呈指数级增长. 证明: (注意:我会在简单路径上显示) 假设你有一个多项式算法，它在多项式时间内运行并返回k的长度，最短路径让算法为A(G,k) 最大路径数为n!，通过对[1,n!]范围进行二分查找，找到
..
2D 航路点寻路:从 curLocation 到 targetLocation 的 WP 组合
请花点时间了解我的情况.如果有不明白的地方，请在评论中告诉我. 我有一个航点数组列表.这些航点没有任何顺序.航点具有以下属性: {int type, float z, float y, float x, float rotation} 这适用于 3 维世界，但由于我的寻路不应该关心高度(因此将世界视为 2 维世界)，因此忽略 y 值.轮换对于这个问题并不重要. 在这个二维世界中
..
如何光栅化旋转的矩形(在 2d 中由 setpixel)
我有一个旋转矩形的四个二维顶点 A B C D，我需要在 pixelbufer 中(有效地)光栅化/绘制它使用 setpixel(x,y,color) 怎么做? 我正在尝试使用类似的代码 //转换 a b c d do up down left right,//在 y-- 上计算一些 dx_left dx_right//等(在同一行中有 2 个 up_y 顶点时的特殊情况令人沮丧等)
..
2D 航路点寻路:从 curLocation 到 targetLocation 的 WP 组合
请花点时间了解我的情况.如果有不明白的地方，请在评论中告诉我. 我有一个航点数组列表.这些航点没有任何顺序.航点具有以下属性: {int type, float z, float y, float x, float rotation} 这适用于 3 维世界，但由于我的寻路不应该关心高度(因此将世界视为 2 维世界)，因此忽略 y 值.轮换对于这个问题并不重要. 在这个二维世界中
..
如何光栅化旋转的矩形(在 2d 中由 setpixel)
我有一个旋转矩形的四个二维顶点 A B C D，我需要在 pixelbufer 中(有效地)光栅化/绘制它使用 setpixel(x,y,color) 怎么做? 我正在尝试使用类似的代码 //转换 a b c d do up down left right,//在 y-- 上计算一些 dx_left dx_right//等(在同一行中有 2 个 up_y 顶点时的特殊情况令人沮丧等)
..
如何从非重叠位集形成最大数量的 1
给定由 M 位组成的 N 个位集，选择 K 个位集，以便在同一位置不会出现多个 1.最多可以形成多少个 1? 示例: N = 5, M = 6001100011010100100111001001010 答案将结合 011010 和 100100，其中答案是 5. 我期待多项式时间解决方案，尽管我不确定是否可行.问题取自 here 可能有更好的措辞. 解决方案 这是加权最大
..
Javascript 中的匹配算法
我正在为 JavaScript 或类似的东西寻找 Blossom 算法的实现. 我有一组对 A - B A - C B - D 并且我需要选择对，假设每个字母在输出中只能出现一次.在上面的场景中，正确的结果是 A - C B - D 因为 A、B、C 和 D 都在结果中.不正确的结果是 A - B 这会排除 C 和 D. 解决方案
..
是否有一种算法可以在无向图中找到分离源和汇的最小割
我有一个边加权无向图和 2 个节点(通常称为源和汇).我需要找到一组权重最小的边，将这 2 个节点分成 2 个弱分量. 我了解 Ford-Fulkerson 的最大流算法 和他的定理关于有向图上的最大流和最小割关系. 我还知道对无向图的 Ford-Fulkerson 最大流算法进行了修改，该算法将每个无向边替换为 2 个相反的有向边，并同时更新流向它们两个.但是有了这个修改，最大流最小
..
Kruskal 算法的时间复杂度?
我正在计算这样的 kruskal 算法的时间复杂度(请参阅附图中的算法) T(n) = O(1) + O(V) + O(E log E) + O(V log V)= O(E log E) + O(V log V)如 |E|>= |V|- 1T(n) = E log E + E log E= E 日志 E CLRS 算法: 这是正确的还是我做错了什么，请告诉. 解决方案 Krusk
..
找到连接的节点集群的算法
我正在处理 3d 数据，并提供了一个相互连接的顶点列表.数据格式如下: faces = [(0, 1, 2),(1, 3, 2),(3, 5, 6),(5, 7, 4),(10, 11, 12),(11, 12, 13),(12, 13, 14)] 数组中的每一项都由一个三元组组成，其中每个位置的数字表示相互连接的顶点的索引.我在图片中可视化了这个例子，以便更好地理解顶点是如何连接的.
..
计算网格中标记节点 k 距离内的节点
我正在尝试解决编码挑战，但是我的解决方案不是很高效，我正在寻找有关如何改进算法的建议. 拼图如下: 您将获得一个代表果园的单元格网格，每个单元格可以是一个空点 (0) 或一棵果树 (1).一位农民想知道果园内距离所有果树 k 距离内有多少空位. 使用出租车几何计算距离，例如: k = 1[1, 0][0, 0]答案是 2，因为只有右下角的位置与所有树木的距离 > k. 我的解
..
在新结构中快速创建结构列表
我正在尝试构建一些原始对象来存储图形: Vertex = Struct.new(:parent，:rank)图= Struct.new(:vertexes，:edges)边缘= Struct.new(:weight，:endpoints) 这里的想法是:endpoints (和:parent )是顶点，并且，自然地， Graph 存储顶点和边的列表.我试图进行设置，但遇到了麻烦: [4
..
找到“气泡"在图中
..
如何在Python中实现15难题的IDA *算法?
我正在尝试使用IDA *算法和Manhattan启发式算法来解决15-Puzzle问题.我已经在此Wikipedia页面(链接)中的伪代码中实现了该算法. > 到目前为止，这是我的代码: def IDA(初始状态，目标状态):initial_node =节点(initial_state)目标节点=节点(目标状态)阈值= manhattan_heuristic(initial_state，g
..
有向无环图的拓扑排序
有没有一种算法，给定一个未加权的有向无环图，它将所有节点分类到节点集列表中，这样 保留拓扑顺序(即，对于所有边 u-> v ， v 出现在比 u 靠下的集合中代码>)和 列表的长度最小. 这个问题有名字吗? 示例 下面的图形可能是 [1]，[2、3]，[4、5]，[6、7] 一种替代解决方案是 [1]，[2、3]，[4]，[5、6、7] 解决方案 考虑标
..
我的Dijkstra的算法实现未返回最短路径
我试图在JavaScript中实现Dijkstra的最短路径算法，并通过多个示例对其进行了测试. 我正在使用此图查看其行为: 如果我想找到从A到I的最短路径，结果应该是[A，D，C，F，G，H，I]，距离等于10. 但是我的实现将路径返回为[A，B，E，J，F，G，H，I]，距离为14. 这是我的JavaScript代码: const graph = {A:{B:3
..
查找科赫曲线的坐标
对不起，我的语言，因为英语是我的第二语言. 我正在尝试将直线转换为称为科赫曲线的分形.给出了直线的2个点，然后我需要创建Koch曲线，在该曲线中将线划分为3个线段，然后使第二个线段成为等边三角形.参见 http://www.tgmdev.be/curvevonkoch.php . 到目前为止，我们将直线转换为4个相等的线段，我需要找出科赫曲线的所有坐标. 当2点的y坐标相同时，我
..