jjzjj

algorithm - 递归旅行推销员喜欢在 go 中计算

coder 2024-07-09 原文

我有一个函数有点类似于我试图递归的旅行商问题。我认为它正在工作，但我在让附加功能在大型数据集上正常工作时遇到了一些麻烦。这就是我所拥有的……main 应该写成递归的，这样我就可以调用可变数量的递归……https://play.golang.org/p/Lz8arHybFr 

package main

type Foo struct {
    StartPoint string
    EndPoint string 
    distance int
}

func (f *Foo) Connects(endFoo *Foo) bool {
    return f.EndPoint == endFoo.StartPoint
}

func (f *Foo) Completes(endFoo *Foo) bool {
    return f.StartPoint == endFoo.EndPoint
}

var fl = []*Foo{
    // many foo in here
}

func main() {

    completeList := [][]*Foo{}

    for _, first := range fl {
        for _, second := range fl {
            if second.Connects(first) {
                if second.Completes(first) {
                    l := []*Foo{
                        first, second,
                    }
                    completeList = append(completeList, l)
                }

                //if the connection is made, but not complete, keep going
                for _, third := range fl {
                    if third.Connects(second) {
                        if first.Completes(third) {
                            l := []*Foo{
                                first, second, third,
                            }
                            completeList = append(completeList, l)
                        }
                    }
                }
            }
        }
    }

}

最佳答案

我提出了 2 个递归，请检查您的数据: (我想你会把它并行化，所以使用 2 次递归会更容易，就像 go rec2(...) 一样)

func main() {
    rec(0,0)
}

func rec(a, b int) {
    if a >= len(fl) || b >= len(fl) || a == b {
        return
    }
    aa, bb := fl[a], fl[b]
    if !aa.Connects(bb) {
        rec(a, b+1)
        return
    }
    l := []*Foo{
        aa, bb,
    }
    completeList = append(completeList, l)

    rec2(0, a, b)
}

func rec2(c, a, b int) {
    if c >= len(fl) || a == c || b == c {
        return
    }
    cc, aa, bb := fl[c], fl[a], fl[b]
    if cc.Connects(bb) && aa.Completes(cc) {
         l := []*Foo{
              aa, bb, cc,
         }
         completeList = append(completeList, l)
    }
    rec2(c+1, a, b)
}

关于algorithm - 递归旅行推销员喜欢在 go 中计算，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44732016/

中计algorithmcompleteListsectionFoorecursiongo

有关algorithm - 递归旅行推销员喜欢在 go 中计算的更多相关文章

  1. ruby - 递归地将所有数字字符串转换为 Ruby 哈希中的整数 - 2

    我有一个随机大小的散列，它可能有类似"100"的值，我想将其转换为整数。我知道我可以使用value.to_iifvalue.to_i.to_s==value来做到这一点，但我不确定我将如何在我的散列中递归地做到这一点，考虑到一个值可以是一个字符串，或一个数组(哈希或字符串)，或另一个哈希。 最佳答案 这是一个非常简单的递归实现(尽管必须同时处理数组和散列会增加一些技巧)。deffixnumifyobjifobj.respond_to?:to_i#IfwecancastittoaFixnum,doit.obj.to_ielsifobj

  2. Ruby:标准递归模式 - 2

    我经常迷上ruby​​的一件事是递归模式。例如，假设我有一个数组，它可能包含无限深度的数组作为元素。所以，例如:my_array=[1,[2,3,[4,5,[6,7]]]]我想创建一个方法，可以将数组展平为[1,2,3,4,5,6,7]。我知道.flatten可以完成这项工作，但这个问题是作为我经常遇到的递归问题的一个例子-因此我试图找到一个更可重用的解决方案。简而言之-我猜这种事情有一个标准模式，但我想不出任何特别优雅的东西。任何想法表示赞赏 最佳答案 递归是一种方法，它不依赖于语言。您在编写算法时要考虑两种情况:再次调用函数的情

  3. ruby - 为什么我用递归得到 "stack level too deep"？ - 2

    我有这个ruby代码:defget_sumnreturn0ifn似乎正在为999之前的值工作。当我尝试9999时，它给了我这个:stackleveltoodeep(SystemStackError)所以，我添加了这个:RubyVM::InstructionSequence.compile_option={:tailcall_optimization=>true,:trace_instruction=>false}但什么也没发生。我的ruby版本是:ruby1.9.3p392(2013-02-22revision39386)[x86_64-darwin12.2.1]我还增加了机器的堆栈大

  4. ruby - 构建网络蜘蛛时，应该使用递归吗？ - 2

    构建一个深度优先的网络蜘蛛，这意味着它将访问第一页上的所有链接，然后转到每个链接，并访问所有第二页上的链接...你应该使用递归吗？我发现这是CPU密集型的。defrecursion()linkz_on_first_page.eachdo|link|recursion(link)endendrecursion(firstpage) 最佳答案 绝对不是，由于万维网的实际性质，您很快就会遇到问题。当您访问带有主导航部分的网站时，每个页面都链接到其他页面，您就进入了一个无限循环。您可以跟踪您处理了哪些链接，但即便如此，递归循环并不真正适合万

  5. ruby-on-rails - 如何以递归方式将 YAML 文件扁平化为 JSON 对象，其中键是点分隔的字符串？ - 2

    例如，如果我有YAML文件en:questions:new:'NewQuestion'other:recent:'Recent'old:'Old'这最终会变成一个json对象，例如{'questions.new':'NewQuestion','questions.other.recent':'Recent','questions.other.old':'Old'} 最佳答案 由于问题是关于在Rails应用程序上使用YAML文件进行i18n，因此值得注意i18ngem提供了一个辅助模块I18n::Backend::Flatten完全像

  6. ruby-on-rails - Textmate 'Go to symbol' 相当于 Vim - 2

    在Railcasts上，我注意到一个非常有趣的功能“转到符号”窗口。它像Command-T一样工作，但显示当前文件中可用的类和方法。如何在vim中获取它？ 最佳答案 尝试:helptags有各种程序和脚本可以生成标记文件。此外，标记文件格式非常简单，因此很容易将sed(1)或类似的脚本组合在一起，无论您使用何种语言，它们都可以生成标记文件。轻松获取标记文件(除了下载生成器之外)的关键在于格式化样式而不是实际解析语法。 关于ruby-on-rails-Textmate'Gotosymbol

  7. ruby - 为什么尾递归 gcd 比 rubinius 的 while 循环更快 - 2

    我有这两个gcd函数的实现:defgcd1(a,b)ifa==baelsifa>bif(a%b)==0belsegcd1(a%b,b)endelseif(b%a)==0aelsegcd1(a,b%a)endendenddefgcd2(a,b)if(a==b)returnaelsifb>amin,max=a,belsemin,max=b,aendwhile(max%min)!=0min,max=max%min,minendminend函数gcd1是尾递归的，而gcd2使用while循环。我已经验证rubinius通过对阶乘函数进行基准测试来执行TCO，只有阶乘函数基准测试显示递归版本和迭

  8. ruby-on-rails - 为什么我的 helper 递归方法不返回每个值？ - 2

    我想显示一个由gem祖先管理的类别树。我想使用一个助手，它会递归地遍历树并一个一个地返回类别，暂时没有html标签或内容。moduleCategoriesHelperdefdisplay_tree(category)ifcategory.has_children?category.children.eachdo|sub_category|display_tree(sub_category)puts(sub_category.name)#tocheckifitgoeshereendendcategory.nameendendcategory参数是根类别之一。它应该返回什么？在网页中:它仅

  9. ruby - 如何处理树顶左递归 - 2

    我有一个grammarfile对于我正在尝试构建的一种新的通用编程语言。我正在努力使该语言健壮且易于使用(它深受Ruby等启发)，为此我引入了一些左递归规则。我看到一些例子似乎表明了以下左递归规则:rulel_recursel_recurse/'somethingelse'end可以通过将其更改为非左递归:ruler_recurse'somethingelse'/r_recurseend对我来说，这看起来会有不同的问题并且仍然会失败。我是对的，还是这会“奏效”？我试图(查找和)消除的特定左递归可以在这个grammarfile中找到.我不确定哪些规则受到影响，但至少somewerepoi

  10. ruby - 如何递归 rake ？ -- 或合适的替代品 - 2

    我希望我的项目的顶级Rakefile使用树中更深的rakefile来构建东西；即顶层rakefile说明如何构建项目(大图)，而较低层的rakefile说明如何构建特定模块(本map片)。当然有一组共享的配置，用于在任务之间共享时执行的详细信息:所以它主要是关于保持对需要构建的内容的描述，尽可能接近正在构建的源。例如。/Source/Module/code.foo和cie应该使用/Source/Module/Rakefile中的指令构建；并且/Rakefile了解模块之间的依赖关系。我不关心它是否使用多个rake进程(ala递归make)，或者只是创建单独的构建环境。无论哪种方式，它都

随机推荐