-
2 votesanswersviews
计算给定路径成本下的最大利润
给出了根图 . 这里，节点是“家”，包含一些有 Value 的项目 . 给出入口节点，即图的根 . 还给出了从一个节点移动到另一个节点的成本，即Egde权重 . Question - 您必须收集最大的贵重物品，总成本不应超过给定的成本 . Contraint - 1.没有循环 . 2.我们也可以使用相邻矩阵 . （顶点总数最多为1000） . Example Edges given with ... -
1 votesanswersviews
如何在图中找到精确长度的路径
我想在无向图中找到固定长度的路径（在运行程序时给出） . 我正在使用我的图的邻接矩阵 .我尝试使用一些算法，如DFS或A *，但它们只返回最短路径 . 无法再次访问节点 . 因此，假设我的图表有9个节点，最短路径是从4个节点构建的 .我希望有一个额外的变量"tell"我想找到有7个节点的路径的算法（例如），它将返回包含在我预期路径中的节点{1,2,4,5,6,7， 8} .当然... -
19 votesanswersviews
计算两点之间的最短路线
过去几周我一直在使用 nodejs 和 websockets 进行多人HTML5游戏 . 我已经陷入了这个问题一段时间了 . 想象一下，我有一个用数组实现的tileheet map（如下所示） . 1 或 brown tiles - 路上有障碍，玩家无法通过它 . 0 或 green tiles - 允许玩家移动的自由路径 . 通过以下方式访问 Map 上的任何图块： array[x][y... -
2 votesanswersviews
在我的图形实现中查找边数并执行拓扑排序
我过去几天一直致力于图表实施 . 所有这一切对我来说都是新的，我被困在我实施的两个部分 . 我正在从输入文件中实现课程的图表 . 从文件中，我可以确定哪些课程是其他课程的先决条件 . 然后我创建了一个以图表为节点的图表，以及连接作为先决条件的边缘的边缘 . 我还想找到节点和边的总数，并在图上执行拓扑排序（我稍后将向边添加权重） . 这是我的实施 . Digraph.h class vertex{ ... -
0 votesanswersviews
图上的聚类（使用Boost图库）
在C项目中，我们正在尝试一个重要的Boost Graph流量相关，以便在两个节点之间的最短路径上启动Dijkstra的几个模拟 . 该图有18 000个顶点和40 000个边 . 加载图表大约需要200毫秒，而Dijkstra运行50毫秒 . 但时间开始成为一个问题，所以我们希望降低这些时间 . 我们正在寻找几种选择： 使用Dijkstra算法的启发式方法如： 双向Dijkstra A... -
1 votesanswersviews
从无向图中移除二度顶点（Skiena TADM 5-22）
从算法设计手册第2版，问题5-22： 设计线性时间算法，通过用边（u，w）替换边（u，v）和（v，w），从图中消除2阶的每个顶点v . 我们还试图通过用单个边缘替换它们来消除多个边缘副本 . 请注意，删除边的多个副本可能会创建一个2级的新顶点，必须将其删除，并且删除2级顶点可能会创建多个边，这些边也必须被删除 . 因为问题出现在关于无向图的部分中，所以假设我们的图是无向的 . 这是一个根据需要... -
0 votesanswersviews
寻找n-ary图树的分支
给定一个n-ary树，http://en.wikipedia.org/wiki/Tree_%28graph_theory%29，由具有顶点和边的图形描述，我想将树分割成子图 . 每个子图将是n元树的分支 . 子图将包含具有度数为2的顶点的相邻边 . 起始条件是度数大于2的顶点 . 如果非终止，则结束条件也将是度数大于2的顶点 . 如果分支终止（叶子），则结束条件将是度为1的顶点 . 什么算法可以实... -
1 votesanswersviews
从图中消除顶点[关闭]
来自Skiena的书， 设计线性时间算法，通过用边（u，w）替换边（u，v）和（v，w），从图中消除2阶的每个顶点v . 我们还试图通过用单个边缘替换它们来消除多个边缘副本 . 请注意，删除边的多个副本可能会创建一个2级的新顶点，必须将其删除，并且删除2级顶点可能会创建多个边，这些边也必须被删除 . 一般来说，我至少有一种方法，对于这个问题，我很无奈 . 这不是新闻，而只是我自己准备面试 . -
1 votesanswersviews
计算有向图的平方的算法（以邻接表的形式表示）
我正在构建一个算法来计算有向图的G ^ 2，有向图是一种邻接列表的形式，其中G ^ 2 =（V，E'），其中E'定义为（u，v）∈E '如果在G中u和v之间有一条长度为2的路径 . 我很好地理解了这个问题并找到了一个我认为是正确的算法，但是算法的运行时间是O（VE ^ 2）其中V是顶点数和E是图的边数 . 我想知道如何在O（VE）时间内做到这一点，以使其更有效率？ 这是算法，我提出： 顶点中的顶点... -
2 votesanswersviews
最短路径访问无向图中的顶点集
我在室内 Map 中有一个无向的位置图 . 给定一组顶点时，我想找到覆盖所有顶点的最短路径 . 图包含52个顶点和150 - 250个边 . 什么是我可以用来找到最短路径的最佳算法 . 请不要混淆这是一个旅行商问题 . 它不必覆盖所有节点 . 只有给定的节点集 . -
0 votesanswersviews
写入相邻列表图时出现未知错误
我正在编写一个带加权边的相邻的基于列表的图 . 我的目标是实现一个图来测试Djikstra的最短路径算法 . 我在实现removeEdge功能时遇到了麻烦 . 我查看了构建消息，但我不知道下面的错误是什么 . 在下面这个之前有一些警告但是它们很小，因为它编译并运行正常 . c：\ program files（x86）\ codeblocks \ mingw \ bin .. \ lib \ gc... -
-1 votesanswersviews
广度优先搜索队列
我正在看这个作业： 考虑在无向图中从s执行广度优先搜索期间同时在FIFO队列上的两个顶点a和b . 以下内容哪些是对的？ s和a之间的最短路径上的边缘数量比s和b之间的最短路径上的边缘数量多一个 . s和a之间的最短路径上的边缘数量至少比s和b之间的最短路径上的边缘数量少一个 . a和b之间有一条路径 . 可能的答案：a）1只有b）1和2只有c）2只有d）1,2和3 我知道如何解决它，但我... -
1 votesanswersviews
在图中查找所有独立连接
我有一个无向图 . 有没有什么有效的算法可以找到两个节点之间的所有独立连接？通过独立，我的意思是这些连接可以有共同的节点，但不能有共同的边缘 . 在此示例中，有2个独立的连接，从0到8（0-2-3-4-8或0-5-6-7-8） . 我尝试连续使用广度优先搜索算法，而我已经看过“伪删除”边缘 . 问题是我可以通过这种方式通过图表：0-5-4-8这是不对的，因为我不能做任何其他路径 . 谢谢你的帮助... -
15 votesanswersviews
深度优先搜索广度优先搜索的优点，反之亦然
我已经研究了两个图遍历算法，深度优先搜索和广度优先搜索 . 由于这两个算法都用于解决图遍历的相同问题，我想知道如何在两者之间进行选择 . 我的意思是比一个更有效其他或任何理由为什么我会在特定场景中选择一个而不是另一个？ 谢谢 -
3 votesanswersviews
广度优先搜索树如何包含跨边界？
好吧，我知道无向图的广度优先搜索树不能有后沿 . 但我想知道它怎么能有一个跨界？我无法对由OFS构造的图形G的生成树进行成像，其中包含一个交叉边缘 . -
2 votesanswersviews
彩色边缘图中的最短路径
在无向和连通图中，每条边都有一种颜色（红色，绿色或蓝色） .有效路径是具有每种颜色的至少一个边缘的路径 .问题是如何找到最短的有效路径或确定不存在 . 我试图使用BFS但无法找出解决方案 .关于如何开始的任何想法？ -
1 votesanswersviews
深度优先搜索：格式化输出？
如果我有以下图表： Marisa Mariah \ / Mary---Maria---Marian---Maryanne | Marley--Marla 如果“玛丽”是我的起点，我应该如何实现深度优先搜索功能？ Mary Maria Marisa Mariah Marian Maryan... -
1 votesanswersviews
Bellman Ford算法无法计算有向边加权图的最短路径
当我在书Algorithms, 4th edition, Robert Sedgewick and Kevin Wayne中遇到下面的问题时，我最近了解了最短路径算法 . 假设我们将EdgeWeightedGraph转换为Directed EdgeWeightedGraph，方法是在EdgeWeightedGraph中为每个Edge创建EdgeWeightedDigraph中的两个Directe... -
2 votesanswersviews
重复深度优先搜索算法
我正在用Java编写程序，我必须实现三种搜索算法，其中三种是深度优先的图搜索算法 . 我的程序遍历由邻接矩阵在内部表示的连通图，并使用每个算法的前沿和探索集 . 边界存储扩展父节点的未探测子节点，探索集存储实际已扩展的节点 . 探索集的目的是避免重复，从而避免无限循环 . 我的前沿是使用链接的阻塞deque和我使用链接哈希集的探索集实现的 . 然而，在测试该算法实现的初始版本时，我注意到仍然存在少... -
3 votesanswersviews
在彩色边缘图中找到最短的有效路径
给定有向图G，边缘颜色为绿色或紫色，G中的顶点S，我必须找到一个算法，找到从_到27181860_中每个顶点的最短路径（和所需的绿色一样多） . 在删除所有紫色边缘之后我想到了G上的BFS，并且对于最短路径仍然无穷大的每个顶点，做一些尝试找到它的东西，但是我有点卡住，并且它需要很多运行时间... 还有其他建议吗？ 提前致谢 -
4 votesanswersviews
使用A星查找路径的启发式函数
我正在尝试为以下问题找到最佳解决方案 每个节点内表示的数字表示为 (x,y) . 节点的相邻节点始终具有 y 值（当前节点y值为1） . 当我们从一个节点到另一个节点时， x 值的变化成本为1 如果 x 的值没有变化，则从节点到其相邻节点没有任何成本 . 具有相同 y 值的2个节点被认为是相邻的 . 最优解是成本最低的解决方案，我正在考虑使用A *路径寻找算法来寻找最优解... -
0 votesanswersviews
通过某些边缘的最短路径算法
我需要在图表中找到最短路径，该路径至少经过标记为“必须通过”的一条边 . 有任何想法吗？可以修改Dijkstra的算法以实现这一目标吗？ 谢谢 . -
2 votesanswersviews
双向A *没有找到最短路径
我正在Python 2.7.12中实现双向 A* 算法，并从Russell和Norvig，第3章在罗马尼亚 Map 上测试它 . 边缘有权重，目的是找到两个节点之间的最短路径 . 以下是测试图的可视化： 我的双向A *失败的示例是起点为 'a' 且目标为 'u' . 这是我的实现找到的路径：['a', 's', 'f', 'b', 'u'] 的长度是 535 . 这是从 'a' 到 'u' ... -
0 votesanswersviews
可以对AnyTime加权A *算法进行哪些改进？
首先，对于那些不知道的人 - Anytime Algorithm是一种算法，它可以获得它可以运行的时间量作为输入，它应该在那个时间提供最佳解决方案 . 加权A *与A *相同，f函数中有一个差异： （其中g是节点的路径成本，h是到达目标之前到路径末端的启发式） Original = f(node) = g(node) + h(node) Weighted = f(node) = (1-w)g(... -
3 votesanswersviews
两点之间网格中的最短路径 . grab 了
我有这个问题，我必须通过向右或向下移动找到NxM网格中从A点（总是左上角）到B点（总是右下角）的最短路径 . 听起来很简单，嗯？好吧，这里有一个问题：我现在只能移动我正坐在的瓷砖上显示的数字 . 让我说明一下： 2 5 1 2 9 2 5 3 3 3 1 1 4 8 2 7 在这个4x4网格中，最短路径将需要3个步骤，从左上角2个节点向下步行到3个，从那里3个节点从右到1，然后从1个节点向下到达... -
0 votesanswersviews
在两个顶点之间创建成本最低的路径
我有一个加权无向图 . 给定该图中两个顶点之间没有路径的顶点，我想在之间创建一条路径，方法是在图形中添加边，尽可能少地增加图的总权重 . 是否有已知的算法来确定要添加哪些边？ 一个类似的问题是，如果我有一个国家的道路系统的图表，其中有两个城市无法通过道路彼此进入，我想 Build 最短的一组新道路将连接它们 . 在它们之间可能还有其他城市与两者都没有联系，如果它们存在，我想利用它们 . 这是一个小... -
2 votesanswersviews
2D航路点寻路：WP的组合从curLocation到targetLocation
请花点时间了解我的情况 . 如果不可理解，请在评论中告诉我 . 我有一个Waypoints的ArrayList . 这些航点不是任何顺序 . 航点具有以下属性：{int type, float z, float y, float x, float rotation} 这适用于三维世界，但由于我的寻路不应该关心高度（因此将世界视为二维世界），因此忽略y值 . 轮换对于这个问题并不重要 . 在这个... -
18 votesanswersviews
最短的路径和测地线
给定一个完全由四边形组成的网格，其中每个顶点都具有效价n（n> = 3），并且不在同一平面上，我需要从一组封闭的种子顶点中找到网格中每个顶点的距离 . 也就是说，给定一个或多个网格顶点（种子集），我需要构建一个距离图，该距离图存储每个网格顶点距种子集的距离（距离自身的距离为0） . 在花了一些时间寻找可能的解决方案之后，我得到了以下图片： 1）这不是微不足道的，并且在过去20年左右的时间里已... -
4 votesanswersviews
带有彩色边缘的图形：最短路径，最多k个颜色变化？
我有一个带有彩色加权边的有向图 . 有2种颜色 . 每个边缘只能有1种颜色 . 我想找到颜色变化有限的最短路径 . 从一个顶点可以出现最多2个边缘，其中有2种不同的颜色，2个边缘有2种不同的颜色 . 例如，在此图中： 最短路径最多3个颜色变化 9 最大 0 颜色变化最短路径是 6+1+4=11 等 . 我的解决方案是递归访问所有可能的路径并交换，如果递归找到一个更好的，使这个问题呈指数级 . 是... -
1 votesanswersviews
图最短路径？
我面对的是我认为是图表上的一种最短路径问题 . 我需要找到从节点A到B的最短路径，考虑到所有边缘对于连接的顶点具有正权重，对于未连接的顶点具有∞ . 顶点具有可变的正重量 . 考虑到该路径中涉及的所有顶点，路径的成本是具有最大权重的顶点的权重 . 我应该在这种情况下应用Dijkstra，如果是这样的话，考虑到每个Vertex的权重会根据之前访问的顶点而变化吗？ 你能指点我怎么解决这个问题吗？