Yam Code

New Paste Browse

def IDS(self,start,end):  
        f = open("output.txt",'w')
        if (start == end):
            f.write(start)
            f.write('\n')
            f.write(end)
            f.close()
            return
 
        queue = PriorityQueue()               # list of return path           
        level = 0       # incremnetal level
        
        while (True):
            path  = []
            expanded = []     # list of expanded states
            discovered = [False] * (len(self.matrix)-1)  
             #keep track of any visted vertices
            discovered[start] = True
 
            depth = 0 # the depth of current node, if higher than level, it will stop exploring
            queue.put((depth,[start]))
            
            while queue.empty() == False:                
                # add lastest node from to queue path and expanded
                #because we backtrack so we do not add old node to path
                depth, path = queue.get()
                        
                v = path[len(path)-1]       # last node in path is the node ready to explore neighbor
                expanded.append(v)
                discovered[v] = True
                    
                if (v == end):
                    for x in expanded:
                        f.write(str(x))
                        f.write(' ')
                    f.write('\n')
                    for x in path:
                       f.write(str(x))
                       f.write(' ')
                    f.close()
                    return
                
 
                for i in range(len(self.matrix)-1):
                    if (self.matrix[v][i] != 0 and i != path[len(path)-2]): # basically prevent the current node go backward, for ex: 0 -> 1, then 1 cannot go back to 0
                                                                                    # but 0 -> 1 -> 4, 4 cannot go back to 1 but 4 can go back to 0
                        totalDepth = depth - 1     # we do reversed logic here, because priority queue pop out the one with lowest priority.
                        # reversed logic, all depth in queue is in negative number
                         # reversed logic is applied to make sure the path with highest depth go DFS because queue contains many path
                        # and priority queue just pop out the one with lowest priority first
                                            #for instance: queue has [(-2,[0,2,4]),(0,[0]),(-1,[0,1])], it will pop out the [0,2,4] then go DFS, if not we will do BFS instead
                        if (abs(totalDepth) <= level):                  
                            tmp = path[:]
                            tmp.append(i)
                            queue.put((totalDepth,tmp))
            level +=1
            queue.queue.clear()
            for x in expanded:
                f.write(str(x))
                f.write(' ')
            f.write('\n')
            if  (level > len(self.matrix)-1): # maximum depth can be explored lower than level, because we increase level but exceed maximum depth meaning no more can be explored
                f.write("No path.")
                return
 
        f.close()

Paste Settings

Paste Title : [Optional]

Paste Folder : [Optional]

Syntax Highlighting : [Optional]

Paste Expiration : [Optional]

Paste Status : [Optional]

Password : [Optional]

Description: [Optional]

Tags: [Optional]

Encrypt Paste (?)

You are currently not logged in, this means you can not edit or delete anything you paste. Sign Up or Login

Paste Settings

Site Languages