फ्लोयड-वॉरसॉल पथ पुनर्निर्माण

Question

नीचे फ़्लॉइड-वॉर्सहॉल एल्गोरिदम के लिए कार्यान्वयन है, जो किसी दिए गए भारित ग्राफ के लिए सभी जोड़े सबसे छोटे पथों को ढूंढता है।

फ़ंक्शन floyd_warshallइनपुट के रूप में एक ग्राफ लेता है, जिसे [ स्रोत , गंतव्य , वजन ] के रूप में एक किनारे सूची द्वारा दर्शाया जाता है।

path_reconstructionसमारोह प्रत्येक शिखर कि हर दूसरे शिखर से जुड़ा है से कम से कम पथ आउटपुट।

कृपया किसी भी प्रकार के सुधार के लिए सुझाव दें।

import sys

INF = sys.maxsize

def floyd_warshall(graph):
    source_vertices = [column[0] for column in graph]
    destination_vertices = [column[1] for column in graph]
    vertices = list(set(source_vertices) | set(destination_vertices))

    distance = [[INF] * len(vertices) for i in range(len(vertices))]
    next_vertices  = [[0]   * len(vertices) for i in range(len(vertices))]

    for i in range(len(vertices)):
        distance[i][i] = 0
    for source, destination, weight in graph:
        distance[source-1][destination-1] = weight
        next_vertices[source-1][destination-1] = destination-1

    for k in range(len(vertices)):
        for i in range(len(vertices)):
            for j in range(len(vertices)):
                if distance[i][j] > distance[i][k] + distance[k][j]:
                    distance[i][j] = distance[i][k] + distance[k][j]
                    next_vertices[i][j]  = next_vertices[i][k]

    path_reconstruction(distance, next_vertices)

def path_reconstruction(dist, nxt):
    print("Edge \t\t Distance \t Shortest Path")
    for i in range(len(dist)):
        for j in range(len(dist)):
            if i != j:
                path = [i]
                while path[-1] != j:
                    path.append(nxt[path[-1]][j])
                print("(%d, %d) \t\t %2d \t\t %s"
                      % (i + 1, j + 1, dist[i][j], ' - '.join(str(p + 1) for p in path)))
    print()

def main():
    edge_list1 = [
        [1, 3, -2],
        [2, 1, 4],
        [2, 3, 3],
        [3, 4, 2],
        [4, 2, -1]
    ]
    edge_list2 = [
        [1, 2, 10],
        [1, 3, 20],
        [1, 4, 30],
        [2, 6, 7],
        [3, 6, 5],
        [4, 5, 10],
        [5, 1, 2],
        [5, 6, 4],
        [6, 2, 5],
        [6, 3, 7],
        [6, 5, 6]
    ]

    floyd_warshall(edge_list1)
    floyd_warshall(edge_list2)

if __name__ == '__main__':
    main()

Answer 1

FMc ने कुछ बेहतरीन अंक बनाए हैं। मैं उन लोगों को नहीं दोहराने की कोशिश करूंगा।

कार्यक्षेत्र

आप का उपयोग कर कोने की सूची निर्धारित करते हैं:

    source_vertices = [column[0] for column in graph]
    destination_vertices = [column[1] for column in graph]
    vertices = list(set(source_vertices) | set(destination_vertices))

और फिर बार len(vertices)- बार अपने कोड का उपयोग करें।

FMc का उपयोग करने का सुझाव देता है:

    vertices = set(col[i] for col in graph for i in (0, 1))
    n = len(vertices)

दोनों कार्यान्वयन सभी वर्टिकल का कवर बनाने के लिए सेट का उपयोग करते हैं। लेकिन यह वास्तव में कोई मतलब नहीं है। आप range(len(vertices))सूचकांकों को निर्धारित करने के लिए उपयोग कर रहे हैं । यदि रेखांकन 1, 2, 4, और 5 का उपयोग करता है तो क्या होगा? आपका सेट हो जाएगा {1, 2, 4, 5}, सेट की लंबाई है 4, और range(4)पैदा करता सूचकांक 0, 1, 2, और 3। लेकिन आप निष्पादित करें:

    for source, destination, weight in graph:
        distance[source-1][destination-1] = weight

आप पाते हैं sourceया destinationहै 5, गणना घटाना 1, सूचकांक 4 पाने के लिए, और आप मैट्रिक्स के अंत से गिर गया है लगता है!

जाहिर है, वहाँ एक आवश्यकता है कि से सभी सूचकांकों है 1करने के लिए N, इस्तेमाल किया जाना चाहिए कोई अंतराल के साथ अनुमति दी। लेकिन फिर, आपको एक सेट की आवश्यकता नहीं है। आपको केवल अधिकतम सूचकांक खोजने की आवश्यकता है।

    n = max(edge[col] for edge in graph for col in (0, 1))

अनुक्रमण धीमा है

इस कोड में, 100 कोने के लिए, कितनी बार distance[i]मूल्यांकन किया जाता है? कैसे के बारे में distance[k]?

    for k in range(len(vertices)):
        for i in range(len(vertices)):
            for j in range(len(vertices)):
                if distance[i][j] > distance[i][k] + distance[k][j]:
                    distance[i][j] = distance[i][k] + distance[k][j]
                    next_vertices[i][j]  = next_vertices[i][k]

distance[i]कहीं 2000000 और 4000000 बार के बीच देखा जाता है? अत्यधिक लगता है, शायद? distance[k]1000000 और 2000000 बार के बीच देखा जाता है। एक मूत थोड़ा कम, लेकिन अभी भी काफी कुछ।

एक बार जब आप पहला forलूप दर्ज कर लेते हैं k, तो उस पुनरावृत्ति के लिए एक स्थिरांक होता है। आप distance[k]एक बार देख सकते हैं । इसी तरह, एक बार जब आप दूसरे forलूप में प्रवेश करते हैं , iतो उस पुनरावृत्ति के लिए एक स्थिर है। आप distance[i]एक बार देख सकते हैं ।

    for k in range(len(vertices)):
        distance_k = distance[k]
        for i in range(len(vertices)):
            distance_i = distance[i]
            for j in range(len(vertices)):
                if distance_i[j] > distance_i[k] + distance_k[j]:
                    distance_i[j] = distance_i[k] + distance_k[j]
                    next_vertices[i][j]  = next_vertices[i][k]

अब, दूरी को देख रहे थे [k] केवल १०० बार, और दूरी [i] केवल १०००० बार। यह एक गति में सुधार होगा।

हम लूप के लिए बेहतर कार्य कर सकते हैं: सूचकांकों को प्राप्त करना और मूल्यों को एक साथ enumerateदेखना , उपयोग करना , और distanceमैट्रिक्स की पंक्तियों पर लूपिंग करना :

    for k, distance_k in enumerate(distance):
        for i, distance_i in enumerate(distance):
            for j in range(len(vertices)):
                if distance_i[j] > distance_i[k] + distance_k[j]:
                    distance_i[j] = distance_i[k] + distance_k[j]
                    next_vertices[i][j]  = next_vertices[i][k]

फिर से, distance_i[k]आंतरिक लूप में नहीं बदलता है, इसलिए हम इसे मध्य लूप में एक बार देख सकते हैं:

    for k, distance_k in enumerate(distance):
        for i, distance_i in enumerate(distance):
            dist_ik = distance_i[k]
            for j in range(len(vertices)):
                dist_ik_kj = dist_ik + distance_k[j]
                if distance_i[j] > dist_ik_kj:
                    distance_i[j] = dist_ik_kj 
                    next_vertices[i][j]  = next_vertices[i][k]

अंत में, हम distance_kमैट्रिक्स की पंक्ति पर पुनरावृति कर सकते हैं , अतिरिक्त लुकअप ओवरहेड्स से बचने के लिए:

    for k, distance_k in enumerate(distance):
        for i, distance_i in enumerate(distance):
            dist_ik = distance_i[k]
            for j, dist_kj in enumerate(distance_k):
                dist_ik_kj = dist_ik + dist_kj
                if distance_i[j] > dist_ik_kj:
                    distance_i[j] = dist_ik_kj 
                    next_vertices[i][j]  = next_vertices[i][k]

दोनों next_vertices[i]और next_vertices[i][k]भीतरी पाश में लगातार कर रहे हैं; हम अतिरिक्त बचत के लिए, मध्य पाश में एक बार उन्हें देख सकते हैं। आप बयान में भी zip distanceऔर next_verticesसाथ में भी और for i, ...दोनों distance_iको next_vertices_iएक साथ देख सकते हैं। लेकिन शायद यह थोड़ा उन्नत हो रहा है।

याद

पायथन लिस्ट मेमोरी हॉग हैं। इससे कोई फर्क नहीं पड़ता कि आपके ग्राफ़ में कुछ सौ से अधिक कोने नहीं हैं। लेकिन यदि आप बड़े रेखांकन (हज़ारों की संख्या में? सैकड़ों हज़ारों की संख्या में) का समर्थन करना चाहते हैं, तो आप मेमोरी कुशल संरचनाओं का उपयोग करना चाहेंगे।

आप numpyअपने NxN distanceऔर next_verticesमैट्रिसेस बनाने के लिए उपयोग कर सकते हैं । लेकिन अगर आपने numpyस्थापित नहीं किया है, तो हमें उस स्लेजहेमर का उपयोग करने की आवश्यकता नहीं है। पायथन अधिक मेमोरी कुशल arrayऑब्जेक्ट्स के साथ आता है , जो केवल सूचियों के जैक-ऑफ-ऑल-ट्रेड विषम सूची के बजाय स्केलर जानकारी (पूर्णांक, फ़्लोट्स, वर्ण) संग्रहीत कर सकते हैं।

next_verticesपूर्णांक शीर्ष मानों को पकड़ो। के बजाए:

next_vertices  = [[0]   * len(vertices) for i in range(len(vertices))]

विचार करें:

zeros = [0] * len(vertices)
next_vertices = [array.array('I', zeros) for _ in range(len(vertices))]

बाकी कोड को बदलने की आवश्यकता नहीं होगी। आप अभी भी जैसे डेटा तक पहुंचते हैं next_vertices[i][j]।

यह पूर्णांकों listका निर्माण करता है array, जहां सरणी प्रति तत्व 8 बाइट्स के बजाय मात्र 2 बाइट्स प्रति मान लेता है, साथ ही प्रत्येक पूर्णांक (लगभग 28 बाइट्स प्रत्येक) की भंडारण आवश्यकता भी होती है।

आप distanceमैट्रिक्स के लिए कुछ समान कर सकते हैं । लेकिन अब हमें यह जानना चाहिए: क्या वेट हमेशा पूर्णांक मान हैं, या वे फ्लोटिंग पॉइंट हैं? आप 'd'प्रकार कोड का उपयोग करना चाह सकते हैं , यदि वजन आंशिक हो सकता है। देखें सरणी जानकारी के लिए।

Answer 2

आपका कार्यक्रम यह देखने के लिए एक अच्छा उदाहरण प्रदान करता है कि कैसे कुछ सामान्य तकनीकों के माध्यम से कोड पठनीयता को बढ़ाया जा सकता है: (1) वर्बोज़ पुनरावृत्ति से बचने के लिए सुविधा चर; (2) कोड छोटे पैराग्राफ "पैराग्राफ" या ब्लॉक के रूप में आयोजित; और (3) छोटे चर नाम का उपयोग कोड के दृश्य वजन को हल्का करने के लिए, इस प्रकार पढ़ने और दृश्य स्कैनिंग में आसानी को बढ़ाता है। ध्यान दें कि संक्षिप्त नामों का उपयोग विवेकपूर्ण रूप से किया जाना चाहिए: क्योंकि वे गुप्त हो सकते हैं, लघु संस्करण आम तौर पर या तो प्रोग्राम में लगातार उपयोग किए जाने वाले सम्मेलन से या अन्य प्रासंगिक सुरागों (जैसे, पास के कार्यों या संग्रह से अधिक स्पष्ट नाम और अच्छी तरह से) से उनका अर्थ प्राप्त करते हैं। -प्रकाशित टिप्पणियाँ)। यहाँ floyd_warshall()उन पंक्तियों के साथ एक भारी संपादित संस्करण है । क्योंकि मैं आलसी हूं, इसलिए मैं मान लूंगा कि आपने फ्लोयड-वारशॉल को सही तरीके से लागू किया है।

def floyd_warshall(graph):
    # Collect all vertices.
    vertices = set(
        col[i]
        for col in graph
        for i in (0, 1)
    )
    n = len(vertices)
    rng = range(n)

    # Initialize the distance and next-vertex matrix.
    dists = [
        [0 if i == j else INF for j in rng]
        for i in rng
    ]
    next_vertices = [
        [0 for j in rng]
        for i in rng
    ]

    # Populate the matrixes.
    for src, dst, weight in graph:
        i = src - 1
        j = dst - 1
        dists[i][j] = weight
        next_vertices[i][j] = j

    # Do that Floyd-Warshall thing.
    for k in rng:
        for i in rng:
            for j in rng:
                ikj = dists[i][k] + dists[k][j]
                if dists[i][j] > ikj:
                    dists[i][j] = ikj
                    next_vertices[i][j]  = next_vertices[i][k]

    return path_reconstruction(dists, next_vertices)

एक बड़ा मुद्दा यह है कि आपके floyd_warshall()फ़ंक्शन को ऐसे फ़ंक्शन को कॉल नहीं करना चाहिए जो प्रिंट करता है। बल्कि इसे किसी तरह का सार्थक डेटा वापस करना चाहिए। वह दृष्टिकोण आपके कार्य को अधिक आसानी से परीक्षण योग्य बनाता है। उदाहरण के लिए, path_reconstruction()घोषणापत्रों की सूची वापस कर सकता है।

def path_reconstruction(dists, next_vertices):
    # Same ideas here: return data, don't print; use convenience
    # vars where they help with readability.
    rng = range(len(dists))
    paths = []
    for i in rng:
        for j in rng:
            if i != j:
                path = [i]
                while path[-1] != j:
                    path.append(next_vertices[path[-1]][j])
                paths.append(dict(
                    i = i,
                    j = j,
                    dist = dists[i][j],
                    path = path,
                ))
    return paths

फिर अपने मुद्रण को एल्गोरिथम कोड के बाहर करें।

def main():
    edge_lists = [
        [
            [1, 3, -2],
            [2, 1, 4],
            [2, 3, 3],
            [3, 4, 2],
            [4, 2, -1],
        ],
        [
            [1, 2, 10],
            [1, 3, 20],
            [1, 4, 30],
            [2, 6, 7],
            [3, 6, 5],
            [4, 5, 10],
            [5, 1, 2],
            [5, 6, 4],
            [6, 2, 5],
            [6, 3, 7],
            [6, 5, 6],
        ],
    ]
    for el in edge_lists:
        paths = floyd_warshall(el)
        for p in paths:
            print(p)