-
9 votesanswersviews
TSP变量的近似算法，固定开始和结束任何地方，但在每个顶点允许的起点多次访问
注意：由于旅行不是在它开始的同一个地方结束的事实，而且只要我仍然访问所有这些点，每个点都可以被访问多次这一事实，这不是真正的TSP变体，而是我之所以说是因为缺乏对问题的更好定义 . 所以.. 假设我正在徒步旅行，有n个兴趣点 . 这些景点都通过远足径相连 . 我有一张 Map 显示了所有距离的路径，给我一个有向图 . 我的问题是如何近似一个从A点开始并且访问所有n个兴趣点的旅游，同时结束旅行的任何... -
-1 votesanswersviews
用于排列随机大小的矩形图像的算法，它们之间具有最佳间隔
我需要将图像分散在矩形区域上，使得每个图像与矩形的边之间存在最佳间距（均匀分散/分布） - 不会集中在任何一个区域 . 可以想象它的目的不仅仅是将图像放在矩形上，而是最大化它们之间的间距 . 图像将具有最大宽度和高度，但可以具有不同的宽高比 矩形足够大以包含图像 显然没有重叠 图像不会倾斜 有人提出任何想法或澄清吗？ -
0 votesanswersviews
使用dijkstra算法在图中找到源和目的地之间的最短路径
我想写一个算法，它在有向和无向图中找到两个特定顶点（源和目标）之间的最短路径 . 我知道dijkstra的算法，用于查找所有最短路径图 . 但是你会修改这个算法来找到两个顶点之间的最短路径吗？ -
-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 我知道如何解决它，但我... -
7 votesanswersviews
我应该使用什么算法来查找有向下限但没有上限的有向图上的最小流量？
我应该使用什么算法来查找有向下限但不是上限的有向图上的最小流量？比如这个简单的例子： 在文献中，这是最小的成本流问题 . 然而，在我的情况下，成本与每个边缘所需流量的非零下限相同，所以我在上面提出问题 . 在文献中，问题是：找到单源/单宿有向无环图的最小成本流的最佳算法是什么，其中每个边具有无限容量，流上的非零下界，以及成本等于流量的下限 . 根据我的研究，似乎人们处理任何类型网络的任何类型的最... -
2 votesanswersviews
网络流程方法，用于最大化可以安排的作业数量
我很想通过网络流方法来解决这个问题 . 希望有人在这里花时间帮助我为这个问题构建一个合适且合适的图表 . 构建的图形在求解最大流量时应该导致作业机器分配最大化给定数量的机器和作业调度的作业数量 . 给定m台机器和n个工作，约束m≤n . 使用网络流算法来解决分配，以最大化给定数量的机器的作业数量 . 每个作业 Ji 都有一个开始时间 Si 和结束时间 Fi . 所有机器都是相同的，一次最多可以完... -
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
写入相邻列表图时出现未知错误
我正在编写一个带加权边的相邻的基于列表的图 . 我的目标是实现一个图来测试Djikstra的最短路径算法 . 我在实现removeEdge功能时遇到了麻烦 . 我查看了构建消息，但我不知道下面的错误是什么 . 在下面这个之前有一些警告但是它们很小，因为它编译并运行正常 . c：\ program files（x86）\ codeblocks \ mingw \ bin .. \ lib \ gc... -
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）时间内做到这一点，以使其更有效率？ 这是算法，我提出： 顶点中的顶点... -
0 votesanswersviews
找到最陡峭的爬坡功能的路径
当使用Steepest Hill Climbing Search时，当你达到无限循环时会发生什么 - 也就是说，你发现自己在相同的两个状态之间来回走动，因为它们都是彼此最好的接班人？ 例如，在下图中， (J) 将反复转到 (K) ，反之亦然 . 如果我正在编程它，我想我会在访问状态上放置某种标志，所以我知道我是否正在重新审视同一个 . 但是，在关于Steepest Hill Climbing算法的... -
0 votesanswersviews
用于检测非直方图中的循环的最佳并行算法
我想检测无向图中的循环，以便找到最小生成树（特别是我想使用Kruskal算法） . 由于我想并行化代码，我想知道哪种算法是最好的，深度优先搜索union-find算法？谢谢你的任何建议 . -
2 votesanswersviews
Java检测循环有向图
我目前正在尝试编写一个程序来检查是否 directed graph is cyclic or not . 我不确定我做错了什么（我很可能做错了所以所以请StackOverflow，告诉我我的愚蠢！） . 我已经到了不知道可能是什么问题的地步 . 输入是一个邻接列表，例如： 0: 2 4 1: 2 4 2: 3 4 3: 4 4: 0 1 2 3 （0指向2和4; 1指向2和4，依此类推....... -
1 votesanswersviews
在图中查找所有独立连接
我有一个无向图 . 有没有什么有效的算法可以找到两个节点之间的所有独立连接？通过独立，我的意思是这些连接可以有共同的节点，但不能有共同的边缘 . 在此示例中，有2个独立的连接，从0到8（0-2-3-4-8或0-5-6-7-8） . 我尝试连续使用广度优先搜索算法，而我已经看过“伪删除”边缘 . 问题是我可以通过这种方式通过图表：0-5-4-8这是不对的，因为我不能做任何其他路径 . 谢谢你的帮助... -
15 votesanswersviews
深度优先搜索广度优先搜索的优点，反之亦然
我已经研究了两个图遍历算法，深度优先搜索和广度优先搜索 . 由于这两个算法都用于解决图遍历的相同问题，我想知道如何在两者之间进行选择 . 我的意思是比一个更有效其他或任何理由为什么我会在特定场景中选择一个而不是另一个？ 谢谢 -
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
DFS和BFS输出？
所以我对BFS和DFS算法的输出都感到困惑 . 据我所知，BFS将输入视为 G ，顶点为 x . 输出：返回一个图形，对于 G 中的每个顶点，新图形具有从顶点 x 到图形中任何其他顶点的最短路径 . 是对的吗？如果不是，那是什么？ DFS怎么样？ DFS的输入只是一个图表，是否意味着DFS并不关心你从哪里开始？什么是DFS的输出？ 谢谢 -
1 votesanswersviews
用Java解决n-puzzle
我正在尝试实现一个解决n-puzzle problem的程序 .我在Java中编写了一个简单的实现，它具有一个问题状态，其特征在于表示tile的矩阵 . 我还能够自动生成给出起始状态的所有状态的图形 . 然后，在图表上，我可以使用BFS来查找目标状态的路径 .但问题是我的内存不足，甚至无法创建整个图形 . 我尝试了2x2瓷砖，它的工作原理 . 还有一些3x3（它取决于起始状态和图中有多少个节点） ... -
3 votesanswersviews
广度优先搜索树如何包含跨边界？
好吧，我知道无向图的广度优先搜索树不能有后沿 . 但我想知道它怎么能有一个跨界？我无法对由OFS构造的图形G的生成树进行成像，其中包含一个交叉边缘 . -
2 votesanswersviews
彩色边缘图中的最短路径
在无向和连通图中，每条边都有一种颜色（红色，绿色或蓝色） .有效路径是具有每种颜色的至少一个边缘的路径 .问题是如何找到最短的有效路径或确定不存在 . 我试图使用BFS但无法找出解决方案 .关于如何开始的任何想法？