使用贪心算法在有向图中查找至少包含K个节点的路径，给定起始节点。

Question

我有一个非加权DAG图。我想要以贪心的方式找到所有路径，并且这些路径应该至少包含K个节点和给定的起始节点。

是否存在任何现有的算法/实现可以做到这一点？

例如，我有以下图形：

my %graph =(36=>[31],31=>[30,22],30=>[20],22=>[20,8],20=>[1],8=>[5],5=>[2],2=>[1,20]);

如果我定义K=5并从起始节点36开始，我希望得到：

{1,20,22,31,36}
{1,20,2,5,8,22,31,36}
{1,20,30,31,36}
{1,2,5,8,22,31,36}

- neversaint

---

看起来这样的路径数量可能会随着节点数量呈指数增长。你会如何处理？ - Leonid

@Leonid：我将使用启发式方法来完成，例如根据某些条件（领域特定）删除特定节点。 - neversaint

回溯法是否不能解决你的问题？我会看一下更快的方法，考虑用动态规划的方式思考问题，根据特定的领域条件进行应用。如果没有这些条件，似乎没有比回溯更好的选择。 - Leonid

Answer 1

这并不是很难。

use warnings;
use strict;
use Data::Dumper;

my @stack = ();

my %graph = (36=>[31],31=>[30,22],30=>[20],22=>[20,8],
             20=>[1],8=>[5],5=>[2],2=>[1,20]);

# add begin to stack
push(@stack, { node => 36, way => [36] });

while (@stack > 0) {

    my $node = pop(@stack);

    # way
    my $way = $node->{way};

    # complete way
    if ($node->{node} == 1) {
        print Dumper($node->{way});
    }

    # add next nodes
    my $nextArr = $graph{$node->{node}};

    for my $nextNod (@$nextArr) {
        # add way
        my @tmpWay = @$way;
        push(@tmpWay, $nextNod);

        # add to stack
        push(@stack, { node => $nextNod, way => \@tmpWay });
    }
}

所以你可以测试，如果节点是终点并保存所有路径（方式）。

你必须优化这个脚本

编辑

添加无尽保存保护。

编辑2

你不需要无尽的保护。添加shift到pop，然后你可以搜索多种方式来结束注释 :)

- xGhost

---

谢谢，我遇到了输出问题。你的这两行代码出现了错误信息："push(@stack, { node => 36, way => [36] })" 和 "while (@#stack > 0) {"。请给予建议。 - neversaint

代码现在可以运行了。之前只是伪代码，但我已经为你修复了它...希望我没有帮你完成作业。 - xGhost