मैं इस 3D इंटरफ़ेस में दो नोड्स के बीच सबसे छोटा पथ प्राप्त करने के लिए दिज्क्स्ट्रा एल्गोरिथम को लागू करना चाहता हूं। पहले मैंने दिज्क्स्ट्रा एल्गोरिथम में ग्राफ का उपयोग करके 2डी सतह में काम किया था। लेकिन इस बार मैं अटक गया। एक अंतिम समाधान की तलाश में। स्टार नोड मेरा गंतव्य नोड है और बाकी में से कोई भी स्रोत नोड हो सकता है।

Nodes in 3D model

इन नोड्स की स्थिति का अनुमान निम्नलिखित कोड द्वारा लगाया गया था।

import numpy as np
import matplotlib.pyplot as plt

n = 50

x1, x2 = 0.1, 0.5
y1, y2 = 0.1, 0.5
z1, z2 = 0.1, 0.5

xs = (x2 - x1)*np.random.rand(n) + x1
ys = (y2 - y1)*np.random.rand(n) + y1
zs = (z2 - z1)*np.random.rand(n) + z1

xs1 = (x2 - x1)*np.random.rand(n) + x1
ys1 = (y2 - y1)*np.random.rand(n) + y1
zs1 = (z2 - z1)*np.random.rand(n) + z1

fig = plt.figure()
ax = fig.add_subplot(111,projection='3d')

for i in range(n):
    if zs[i] == max(zs):
        ax.plot(xs[i], ys[i], zs[i], "k*")
    else:
        ax.plot(xs[i], ys[i], zs[i], "go")

ax.set_xlabel('X Label')
ax.set_ylabel('Y Label')
ax.set_zlabel('Z Label')

plt.show()

नोड्स के बीच की दूरी का अनुमान लगाने के लिए:

def distance(p1,p2):
    squared_dist = np.sum((p1-p2)**2, axis=0)
    dist = np.sqrt(squared_dist)
    return dist

graph = []

for i in range(len(xs)):
    graph.append([])
    for j in range(len(xs)):
        p1 = np.array([xs[i], ys[i], zs[i]])
        p2 = np.array([xs[j], ys[j], zs[j]])
        graph[i].append(distance(p1,p2))
graph = np.array(graph)
print(graph)

सबसे छोटा रास्ता पाने के लिए दिज्क्स्ट्रा एल्गोरिथम

M = []
class DijkstraAlgoWithPath:
    global M
    
    def minDistance(self, dist, queue):
        minimum = float("Inf")
        min_index = -1
        
        for i in range(len(dist)):
            if dist[i] < minimum and i in queue:
                minimum = dist[i] 
                min_index = i
        return min_index
    
    def printPath(self, parent, j):
        if parent[j] == -1:                 # If 'j' is the source
            print (j+1, end="  ")
            M.append(j+1)
            return 0
        self.printPath(parent, parent[j])   #If 'j' is not the source, call the recursive function
        M.append(j+1)
        print (j+1, end="  ")
        


    def dijkstraWithPath(self, graph, src, des):
        s = src - 1
        row = len(graph)
        col = len(graph[0])
        
        dist = [float('Infinity')] * row    # initializing all distances are inifinity
        parent = [-1] * row                 # The parent array where to store the shortest path tree
        
        dist[s] = 0                         # Distance of source from itself is zero
        
        q = []                              # An empty list to store all vertices in queue
        for i in range(row):
            q.append(i)
        
        # Find the shortest path for all vertices
        while q:
            # Select the minimum distance vertex 
            # from the set of vertices 
            # which are still in the queue
            u = self.minDistance(dist, q)
            q.remove(u)     # Now remove the minimum distance element which already got
            
            # Consider the vertices which are still in the queue,
            # update the distance and parent index of the adjacent vertices
            # which are selected 
            for i in range(col):
                if graph[u][i] and i in q:  # If dist[i] in the queue
                    if dist[u] + graph[u][i] < dist[i]: # and if the total weight of path from source to destination is less than the current value of dist[i]
                        dist[i] = dist[u] + graph[u][i]
                        parent[i] = u
        self.printPath(parent, des-1)
        

def main():
    global graph
    
    x = DijkstraAlgoWithPath()
    source = 5   # Take input of the source value
    des = 41
    x.dijkstraWithPath(graph, source, des)
    
if __name__ == '__main__':
    main()
0
Md Mizanur Rahman Mustakim 14 जिंदा 2021, 11:44
जब आप अपने कोड का उपयोग करते हैं तो क्या होता है? क्या आपको त्रुटि मिलती है?
 – 
Hans
14 जिंदा 2021, 11:55
यह मुझे स्रोत और गंतव्य के बीच अन्य नोड्स नहीं दिखाता है। उदाहरण के लिए: जब मैं स्रोत नोड को 1 के रूप में दर्ज करता हूं, तो आउटपुट आया: 1 44 लेकिन यह उचित पथ नहीं है। इसमें उनके बीच अन्य नोड्स शामिल नहीं थे।
 – 
Md Mizanur Rahman Mustakim
14 जिंदा 2021, 12:03
2
क्या एल्गोरिदम सिर्फ शुरुआती और समाप्ति नोड को आउटपुट कर रहा है? प्रारंभ से अंत तक एक सीधी रेखा स्पष्ट रूप से सबसे छोटा मार्ग है जब तक कि कुछ बाधाएं न हों जो मुझे दिखाई नहीं दे रही हैं।
 – 
big_bad_bison
14 जिंदा 2021, 12:25

1 उत्तर

सबसे बढ़िया उत्तर

बहुत ही रोचक समस्या।

डिजस्ट्रा एल्गोरिथम का उपयोग करने के लिए आपको ग्राफ़ में कुछ किनारों को परिभाषित करने की आवश्यकता हो सकती है। अन्यथा (नोटों की प्रत्येक जोड़ी में यूक्लिडियन दूरी के साथ एक किनारा होता है), तो सीधी रेखा सबसे छोटा रास्ता होना चाहिए।

यह समस्या मोशन प्लानिंग से जुड़ी है। यह एनपी-हार्ड है।

जे. कैनी और जे.एच. रीफ, रोबोट मोशन प्लानिंग समस्याओं के लिए नई निचली बाउंड तकनीक, प्रोक। 28 वें अन्नू। आईईईई संगोष्ठी। मिला। संगणना। विज्ञान।, 1987, पीपी। 49-60।

2
Syscall 7 अप्रैल 2021, 09:44
आपकी बहुमूल्य प्रतिक्रिया के लिए बहुत-बहुत धन्यवाद। मैंने अपनी समस्या पहले ही हल कर ली है। मैंने इस समस्या को हल करने के लिए एक पायथन पैकेज बनाया है। काम की जांच के लिए आप डिजस्ट्रा एल्गोरिथम पर जा सकते हैं।
 – 
Md Mizanur Rahman Mustakim
12 अप्रैल 2021, 00:44