I really struggled with describing this in the title but I'll give it a go in a longer format.
我真的很难在标题中描述这个,但我会用更长的格式来试试。
I'm really stumped on this problem and I'm not looking for answers, just a little help or some specific topics to read up on.
我真的很难解决这个问题,我不是在寻找答案,只是寻求一些帮助或一些特定的主题来阅读。
What I have is a directed Graph with edges of various weights, both negative and positive. What I am attempting to do is to write an algorithm that is provided with two nodes positioned on the graph (and assuming they're connected) finds a path between them that results in the total weight of the path being either zero or negative. The path can include nodes multiple times (hopefully allowing for the path to offset the positive weight of included edges).
我所拥有的是具有各种权重边缘的有向图,包括负数和正数。我试图做的是编写一个算法,该算法提供有两个位于图上的节点(并假设它们已连接)在它们之间找到一条路径,导致路径的总权重为零或负。该路径可以多次包括节点(希望允许路径偏移所包含边的正权重)。
I'm currently reading Russel and Norvig's Artificial Intelligence, but am struggling to find a way to apply the logic in the text to my problem due to various problems (The algorithm continuously going round the negative cycle). I'm not fully understanding how to utilize methods such as Backtrack and AStar for this
我目前正在阅读Russel和Norvig的人工智能,但由于各种问题(算法不断绕过负循环),我很难找到一种方法将文本中的逻辑应用于我的问题。我还没有完全理解如何利用Backtrack和AStar等方法
If anyone could point me in the right direction of something that would help me understand my problem better it would be a great help, I'm fine with dealing with DFS and BFS and many other things in relation to Graphs but having to find a path between two nodes with the weight restrictions is really baffling me.
如果有人能指出我能帮助我更好地理解我的问题的正确方向,那将是一个很大的帮助,我很好处理DFS和BFS以及与Graphs相关的许多其他事情,但必须找到一条路径两个节点之间的重量限制真是令我困惑。
Thanks
Below I've included a sample graph, I need to be able to find a path from Start to Goal where the total weight of the path doesn't exceed Zero.
下面我已经包含了一个示例图,我需要能够找到从Start到Goal的路径,其中路径的总权重不超过零。
Example Graph http://i144.photobucket.com/albums/r166/ZooropaTV/bu.jpg
示例图http://i144.photobucket.com/albums/r166/ZooropaTV/bu.jpg
Just realised that a lot of the searching/Reading I've been doing has been misguided, since my goal isn't necessarily about finding the shortest path by weight, but by visiting the minimum required number of nodes, I need to have another think about it now, but still would like any advice
刚刚意识到我所做的很多搜索/阅读都被误导了,因为我的目标不一定是按重量找到最短的路径,而是通过访问所需的最小节点数,我需要另外一个想法关于它现在,但仍然想要任何建议
1 个解决方案
#1
0
I think this is what you want: The Floyd–Warshall algorithm http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
我想这就是你想要的:Floyd-Warshall算法http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
You'll have to modify it to fit your needs but it will detect negative cycles thus allowing you to find a path of zero or lesser weight.
您必须修改它以满足您的需要,但它会检测负循环,从而允许您找到零重量或更小重量的路径。
#1
0
I think this is what you want: The Floyd–Warshall algorithm http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
我想这就是你想要的:Floyd-Warshall算法http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
You'll have to modify it to fit your needs but it will detect negative cycles thus allowing you to find a path of zero or lesser weight.
您必须修改它以满足您的需要,但它会检测负循环,从而允许您找到零重量或更小重量的路径。