पायथन

Question

में लघु पथ एल्गोरिदम के लिए कार्यात्मक समाधान मैं Learn You Some Erlang for Great Good! पढ़ रहा हूं और दिलचस्प पहेली पाई। मैंने इसे पायथन में सबसे कार्यात्मक तरीके से लागू करने का निर्णय लिया।

कृपया मेरे कोड देखें:

def open_file(): 
    file_source = open('resource/path.txt', 'r') # contains 50\n 10\n 30\n 5\n 90\n 20\n 40\n 2\n 25\n 10\n 8\n 0\n 
    return file_source 


def get_path_tuple(file_source, pathList=[]): 
    try: 
     node = int(next(file_source)), int(next(file_source)), int(next(file_source)) 
     pathList.append(node) 
     get_path_tuple(file_source, pathList) 
    except StopIteration: 
     pass 
    return pathList 


def short_step(pathList, n, stepList): 
    try: 
     stepA = pathList[n][0] + pathList[n][1] 
     stepB = pathList[n][1] + pathList[n][2] 
     stepList.append(min([stepA, stepB])) 
     short_step(pathList, n+1, stepList) 
    except IndexError: 
     pass 
    return stepList 


pathList = get_path_tuple(open_file(), []) 
pathList.reverse() 
print(short_step(pathList, 0, [])) 

लेकिन मैं इस समस्या में मारा, मैं कैसे वर्तमान स्थान के राज्य रखने के लिए पता नहीं है। परिणाम है: [8, 27, 95, 40]। क्या आप कृपया मेरे कोड को ठीक करने में मदद कर सकते हैं।

Answer 1

इस विशिष्ट मामले में, और अपने डेटा संरचना का उपयोग, ऐसा लगता है कि आप समानांतर में दो स्थितियों को चलाने के लिए सक्षम होना चाहिए:

बी के एक

लागत की

• लागत

आप वर्तमान लागत को बनाए रख सकते हैं, और आपके द्वारा एकत्रित डेटा तीसरे तत्व में "स्विच करने की लागत" प्रदान करता है।

तो आपको पूछना होगा: कौन सा सस्ता है? शुरुआती पथ पर रहना, या दूसरे रास्ते पर स्विच करना?

path_list = [ 
     (50, 10, 30), 
     (5, 90, 20), 
     (40, 2, 25), 
     (10, 8, 0), 
] 

A = 0 
B = 1 
Switch = 2 

def cheapest_path(path_list, path=None, history=None): 
    if history is not None: 
     # Terminate when path_list is empty 
     if not path_list: 
      return history 

     # Determine cost to stay this path, vs. cost to switch 
     step = path_list[0] 
     path_list = path_list[1:] 

     stay_on_path = cheapest_path(path_list, path, history + [step[path]]) 
     switch_path = cheapest_path(path_list, B if path == A else A, history + [step[path], step[Switch]]) 

     return switch_path if sum(switch_path) < sum(stay_on_path) else stay_on_path 
    else: 

     pathA = cheapest_path(path_list, A, []) 
     pathB = cheapest_path(path_list, B, []) 
     return pathA if sum(pathA) < sum(pathB) else pathB 

print(", ".join(map(str, cheapest_path(path_list)))) 

Answer 2

वास्तव में, मुझे लगता है कि सभी पथदर्शी समस्याओं में, आपको कुल पथ की लंबाई से प्रत्येक बिंदु तक गणना करना होगा। फिर आपको दोनों की गणना करना होगा, बी के पथ की सूची और बी

मुझे पता नहीं है कि रिकर्सिव एल्गोरिदम व्यायाम का हिस्सा है लेकिन मैंने एक साधारण लूप का उपयोग किया है।

pathList = [[50,10,30],[5,90,20],[40,2,25],[10,8,999999]] 

def all_steps(pathList): 

    stepListA,stepListB = [],[] 
    for n in range(0,len(pathList)): 

     #Step to A 
     if pathList[n][0]<=pathList[n][1] + pathList[n][2]:#A to A 
      new_stepListA = list(stepListA) 
      new_stepListA.append(pathList[n][0]) 
     else: #B to A 
      new_stepListA = list(stepListB) 
      new_stepListA.extend([pathList[n][1],pathList[n][2]])   

     #Step to B 
     if pathList[n][1]<=pathList[n][2] + pathList[n][2]:#B to B 
      new_stepListB = list(stepListB) 
      new_stepListB.append(pathList[n][1]) 
     else: #A to B 
      new_stepListB = list(stepListA) 
      new_stepListB.extend([pathList[n][0],pathList[n][2]]) 

     stepListA = list(new_stepListA) 
     stepListB = list(new_stepListB) 

    if sum(stepListA)<=sum(stepListB): 
     print "finish on A" 
     return stepListA 
    else: 
     print "finish on B" 
     return stepListB 


print all_steps(pathList)