page477.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 98 行
HTML
98 行
<HTML><HEAD><TITLE>Projects</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html6652" HREF="page478.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6650" HREF="page433.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6646" HREF="page476.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6654" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0014700000000000000000">Projects</A></H1><P><OL><LI> <A NAME="projectalgsproji"> </A> Design a class that extends the abstract <tt>Solution</tt> class defined in Program <A HREF="page441.html#progsolutiona"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> to represent the nodes of the solution space of a <em>0/1-knapsack problem</em> described in Section <A HREF="page438.html#secalgsknapsack"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P> Devise a suitable representation for the state of a node and then implement the following properties <tt>getIsFeasible</tt>, <tt>getIsComplete</tt>, <tt>getObjective</tt>, <tt>getBound</tt>, and <tt>getSuccessors</tt>. Note, the <tt>getSuccessors</tt> method returns an iterator object that enumerates all the successors of a given node. <OL><LI> Use your class with the <tt>DepthFirstSolver</tt> defined in Program <A HREF="page443.html#progdepthFirstSolvera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> to solve the problem given in Table <A HREF="page438.html#tblalgsknapsack"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> Use your class with the <tt>BreadthFirstSolver</tt> defined in Program <A HREF="page444.html#progbreadthFirstSolvera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> to solve the problem given in Table <A HREF="page438.html#tblalgsknapsack"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> Use your class with the <tt>DepthFirstBranchAndBoundSolver</tt> defined in Program <A HREF="page446.html#progdepthFirstBranchAndBoundSolvera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> to solve the problem given in Table <A HREF="page438.html#tblalgsknapsack"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. </OL><LI> Do Project <A HREF="page477.html#projectalgsproji"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> for the <em>change counting problem</em> described in Section <A HREF="page435.html#secalgschange"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> Do Project <A HREF="page477.html#projectalgsproji"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> for the <em>scales balancing problem</em> described in Section <A HREF="page440.html#secalgsscales"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> Do Project <A HREF="page477.html#projectalgsproji"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> for the <em><I>N</I>-queens problem</em> described in Exercise <A HREF="page476.html#exercisealgsqueens"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> Design and implement a <tt>GreedySolver</tt> class, along the lines of the <tt>DepthFirstSolver</tt> and <tt>BreadthFirstSolver</tt> classes, that conducts a greedy search of the solution space. To do this you will have to add a method to the abstract <tt>Solution</tt> class:<PRE>class GreedySolution(Solution): def greedySuccessor(self): pass greedySuccessor = abstractmethod(greedySuccessor)</PRE><LI> Design and implement a <tt>SimulatedAnnealingSolver</tt> class, along the lines of the <tt>DepthFirstSolver</tt> and <tt>BreadthFirstSolver</tt> classes, that implements the simulated annealing strategy described in Section <A HREF="page474.html#secalgsanneal"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> To do this you will have to add a method to the abstract <tt>Solution</tt> class:<PRE>class SimulatedAnnealingSolution(Solution): def randomSuccessor(self): pass randomSuccessor = abstractmethod(randomSuccessor)</PRE><LI> Design and implement a dynamic programming algorithm to solve the change counting problem. Your algorithm should always find the optimal solution--even when the greedy algorithm fails.<LI> Consider the divide-and-conquer strategy for matrix multiplication described in Section <A HREF="page457.html#secalgsmatrix"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. <OL><LI> Rewrite the implementation of the <tt>__mul__</tt> method of the <tt>Matrix</tt> class introduced in Program <A HREF="page94.html#progmatrixa"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> Compare the running time of your implementation with the <IMG WIDTH=40 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58941" SRC="img329.gif" > algorithm given in Program <A HREF="page96.html#progdenseMatrixb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. </OL><LI> Consider random number generator that generates random numbers uniformly distributed between zero and one. Such a generator produces a sequence of random numbers <IMG WIDTH=88 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68891" SRC="img1973.gif" >. A common test of randomness evaluates the correlation between consecutive pairs of numbers in the sequence. One way to do this is to plot on a graph the points <P> <IMG WIDTH=350 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath68885" SRC="img1974.gif" ><P> <OL><LI> Write a program to compute the first 1000 pairs of numbers generated using the <tt>UniformRV</tt> defined in Program <A HREF="page470.html#proguniformRVa"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> What conclusions can you draw from your results? </OL></OL><P><HR><A NAME="tex2html6652" HREF="page478.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6650" HREF="page433.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6646" HREF="page476.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6654" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?