0

Dijkstra のアルゴリズムを Python で実装する必要があります。ただし、先行情報、長さ、未訪問/訪問の 3 つの情報を保持するには、2D 配列を使用する必要があります。私は C で Struct を使用できることを知っていますが、Python で同様のことを行う方法にこだわっていますが、可能であると言われていますが、正直に言うとわかりません

4

5 に答える 5

2

そのためのクラスを作成します。

class XXX(object):
    def __init__(self, predecessor, length, visited):
        self.predecessor = predecessor
        self.length = length
        self.visited = visited

または、collections.namedtuple を使用します。これは、構造体のような複合型を保持するのに特にクールですが、独自の動作はありませんが名前付きメンバー:XXX = collections.namedtuple('XXX', 'predecessor length visited')です。

で作成しますXXX(predecessor, length, visited)。

于 2011-02-10T20:25:41.417 に答える
1

その情報を Python オブジェクトにカプセル化すれば問題ありません。

于 2011-02-10T20:23:02.400 に答える
1

前述のように、オブジェクトのインスタンスを使用できます。

この著者は、Python での Dijkstras のかなり説得力のある Python 実装を持っています。

#
# This file contains the Python code from Program 16.16 of
# "Data Structures and Algorithms
# with Object-Oriented Design Patterns in Python"
# by Bruno R. Preiss.
#
# Copyright (c) 2003 by Bruno R. Preiss, P.Eng.  All rights reserved.
#
# http://www.brpreiss.com/books/opus7/programs/pgm16_16.txt
#
class Algorithms(object):

    def DijkstrasAlgorithm(g, s):
        n = g.numberOfVertices
        table = Array(n)
        for v in xrange(n):
            table[v] = Algorithms.Entry()
        table[s].distance = 0
        queue = BinaryHeap(g.numberOfEdges)
        queue.enqueue(Association(0, g[s]))
        while not queue.isEmpty:
            assoc = queue.dequeueMin()
            v0 = assoc.value
            if not table[v0.number].known:
                table[v0.number].known = True
                for e in v0.emanatingEdges:
                    v1 = e.mateOf(v0)
                    d = table[v0.number].distance + e.weight
                    if table[v1.number].distance > d:

                        table[v1.number].distance = d
                        table[v1.number].predecessor = v0.number
                        queue.enqueue(Association(d, v1))
        result = DigraphAsLists(n)
        for v in xrange(n):
            result.addVertex(v, table[v].distance)
        for v in xrange(n):
            if v != s:
                result.addEdge(v, table[v].predecessor)
        return result
    DijkstrasAlgorithm = staticmethod(DijkstrasAlgorithm)

これらの情報は、Algorithms.Entry() を呼び出して構築しているオブジェクトに「保持」されていることに注意してください。エントリはクラスであり、次のように定義されます。

class Entry(object):
    """
    Data structure used in Dijkstra's and Prim's algorithms.
    """

    def __init__(self):
        """
        (Algorithms.Entry) -> None
        Constructor.
        """
        self.known = False
        self.distance = sys.maxint
        self.predecessor = sys.maxint

self.known、self.distance... はそれらの情報です。彼はこれらをコンストラクター ( init )で明示的に設定せず、後で設定します。Python では、ドット表記で属性にアクセスできます。例: myObject= Entry()。myObject.known、myObject.distance... それらはすべて公開されています。

于 2011-02-10T20:57:13.740 に答える
1

または、単純に 2 次元配列内でタプルまたは辞書を使用することもできます。

width=10
height=10

my2darray = []
for x in range(width):
   my2darray[x]=[]

for x in range(width):
   for y in range(height):
      #here you set the tuple
      my2darray[x][y] = (n,l,v) 
      #or you can use a dict..
      my2darray[x][y] = dict(node=foo,length=12,visited=False)
于 2011-02-10T20:29:52.780 に答える
0

Python はオブジェクト指向言語です。C の構造体から C++ のクラスに移行するようなものだと考えてください。Python でも同じクラス構造を使用できます。

于 2011-02-10T20:29:44.597 に答える