Trees and their implementation in Python make the concepts easier to understand. I use the Zim wiki along with "kate" editor , MIT class 600, Ipython, along with many other open source programs. The graph was created in Zim which has Python extensions. I reviewed the MIT 600 course again today and there are some very interesting things about probability and logical fallacies. I particularly enjoyed the anecdote about shooting at a wall and then painting a bull's eye afterward to make it appear as if the person was a perfect marksman. A related reference to the "minimum principle".
digraph KnapSack { "Index"->"2-5-0" "Objects [A,B,C]+Weights [5,3,2]+Value[9,7,8][]"->"Weight left"->"2-5-0" "Total Value"->"2-5-0" "2-5-0"[color=green] "1-5-0" "0-5-0" "X-5-0"[color=red] "2-5-0"->"1-5-0"[label=" Leave 2" color="orange"][color=blue] "2-5-0"->"1-3-8"[label=" Take 2" color="orange"][color=blue] "1-3-8"->"0-3-8"[label=" Leave 1" color="orange"][color=blue] "0-3-8"->"X-3-8"[label=" Leave 0" color="orange"][color=blue] "0-3-8"->"X-X-X"[label=" Leave 0" color="orange"][color=blue] "1-3-8"->"0-0-15"[label=" Take 1" color="orange"][color=blue] "0-0-15"->"Y-Y-Y"[label=" Nothing" color="orange"][color=blue] "0-0-15"->"Y-Y-Y"[label=" Nothing" color="orange"][color=blue] "1-5-0"->"0-5-0"[label=" Leave 1" color="orange"][color=blue] "1-5-0"->"0-2-7"[label=" Take 1" color="orange"][color=blue] "0-2-7"->"X-2-7"[label=" Leave 0" color="orange"][color=blue] "0-2-7"->"X-X-X"[label=" NO" color="orange"][color=blue] "0-5-0"->"X-5-0"[label=" Leave 0" color="orange"][color=blue] "0-5-0"->"X-0-9"[label=" take 0" color="orange"][color=blue] }
numCalls=0 def maxVal(w, v, i, aW): #print 'maxVal called with:', i, aW global numCalls numCalls += 1 if i == 0: if w[i] <= aW: return v[i] else: return 0 without_i = maxVal(w, v, i-1, aW) if w[i] > aW: return without_i else: with_i = v[i] + maxVal(w, v, i-1, aW - w[i]) return max(with_i, without_i) # def maxVal0(w, v, i, aW): m = {} #return fastMaxVal(w, v, i, aW, m) def fastMaxVal(w, v, i, aW, m): global numCalls numCalls+=1 try: return m[(i, aW)] except KeyError: if i == 0: if w[i] <= aW: m[(i, aW)] = v[i] return v[i] else: m[(i, aW)] = 0 return 0 without_i = fastMaxVal(w, v, i-1, aW, m) if w[i] > aW: m[(i, aW)] = without_i return without_i else: with_i = v[i] + fastMaxVal(w, v, i-1, aW - w[i], m) res = max(with_i, without_i) m[(i, aW)] = res return res weights=[5,3,2] values=[9,8,7] print fastMaxVal(weights,values,len(values)-1,5,m),numCalls weights=[1,5,3,4] values=[15,10,9,5] print fastMaxVal(weights,values,len(values)-1,5,m),numCalls weights=[1,1,5,5,3,3,4,4] values=[15,15,10,10,5,5,5,5] print fastMaxVal(weights,values,len(values)-1,15,m),numCalls weights=[1,1,5,5,3,3,4,4,1,1,5,5,3,3,4,4] values=[15,15,10,10,5,5,5,5,15,15,10,10,5,5,5,5] print fastMaxVal(weights,values,len(values)-1,15,m),numCalls
Besides the graphing of functions, it is possible to take the data from a decision tree in Python and write it out to plot it as a digraph. Using something new I learned it is possible to create a RoseGarden midi file and a video of the changes to a graph to indicate how it is processed using dvd-slideshow and ffmpeg to create a complete video presentation with annotated source and speech..
dot -Tps digraph.dot -o dgraph1.jpg
2 comments:
well hello there professor, just zooming by for my weekly blogging on my way to infinity and here I am looking at all these formulas trying to find something I can relate to and I always do find something I can relate to in your mind.
that allegory about shooting a hole in the wall and then adding the bulls eye after made me laugh and laugh and laugh but the more I think of it the more disturbing it becomes haha.
we probably do that all the time without being conscious of doing this,anytime we say I won it is in retrospect. haha.
have a beautiful week.
sending you sweetly configured kisses.
I'm glad you enjoyed that. I will try to keep my equations to a minimum and concentrate on the funny stuff :)
Post a Comment