1

以下のように作成された簡単なグラフがあります

class Job():
    def __init__(self, name, weight):
        self.name = name
        self.weight = weight
        self.depends = []

    def add_dependent(self, dependent):
        self.depends.append(dependent)


jobA = Job('A', 0)
jobB = Job('B', 4)
jobC = Job('C', 2)
jobD = Job('D', 10)
jobE = Job('E', 3)
jobF = Job('F', 11)

jobA.add_dependent(jobB)
jobA.add_dependent(jobC)
jobB.add_dependent(jobD)
jobC.add_dependent(jobE)
jobD.add_dependent(jobF)
jobE.add_dependent(jobF)

したがって、2つの可能なパスがあります

A->B->D->F  0+4+10+11 = 25
A->C->E->F  0+2+3+11 = 16

したがって、最長のパスは前者になります

最長パスを簡単に収集する方法はありA->B->D->Fますか?

def longest_path(root):
    paths = []
    # some logic here
    return paths

print longest_path(jobA) # should print A->B->D->F
4

2 に答える 2

2

最も効率的な解決策ではありませんが、これは機能するはずです。

import operator

def longest_path(root):
    def _find_longest(job):
        costs = [_find_longest(depend) for depend in job.depends]
        if costs:
            # Find most expensive:
            path, cost = max(costs, key=operator.itemgetter(1))
            return ([job.name] + path, job.weight + cost)
        else:
            return ([job.name], job.weight)
    return "->".join(_find_longest(root)[0])
于 2016-10-18T11:16:45.643 に答える
1

OO ソリューションを使用すると、最も重いパスのみを格納する方法を簡単に提供できます。これは私が思いついた解決策です - 呼び出し可能なクラスを使用して

In [111]: class Heaviest(object):
     ...:     def __init__(self, job):
     ...:         self.path = ''
     ...:         self.weight = 0
     ...:         self.job = job
     ...:     def _find_heaviest(self, job, path='', weight=0):
     ...:         path += job.name
     ...:         weight += job.weight
     ...:         if not job.depends:
     ...:             if weight > self.weight:
     ...:                 self.weight = weight
     ...:                 self.path = path
     ...:         else:
     ...:             for job in job.depends:
     ...:                 self._find_heaviest(job, path, weight)
     ...:     def __call__(self):
     ...:         self._find_heaviest(self.job)
     ...:         return '->'.join(list(self.path)), self.weight
     ...:                 

In [112]: Heaviest(jobA)()
Out[112]: ('A->B->D->F', 25)

後付け:

昨夜、循環依存の場合（私のコメントを参照）、上記の解決策では答えが得られず、再帰の深さが最大に達したときに例外で停止することがわかりました。以下の行を追加するだけで、このアルゴリズムだけでなく、ツリートラバースアルゴリズムが壊れます。

In [226]: jobF.add_dependent(jobA)

In [227]: Heaviest(jobA)()
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
<ipython-input-227-94e994624b4e> in <module>()
----> 1 Heaviest(jobA)()

<ipython-input-111-1ff9f69480a9> in __call__(self)
     15                 self._find_heaviest(job, path, weight)
     16     def __call__(self):
---> 17         self._find_heaviest(self.job)
     18         return '->'.join(list(self.path)), self.weight
     19 

<ipython-input-111-1ff9f69480a9> in _find_heaviest(self, job, path, weight)
     13         else:
     14             for job in job.depends:
---> 15                 self._find_heaviest(job, path, weight)
     16     def __call__(self):
     17         self._find_heaviest(self.job)

... last 1 frames repeated, from the frame below ...

<ipython-input-111-1ff9f69480a9> in _find_heaviest(self, job, path, weight)
     13         else:
     14             for job in job.depends:
---> 15                 self._find_heaviest(job, path, weight)
     16     def __call__(self):
     17         self._find_heaviest(self.job)

RuntimeError: maximum recursion depth exceeded

実装の修正はお任せしますが、必要に応じて、簡単なセーフガードで修正できます

def _find_heaviest(self, job, path='', weight=0):
    if not job.name in path:
        path += job.name
        weight += job.weight
        stop_search = not job.depends
    else:
        stop_search = True
    if stop_search:
        if weight > self.weight:

.....

問題が解決しました

In [230]: Heaviest(jobA)()
Out[230]: ('A->B->D->F', 25)
于 2016-10-18T12:55:37.357 に答える