标签: graph-theory

我正在查看Prim算法的维基百科条目,我注意到它的邻接矩阵的时间复杂度是O(V ^ 2),它的堆和邻接列表的时间复杂度是O(E lg(V))其中E是边数和V是图中顶点的数量.

由于Prim的算法用于更密集的图,因此E可以接近V ^ 2,但是当它接近时,堆的时间复杂度变为O(V ^ 2 lg(V)),其大于O(V ^ 2).显然,堆只会在搜索数组时提高性能,但时间复杂性则另有说法.

算法如何通过改进实际减速？

我有一个图表,n节点作为邻接矩阵.

是否有可能在不到O(n)时间内检测到水槽？

如果有,怎么样？如果不是,我们如何证明呢？

接收器顶点是一个顶点,具有来自其他节点的入射边缘,没有出射边缘.

这就是问题:

我有n个点(p1,p2,p3,... pn),每个点都可以以确定的成本x连接到任何其他点.

每个点属于一组点类型中的一个(例如"A""B""C""D"......).

方法的输入是我想要遵循的路径,例如"ABCADB".

输出是连接输入类型I的点的最短路径,例如"p1-p4-p32-p83-p43-p12",其中p1是A型,p4是B型,p32是C-类型,p83是A型,p43是D型,p12是B型.

"简单"的解决方案包括计算所有可能的路径,但计算成本非常高!

有人能找到更好的算法吗？

正如我在标题中所说,我不知道它是否存在!

更新:

阻止我使用Dijkstra和其他类似算法的关键点是我必须根据类型链接点.

作为输入,我有一个类型的数组,我必须按顺序链接.

这是Kent Fredric的图像(非常感谢),它描述了最初的情况(红色允许的链接)!

alt text http://img13.imageshack.us/img13/3856/immagineaol.jpg

一个真实的例子:

一个男人想早上去教堂,去餐馆,下午去博物馆.

地图上有6个教堂,30家餐厅和4个博物馆.

他希望教堂休息博物馆的距离是最小的.

我有一个问题,这是我的计划的一部分.

对于树T =(V,E),我们需要在树中找到节点v,其最小化从v到任何其他节点的最长路径的长度.

那么我们如何找到树的中心？是否只能有一个中心或更多？

如果有人能为我提供良好的算法,那么我就可以了解如何融入我的计划.

我正在根据这张图片进行练习.我发现最大团体大小为4.我对图论的概念有几个问题.

根据定义,clique是一个完整的子图,其中每对顶点都是连接的.这是否意味着,如果我计算3个派系,(3,4,5),(3,4,6),(3,5,6)和(4,5,6)将被视为3个派系？或者我应该省略那些子图,因为它们是4-clique的一部分.

每个图表只有一个最大集团吗？在我的脑海中想象它,我觉得有可能有​​一个以上的最大团.

练习中的一个问题是询问每个具有一个或多个节点的图形是否必须至少有一个集团.是否存在2-clique(只是一个边缘)或者每个集团是否应该形成一个封闭的形状？

我似乎无法画出一个没有3-clique的4-clique的例子,所以可以安全地假设每个4-clique至少有一个3-clique？我将如何更大规模地检查这样的东西？

我将开始一个关于自动机和图论的科学项目,我正在寻找一个支持以下功能的图库:

• 有向/无向图
• 图同构测试(即图g1同构wrt g2？)
• 子图同构测试(即图形g1与g2的子图同构？)
• 图搜索,访问等
• 可能,非常快,因为我需要做一些严肃的计算

我知道Boost Graph Library,但据我从文档中理解,它缺少子图测试.

所以,我的问题是:哪个是最好的c ++图形库,好吗？他们不需要为我需要的每个功能提供支持,我知道现有的库当然没有完全满足我的需求.

在过去的比赛中,我被要求使用0到9之间的数字生成10位数字符串.字符串中使用的任何四位子字符串都不能再次使用.

使用这些规则可以生成的最大数量的唯一字符串是多少？列出他们.

例:

如果在列表中使用字符串0243697518,则无法生成包含0243,2436,4369,3697,6975,9751和7518的字符串

为了解决这个问题,我编写了一个c ++程序,只需扫描所有的"0123456789"排列,如果之前没有使用过代码的4位子字符串,则将它们添加到解决方案列表中.但我的算法的问题是,解决方案列表的大小取决于您首先添加到列表中的起点.如果我开始从"0123456789"添加到列表中,列表最终会有504个条目,这不是最大要求.我真的很想知道如何解决这个问题,任何帮助都非常感谢.我愿意听你的数学解决方案或任何算法建议来生成所要求的列表.

#include <iostream>
#include <cstdint>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

void main(void)
{
    set<string> substring_list; // holds the list of used 4 digit sub-strings
    set<string> solution_list;

    string code = "0123456789";
    do 
    {
        vector<string> subs;
        for (int i = 0; i < 7; i++)
        {
            // adds all 4  digits sub-strings used in the code
            subs.push_back(code.substr(i, 4));
        }

        if ((substring_list.find(subs[0]) == substring_list.end()) &&
            (substring_list.find(subs[1]) == substring_list.end()) &&
            (substring_list.find(subs[2]) == substring_list.end()) &&
            (substring_list.find(subs[3]) …

好的,所以在拓扑排序中,取决于输入数据,通常有多个正确的解决方案,可以对图形进行"处理",以便所有依赖关系都在"依赖"它们的节点之前.但是,我正在寻找一个稍微不同的答案:

假设以下数据: a -> b和c -> d(a必须在之前b,c必须在之前d).
只有这两个限制,我们有多种候选方案:( ,,a b c d 等).但是,我正在寻找创建一种"分组"这些节点的方法,以便在处理组之后,下一组中的所有条目都会依赖它们的依赖关系.对于上面假设的数据,我会寻找像这样的分组.在每个组内,只要组1 在处理组2 中的任何一个之前完成,那么处理节点的顺序(在之前或之前等,反之亦然)并不重要.a c d bc a b d(a, c) (b, d)acbd(a, c)(b, d)

唯一额外的问题是每个节点应该尽可能在最早的组中.考虑以下:
a -> b -> c
d -> e -> f
x -> y

分组方案在(a, d) (b, e, x) (c, f, y)技术上是正确的,因为x在之前y,更优化的解决方案是(a, d, x) (b, e, …

这似乎是正确的,但我在网上找不到任何人说这是,所以我想确定.如果您同意,请告诉我,如果是,为什么.理想情况下是指向纸张的链接,或者,如果您不同意,则为反例.

我们G是一个有向图有一些负面的边缘.我们想要运行A*G.

首先,如果G从源头到达并且达到目标的负周期,则没有可接受的启发式,因为不可能低估达到目标的成本,因为它是-?.

但是,如果没有这样的循环,可能会有一些可接受的启发式.特别是,所有负边缘的总和将始终低估达到目标的成本.

我的印象是,在这种情况下,A*可以正常工作.

PS我可以在图上运行Bellman-Ford,检测负循环,如果没有,重新加权以消除负边缘.但是,如果我知道没有负循环,我可以跳过它并运行A*.

这是非常错误的.顶点的成本是启发式和到目前为止构建的路径的总和......而启发式低估了达到目标的成本,启发式和到目前为止所采用的路径的总和可能不是.千里马culpa.

似乎用一个低估了达到目标的成本的函数对开放集进行排序,而通过一个给定的顶点可能会工作......如果一个人使用<sum of negative edges in the graph>这样的函数,它看起来像退化为图遍历.

注意:由于旅行不是在它开始的同一个地方结束的事实,而且只要我仍然访问所有这些点,每个点都可以被访问多次这一事实,这不是真正的TSP变体,而是我之所以说是因为缺乏对问题的更好定义.

所以..

假设我正在徒步旅行,有n个兴趣点.这些景点都通过远足径相连.我有一张地图显示了所有距离的路径,给我一个有向图.

我的问题是如何近似一个从A点开始并且访问所有n个兴趣点的旅游,同时结束旅行的任何地方,但我开始的点,我希望旅游尽可能短.

由于远足的性质,我认为这可能不是一个对称问题(或者我可以将我的不对称图转换为对称图？),因为从高海拔到低海拔显然比其他方式更容易.

另外我认为它必须是一种适用于非度量图的算法,其中不满足三角不等式,因为从a到b到c可能比从a到c的真正漫长而奇怪的道路更快直.我确实考虑过三角不等式是否仍然存在,因为对于我访问每个点的次数没有限制,只要我访问所有这些,这意味着我总是选择从a到c的两条不同路径中最短的路径,从而永远不会抓住漫长而奇怪的道路.

我相信我的问题比TSP更容易,因此这些算法不适合这个问题.我考虑过使用最小生成树,但我很难说服自己可以将它们应用于非度量非对称有向图.

我真正想要的是关于如何能够提出近似算法的一些指示,该算法将通过所有n个点找到近乎最佳的旅行