标签: graph-algorithm

我正在做一个问我这个问题的作业问题:

Tiven有限的一组数字,并且一个目标号码,发现如果集合可以用于使用基本的数学运算(ADD,SUB,MULT,格),并使用组中的每个数字来计算目标数量恰好一次(所以我需要耗尽这套).这必须通过递归来完成.

所以,例如,如果我有这个集合

{1, 2, 3, 4}

和目标10,然后我可以通过使用

((3 * 4) - 2)/1 = 10. 

我试图用伪代码表示算法,但到目前为止还没有走得太远.我认为图表是要走的路,但肯定会感谢你的帮助.谢谢.

我有一个未加权的连接图.我想找到一个连接的子图,它肯定包含一组特定的节点,并且尽可能少的附加内容.怎么可以实现呢？

为了以防万一,我将使用更精确的语言重述问题.设G(V,E)为未加权,无向连通图.设N是V的某个子集.找到G(V,E)的最小连通子G'(V',E')的最佳方法是什么,N是V'的子集？

近似没问题.

为了找到图中的最大流量,为什么不仅仅考虑该路径中具有最小边缘容量的所有增强路径而不考虑后边缘就足够了？我的意思是,如果我们从它那里假设流量,那么称它为后沿是什么意思呢？

我想从汉明距离为(例如)1 的单词列表中构建一个图形,或者换句话说,如果它们只与一个字母(lo l - > lo t)不同,则连接两个单词.

所以给定

words = [ lol, lot, bot ]

图表将是

{
  'lol' : [ 'lot' ],
  'lot' : [ 'lol', 'bot' ],
  'bot' : [ 'lot' ]
}

简单的方法是将列表中的每个单词与其他单词进行比较并计算不同的字符; 遗憾的是,这是一种O(N^2)算法.

我可以使用哪种algo/ds /策略来获得更好的性能？

另外,我们假设只有拉丁字符,并且所有单词都具有相同的长度.

过去几周我一直在使用nodejs和玩多人HTML5游戏websockets.

我已经陷入了这个问题一段时间了.想象一下,我有一个用数组实现的tileheet map(如下所示).

1或棕色瓷砖 - 路上有障碍物,玩家无法通过它.

0或绿色瓷砖 - 是允许玩家移动的自由路径.

通过以下方式访问地图上的任何图块:

 array[x][y]

我想创建最快的算法,找出地图两点之间的最短路径(如果有的话).你会如何解决这个问题？我知道这是常见的问题.

示例:

位置(1,7)的玩家用一些人工智能发射子弹,该AI会朝向位置(6,0)的敌方玩家.子弹必须计算两个球员之间的最短路线,如果没有,它只会在墙上爆炸.

问题:

如何有效地找到两点之间的最短路线？

给定一个完全由四边形组成的网格,其中每个顶点都具有效价n(n> = 3),并且不在同一平面上,我需要从一组封闭的种子顶点中找到网格中每个顶点的距离.也就是说,给定一个或多个网格顶点(种子集),我需要构建一个距离图,该距离图存储每个网格顶点距种子集的距离(距离自身的距离为0).

在花了一些时间寻找可能的解决方案之后,我得到了以下图片:

1)这不是微不足道的,并且在过去20年左右的时间里已经开发了不同的方法

2)考虑3d域的每个算法都限于三角域

说,这是我得到的图片:

Dijkstra算法可以用作在网格边缘之后找到2个顶点之间的最短路径的方法,但是它非常不准确并且将导致错误的测地线.Lanthier(洛杉矶)提出了改进,但错误仍然很高.

Kimmel和Sethian(KS)提出了一种快速行进方法-FMM-来解决Eikonal方程,解决计算从种子点开始的波传播并记录波穿过每个顶点的时间的问题.不幸的是,这个算法虽然简单易于实现,但仍然会带来非常不准确的结果,必须注意避免使用钝角三角形,或者以非常特殊的方式处理它们.Novotni(NV)解决了单个种子场景中(KS)精度的问题,但我不清楚是否:

a)它仍然受到钝角问题的困扰

b)当在多种子点场景中使用时,必须为每个种子实施单个FMM,以便从每个种子中找到每个网格顶点的最小距离(即,在10个种子点场景中,FMM将具有每个网格顶点运行10次)

另一方面,Mitchell等人提出了导致0错误的精确算法-MMP-.(MI)在87年,AFAIK从未真正被扼杀(可能是由于所需的计算能力).同样的方法,Surazhsky&al.(SU)提供了基于MMP的替代精确算法,其在速度方面应该优于后者,仍然导致正确的结果.不幸的是,计算所需的计算能力,即使比原始MMP小得多,仍然足够高,因此此时实时交互式实现是不可行的.(SU)也提出了他们的精确算法的近似,他们称之为平精确.它应该花费相同的FMM计算时间,同时只带来1/5的错误,但是:

c)我不清楚它是否可用于多种子方案.

Chen&Han(CH)和Kapoor(KP)已经提出了其他精确的最短路径算法,但是第一种算法绝对慢,第二种算法太复杂而无法在实践中实施.

所以..底线是:我需要一组距离,而不是两点之间的最短路径.

如果我做对了,

要么我使用FMM来获取单个通道中每个顶点的距离,

-要么-

使用另一种算法来计算从每个网格顶点到每个种子点的测地线,并找到最短的一个(如果我把它弄好,这意味着在每个网格顶点的每个种子点上调用该算法,即在10,000个顶点网格上和一个50分的种子集,我将不得不计算500,000测地线,以获得10,000最短的一个)

我错过了什么吗？FMM是一次通过多种种子距离的唯一方法吗？有人知道平面精确算法是否可用于多种子点场景？

日Thnx

笔记:

(洛杉矶):Lanthier等."在多面体表面上逼近加权最短路径"

(KS):Kimmel,Sethian"在流形上计算测地线路径"

(NV):Novotni"计算三角网格上的测地距离"

(MI):米切尔等人."离散测地线问题"

(SU):Surazhsky,Kirsanov等."网格上的快速精确和近似测地线"

(CH):Chen,Han,"多面体的最短路径"

(KP):Kapoor"高效计算geodeisc最短路径"

我继续在Scala中实现了Tarjan的SCC算法的教科书版本.但是,我不喜欢代码 - 这是非常必要/程序化的,有很多变异的状态和簿记索引.是否有更多"功能"版本的算法？我相信算法的命令式版本隐藏了算法背后的核心思想,而不像功能版本.我发现其他人遇到了与此特定算法相同的问题,但我无法将他的Clojure代码转换为idomatic Sc​​ala.

注意:如果有人想要试验,我有一个很好的设置,可以生成随机图并测试你的SCC算法与运行Floyd-Warshall

任何人都可以在C#中实现Reverse Breadth First遍历算法？

通过反向宽度第一次遍历,我的意思是不是从公共节点开始搜索树,而是想从底部搜索树并逐渐收敛到公共节点.

让我们看下图,这是广度优先遍历的输出:

在我逆向广度优先遍历9,10,11和12将是第一个找到的几个节点(它们的顺序并不重要,因为他们都是第一顺序).5,6,7和8是发现第二几个节点,依此类推.1将是找到的最后一个节点.

任何想法或指针？

编辑:将"广度优先搜索"更改为"广度优先遍历"以澄清问题

在此早期的问题中,OP询问如何在图中找到从u到v的最短路径,并且还通过某个节点w.接受的答案非常好,就是运行Dijkstra算法两次 - 一次从u到w,一次从w到v.这时间复杂度等于两次调用Dijkstra算法,即O(m + n log n).

现在考虑一个相关的问题 - 给你一个节点序列u ₁,u ₂,...,u _k,并想找到从u ₁到u _k的最短路径,使路径通过u ₁,u ₂, ...,U _ķ秩序.显然,这可以通过运行Dijkstra算法的k-1个实例来完成,每个相邻顶点对应一个,然后将最短路径连接在一起.这需要时间O(km + kn log n).或者,您可以使用像Johnson算法这样的全对最短路径算法来计算所有最短路径,然后在O(mn + n ² log n)时间内将适当的最短路径连接在一起,这对于比n大得多的k是有利的.

我的问题是,当k很小时,是否有一种解决这个问题的算法比上述方法更快.这样的算法存在吗？或者迭代Dijkstra's得到了它的好处？

在一个背包的情况下,用于最佳地填充背包的动态编程算法很好地工作.但是,是否有一种有效的已知算法可以最佳地填充2个背包(容量可能不相等)？

我尝试了以下两种方法,但它们都不正确.

1. 首先使用原始DP算法填充第一个背包,填充一个背包,然后填充另一个背包.
2. 首先填充尺寸为W1 + W2的背包,然后将溶液分成两个溶液(其中W1和W2是两个背包的容量).

问题陈述(另见维基百科的背包问题):

1. 我们必须用一组物品(每个物品具有重量和值)填充背包,以便最大化我们可以从物品获得的值,同时总重量小于或等于背包尺寸.

2. 我们不能多次使用一个项目.

3. 我们不能使用项目的一部分.我们不能把一个项目的一小部分.(每个项目必须完全包含或不包括在内).