标签: graph-theory

我正在使用HASKELL进行图形游戏.除了使用bfs或树等之外,我愿意从图中的节点到特定节点获得适当的到达能力的方法.

当我要求haskell中的代码从一个节点到一个特定节点的覆盖能力时,有必要告诉你我对haskell完全不熟悉.我一直在阅读教程和简单的例子,但是当它实现时,我就迷失了.我的图是一个有向图,并说我想检查我是否可以从图中的节点v到达节点w.

请帮我解决以下问题的算法 -

鉴于一系列事实,我们希望尽可能多地消除冗余.该问题涉及的事实是大写字母之间的传递关系的成员.因此,每个事实都是一对大写字母,例如AB,意味着A与B相关.一个字母可能与自身相关,也可能不相关,但是传递性成立:如果A与B相关,而B与C相关,那么我们可以推断A与C相关.创建一个FactCount类,它包含一个方法minFacts,它被赋予一个已知的String []并返回最小的事实集合的大小,这些事实将允许我们推断所有(并且只有那些东西)可以从已知的事实中推断出来.

已知的每个元素将包含由单个空格分隔的1个或多个事实.最小的一组事实可能包含可从已知但未包含在其中的事实.

例如:

{"AB AC CA AA BC","AD"}

返回:4

AB,CA,BC和AD允许我们推断AA(AB,BC,CA通过传递性给出AA)和AC(AB,BC通过传递性给出AC),并且没有更小的子集允许我们推断所有已知事实.

PS - 它不是功课.只是我在网上找到的一个问题,几个小时都无法解决...

我认为汉密尔顿循环问题可归纳如下:

给定一个无向图G = (V, E),哈密顿量电路是一次G通过每个顶点G一次而不是一次.

现在,我想做的是减少我的问题.我的问题是:

给定的加权无向图G,整数k,和顶点u, v 都在G,有在一个简单的路径G从u到v 具有至少总重量k？

因此,要知道哈密顿循环问题是NP完全的,通过将这个问题简化为哈密顿量,这个问题也被证明是NP完全的.我的问题是将它减少为哈密顿量的函数.

1. 最大的问题是汉密尔顿问题不处理边权重,所以我必须将我的图转换为没有任何权重的图.
2. 最重要的是,这个问题有一个指定的开始和结束(u和v),而汉密尔顿主义者找到一个循环,所以任何开始都与完成相同.

对于(1),我正在考虑通过一个图表,其中所有简单的路径总重量不超过k.对于(2),我认为这不是一个问题,因为如果存在哈密顿循环,则从u到v的简单路径可以从中切除.

所以,我真正的问题是:

1. 我的解决方案是否会给我正确的答案？
2. 如果是,那么我怎样才能取出产生总重量小于k的简单路径的边缘而不影响实际解决方案可能需要其中一条边缘的可能性？因为如果边缘e被取出,因为它为E的子集产生了一个简单的权重路径<k,它仍然可以在具有不同边缘组合的简单路径中使用,以产生权重> = k的路径.

谢谢!

我正在寻找解决最短路径问题的最佳方法:

我有一个带有未加权边缘的有向图.如果存在这样的路径,我需要能够找到任意两个节点之间的最短路径.使这个问题与常规最短路径问题不同的是:如果存在具有最短长度的多个路径,我需要能够选择具有最高"权限"的路径.

每个节点都有一个数字权限,具有最高权限的路径只是具有最高节点权限总和的路径.

总结: 我需要有向图中一对节点之间的最短路径,但如果有多条路径具有相同的最小长度,我需要找到具有最高路径权限的路径.

这样做的最佳方法是什么？有没有办法将其转换为加权图,然后只使用Dijkstra的算法？有没有办法修改广度优先搜索给我一组最短路径,然后我可以迭代查找最高权限路径？

我正在尝试开发一种算法,其中我有一个位置类.在每个类中,我创建一个相邻位置的列表.我想知道,我怎样才能获得从一个位置到另一个位置的最短路径.我试图寻找不同的算法,但似乎他们没有回答我的问题.

例如,我有一个A点,我想去B点,

A - - C - - H - - J
      |
      F- - K- -B 

我的想法是,如果B位于A的相邻位置列表中,那么这是最短路径.如果没有,它应该搜索A的相邻位置的相邻位置.但是我不知道如何在代码中实现它或者它是一个好的算法.我还想显示A - C - F - K - B作为最短路径的路线.我也在j2me上开发这个,所以我对我可以使用的java功能有点限制.如果有人可以帮助我,我将不胜感激.谢谢

我想要一个数据结构,其中键是多面体(无向3个连接的平面图;在我的情况下,它们可能大多数是<30个顶点),查找等式是同构.有没有一种有效的方法来实现这种映射？

我已经研究和反思了一些但没有提出解决方案.似乎解决方案可能是其中之一

• 一种自定义数据结构,使用图表本身来查找数据

• 二叉搜索树(或其他类似树),需要明确定义的排序.(我怀疑存在这样的排序)

• 哈希表,需要良好的哈希值.我不能立即想出一个比"顶点数"或类似更好的一个.

我怎样才能获得有效的查找？

所以问题很简单.给定一个图(我希望图的结构在这个问题上没有多大关系),我该怎么做呢？

我最近问过一个关于生成列表的问题,其中每个元素都会在其末尾附加许多元素.答案应该有希望让我做一个我需要做BFS的队列.但是搜索需要另一个关键组件,它将节点标记为已访问,因此我们不会再次检查它们.这也需要在算法的执行上没有开销.无论是标记还是阅读.

既然Haskell不允许我改变状态,那我该怎么做呢？

(我不是在寻找将命令式代码翻译成Haskell的方法.惯用的Haskell解决方案会非常棒.)

假设有一个有向图由以下命名的顶点组成:

"ABC", "ABD", "ACB", "ACD", "ADB", "ADC", "BAC", "BAD",
"BCA", "BCD", "BDA", "BDC", "CAB", "CAD", "CBA", "CBD",
"CDA", "CDB", "DAB", "DAC", "DBA", "DBC", "DCA", "DCB"

这些是4个不同字母的3个字母排列.(total = 4*3*2=24)顶点名称还描述它们之间的边.如果源的最后两个字符等于目标的前两个字符,则任何两个顶点相互连接

甲BC - > BC d

要么

D CB - > CB A.

该图与De Burjin或Kautz非常相似,但不相同.它有很强的联系,我知道它有汉密尔顿循环.

为了解决这个问题,我不是算法方面的专家,我只是通过最新的boost图库找到了hawick_unique_circuits()函数,它枚举了所有周期,这里是我的示例代码:

#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/hawick_circuits.hpp>
#include "combination.hpp" // from http://howardhinnant.github.io/combinations.html

using namespace std;
using namespace boost;

typedef boost::adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, uint32_t> > TGraph;

TGraph m_Graph; …

我正在尝试创建深度优先算法,该算法指定完成时间(顶点无法再展开的时间),这些算法用于Kosaraju算法等事情.我能够相当容易地创建DFS的递归版本,但是我很难将其转换为迭代版本.

我正在使用邻接列表来表示图形:顶点的字典.例如,输入图{1: [0, 4], 2: [1, 5], 3: [1], 4: [1, 3], 5: [2, 4], 6: [3, 4, 7, 8], 7: [5, 6], 8: [9], 9: [6, 11], 10: [9], 11: [10]}表示边(1,0),(1,4),(2,1),(2,5)等.以下是使用简单堆栈(LIFO)的迭代DFS的实现),但它不计算完成时间.我遇到的一个关键问题是,由于顶点被弹出,一旦顶点完全展开,算法就无法追溯其路径(与递归不同).我该如何解决？

def dfs(graph, vertex, finish, explored):
    global count

    stack = []
    stack.append(vertex)

    while len(stack) != 0:
        vertex = stack.pop()

        if explored[vertex] == False:
            explored[vertex] = True

            #add all outgoing edges to stack:
            if vertex in graph:                 #check if key exists in …

假设您正在尝试将由N个组件组成的系统组合在一起.在放入其他组件之前不能放入某些组件(不能在第一层之前建造第二层),并且除非没有放入其他组件,否则无法放入某些组件(不能在关闭墙壁后将绝缘材料放在墙壁上).

在数学上我通过将每个组件表示为位域中的一位来对此进行建模.我从全零开始,我尝试一次翻转一位,并且我有一些评估器功能,它确定该翻转是否是允许的移动.换句话说,我从空集开始,尝试逐个添加N的元素,直到它们都在我的集合中.但是,并非所有此类添加都是允许的.

根据我的数学,对应于上述问题的图将具有2 ^ N个节点,每个步骤S沿着构建过程(因此0 <= S <= N)由N组成!/(S!*(NS)!)节点.所以有N种方法放置第一个组件,(N ^ 2 - N)/ 2种方式放置第二个组件,依此类推.每个节点将具有与其子集N中的元素一样多的父节点,并且节点具有的父节点和子节点的数量将等于N中的元素的数量.

O(2 ^ N)除了非常小的N之外不能解决任何问题,但是我想知道是否有这个问题的名称,以便我可以阅读更多关于它的信息.

(我为我对技术术语的不当使用提前道歉.)