easylocal_h-source.html

一个tabu search算法框架

00215     <font class="keyword">virtual</font> <font class="keywordtype">bool</font> <a class="code" href="class_easylocal__ProhibitionManager.html#a1">ProhibitedMove</a>(<font class="keyword">const</font> Move&amp; mv, fvalue mv_cost, fvalue curr, fvalue best) <font class="keyword">const</font> = 0;
00217     <font class="keyword">virtual</font> <font class="keywordtype">void</font> <a class="code" href="class_easylocal__ProhibitionManager.html#a2">Clean</a>() = 0;
<a name="l00220"></a><a class="code" href="class_easylocal__ProhibitionManager.html#a3">00220</a>     <font class="keyword">virtual</font> <font class="keywordtype">void</font> <a class="code" href="class_easylocal__ProhibitionManager.html#a3">Check</a>()<font class="keyword"> </font>{}
00221   };
00222 
00223   <font class="comment">// forward class tag declaration</font>
00224   template &lt;class Move&gt; <font class="keyword">class </font>ListItem;
00225 
00234   template &lt;class Move&gt;
<a name="l00235"></a><a class="code" href="class_easylocal__TabuListManager.html">00235</a>   <font class="keyword">class </font>TabuListManager : <font class="keyword">public</font> ProhibitionManager&lt;Move&gt;
00236   {
00237 <font class="preprocessor">#ifndef __GNUC_MINOR__</font>
00238 <font class="preprocessor"></font>    <font class="keyword">friend</font> std::ostream&amp; operator&lt;&lt;(std::ostream&amp;, const TabuListManager&lt;Move&gt;&amp;);
00239 <font class="preprocessor">#elif __GNUC_MINOR__ &gt; 7 </font>
00240 <font class="preprocessor"></font>    <font class="keyword">friend</font> std::ostream&amp; operator&lt;&lt; &lt;&gt;(std::ostream&amp;, <font class="keyword">const</font> TabuListManager&lt;Move&gt;&amp;);
00241 <font class="preprocessor">#else </font>
00242 <font class="preprocessor"></font>    <font class="keyword">friend</font> std::ostream&amp; operator&lt;&lt;(std::ostream&amp;, const TabuListManager&lt;Move&gt;&amp;);
00243 <font class="preprocessor">#endif</font>
00244 <font class="preprocessor"></font>  <font class="keyword">public</font>:
00245     <font class="keywordtype">void</font> <a class="code" href="class_easylocal__TabuListManager.html#a0">InsertMove</a>(<font class="keyword">const</font> Move&amp; mv, fvalue mv_cost, fvalue curr, fvalue best);
00246     <font class="keywordtype">bool</font> <a class="code" href="class_easylocal__TabuListManager.html#a1">ProhibitedMove</a>(<font class="keyword">const</font> Move&amp; mv, fvalue mv_cost, fvalue curr, 
00247                         fvalue best) <font class="keyword">const</font>;
<a name="l00252"></a><a class="code" href="class_easylocal__TabuListManager.html#a2">00252</a>     <font class="keywordtype">void</font> <a class="code" href="class_easylocal__TabuListManager.html#a2">SetLength</a>(<font class="keywordtype">unsigned</font> <font class="keywordtype">int</font> min, <font class="keywordtype">unsigned</font> <font class="keywordtype">int</font> max)<font class="keyword"> </font>
00253 <font class="keyword">    </font>{ min_tenure = min; max_tenure = max; }
00254     <font class="keywordtype">void</font> <a class="code" href="class_easylocal__TabuListManager.html#a3">Clean</a>();
<a name="l00257"></a><a class="code" href="class_easylocal__TabuListManager.html#a4">00257</a>     <font class="keywordtype">unsigned</font> <font class="keywordtype">int</font> <a class="code" href="class_easylocal__TabuListManager.html#a4">MinTenure</a>()<font class="keyword"> const </font>
00258 <font class="keyword">    </font>{ <font class="keywordflow">return</font> min_tenure; }
<a name="l00261"></a><a class="code" href="class_easylocal__TabuListManager.html#a5">00261</a>     <font class="keywordtype">unsigned</font> <font class="keywordtype">int</font> <a class="code" href="class_easylocal__TabuListManager.html#a5">MaxTenure</a>()<font class="keyword"> const </font>
00262 <font class="keyword">    </font>{ <font class="keywordflow">return</font> max_tenure; }
00269     <font class="keyword">virtual</font> <font class="keywordtype">bool</font> <a class="code" href="class_easylocal__TabuListManager.html#a6">Inverse</a>(<font class="keyword">const</font> Move&amp; mv1, <font class="keyword">const</font> Move&amp; mv2) <font class="keyword">const</font> = 0;
00270   <font class="keyword">protected</font>:
00271     <a class="code" href="class_easylocal__TabuListManager.html#b0">TabuListManager</a>(<font class="keywordtype">int</font> min = 0, <font class="keywordtype">int</font> max = 0);
<a name="l00273"></a><a class="code" href="class_easylocal__TabuListManager.html#b1">00273</a>     <font class="keyword">virtual</font> <a class="code" href="class_easylocal__TabuListManager.html#b1">~TabuListManager</a>()<font class="keyword"> </font>{}
00274     <font class="keyword">virtual</font> <font class="keywordtype">bool</font> <a class="code" href="class_easylocal__TabuListManager.html#b2">Aspiration</a>(<font class="keyword">const</font> Move&amp;, fvalue mv_cost, fvalue curr, fvalue best) <font class="keyword">const</font>; 
00275     <font class="keywordtype">void</font> <a class="code" href="class_easylocal__TabuListManager.html#b3">InsertIntoList</a>(<font class="keyword">const</font> Move&amp; mv); 
<a name="l00281"></a><a class="code" href="class_easylocal__TabuListManager.html#b4">00281</a>     <font class="keywordtype">void</font> <a class="code" href="class_easylocal__TabuListManager.html#b4">UpdateAspirationFunction</a>(fvalue mv_cost, fvalue curr_cost, fvalue best_cost)<font class="keyword"> </font>
00282 <font class="keyword">    </font>{}
00283     <font class="keywordtype">bool</font> <a class="code" href="class_easylocal__TabuListManager.html#b5">ListMember</a>(<font class="keyword">const</font> Move&amp;) <font class="keyword">const</font>;
00284                 
<a name="l00285"></a><a class="code" href="class_easylocal__TabuListManager.html#n0">00285</a>     <font class="keywordtype">unsigned</font> <font class="keywordtype">int</font> min_tenure, 
00286       max_tenure;  
<a name="l00287"></a><a class="code" href="class_easylocal__TabuListManager.html#n2">00287</a>     <font class="keywordtype">unsigned</font> <font class="keywordtype">long</font> iter; 
<a name="l00288"></a><a class="code" href="class_easylocal__TabuListManager.html#n3">00288</a>     std::list&lt;ListItem&lt;Move&gt; &gt; tlist; 
00289   };
00290 
00295   template &lt;class Move&gt; 
<a name="l00296"></a><a class="code" href="class_easylocal__ListItem.html">00296</a>   <font class="keyword">class </font>ListItem
00297   {
00298     <font class="keyword">friend</font> <font class="keyword">class </font>TabuListManager&lt;Move&gt;;
00299 <font class="preprocessor">#ifndef __GNUC_MINOR__</font>
00300 <font class="preprocessor"></font>    <font class="keyword">friend</font> std::ostream&amp; operator&lt;&lt;(std::ostream&amp;, const TabuListManager&lt;Move&gt;&amp;);
00301 <font class="preprocessor">#elif __GNUC_MINOR__ &gt; 7 </font>
00302 <font class="preprocessor"></font>    <font class="keyword">friend</font> std::ostream&amp; operator&lt;&lt; &lt;&gt;(std::ostream&amp;, <font class="keyword">const</font> TabuListManager&lt;Move&gt;&amp;);
00303 <font class="preprocessor">#else </font>
00304 <font class="preprocessor"></font>    <font class="keyword">friend</font> std::ostream&amp; operator&lt;&lt;(std::ostream&amp;, const TabuListManager&lt;Move&gt;&amp;);
00305 <font class="preprocessor">#endif</font>
00306 <font class="preprocessor"></font>  <font class="keyword">public</font>:
<a name="l00312"></a><a class="code" href="class_easylocal__ListItem.html#a0">00312</a>     <a class="code" href="class_easylocal__ListItem.html#a0">ListItem</a>(Move mv, <font class="keywordtype">unsigned</font> <font class="keywordtype">long</font> out)
00313       : out_iter(out) { elem = mv; }
00314   <font class="keyword">protected</font>:
<a name="l00315"></a><a class="code" href="class_easylocal__ListItem.html#n0">00315</a>     Move elem;              
<a name="l00316"></a><a class="code" href="class_easylocal__ListItem.html#n1">00316</a>     <font class="keywordtype">unsigned</font> <font class="keywordtype">long</font> out_iter; 
00318   };
00319         
00321   template &lt;class Move&gt;
00322   std::ostream&amp; operator&lt;&lt;(std::ostream&amp;, const TabuListManager&lt;Move&gt;&amp;);
00323                  
00324 
00331   template &lt;class Input, class State, class Move&gt;
<a name="l00332"></a><a class="code" href="class_easylocal__NeighborhoodExplorer.html">00332</a>   <font class="keyword">class </font>NeighborhoodExplorer
00333   {
00334   <font class="keyword">public</font>:
<a name="l00336"></a><a class="code" href="class_easylocal__NeighborhoodExplorer.html#a0">00336</a>     <font class="keyword">virtual</font> <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a0">~NeighborhoodExplorer</a>()<font class="keyword"> </font>{}
00337                 
00338     <font class="comment">// move generating functions</font>
00339     <font class="keyword">virtual</font> <font class="keywordtype">void</font> <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a1">FirstMove</a>(<font class="keyword">const</font> State&amp; st, Move&amp; mv);
00348     <font class="keyword">virtual</font> <font class="keywordtype">void</font> <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a2">NextMove</a>(<font class="keyword">const</font> State &amp;st, Move&amp; mv) = 0;
00355     <font class="keyword">virtual</font> <font class="keywordtype">void</font> <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a3">RandomMove</a>(<font class="keyword">const</font> State &amp;st, Move&amp; mv) = 0;           
00356     <font class="keyword">virtual</font> fvalue <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a4">BestMove</a>(<font class="keyword">const</font> State &amp;st, Move&amp; mv);
00357     <font class="keyword">virtual</font> fvalue <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a5">SampleMove</a>(<font class="keyword">const</font> State &amp;st, Move&amp; mv, <font class="keywordtype">int</font> samples);
00358     <font class="keyword">virtual</font> fvalue <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a6">BestNonProhibitedMove</a>(<font class="keyword">const</font> State &amp;st, Move&amp; mv, fvalue curr, fvalue best);
00359     <font class="keyword">virtual</font> fvalue <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a7">SampleNonProhibitedMove</a>(<font class="keyword">const</font> State &amp;st, Move&amp; mv, <font class="keywordtype">int</font> samples, fvalue curr, fvalue best);
00360     <font class="comment">// end of exploration detection</font>
00361     <font class="keyword">virtual</font> <font class="keywordtype">bool</font> <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a8">LastMoveDone</a>(<font class="keyword">const</font> Move &amp;mv);
00362 
<a name="l00371"></a><a class="code" href="class_easylocal__NeighborhoodExplorer.html#a9">00371</a>     <font class="keyword">virtual</font> <font class="keywordtype">bool</font> <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a9">FeasibleMove</a>(<font class="keyword">const</font> State &amp;st, <font class="keyword">const</font> Move mv)<font class="keyword"> </font>
00372 <font class="keyword">    </font>{ <font class="keywordflow">return</font> <font class="keyword">true</font>; }
00373 
00374     <font class="keyword">virtual</font> <font class="keywordtype">void</font> <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a10">SetProhibitionManager</a>(ProhibitionManager&lt;Move&gt; *pm);
00375 
00383     <font class="keyword">virtual</font> <font class="keywordtype">void</font> <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a11">MakeMove</a>(State &amp;st, <font class="keyword">const</font> Move&amp; mv) = 0;
00384                 
00385     <font class="comment">// evaluation function</font>
00386     <font class="keyword">virtual</font> fvalue <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a12">DeltaCostFunction</a>(<font class="keyword">const</font> State&amp; st, <font class="keyword">const</font> Move &amp; mv);
00387                 
00388     <font class="comment">// debugging/statistic functions</font>
00389     <font class="keyword">virtual</font> <font class="keywordtype">void</font> <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a13">NeighborhoodStatistics</a>(<font class="keyword">const</font> State &amp;st);
00390     <font class="keywordtype">void</font> <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a14">PrintMoveInfo</a>(<font class="keyword">const</font> State &amp;st, <font class="keyword">const</font> Move&amp; mv, std::ostream&amp; os = std::cout);
00391     
<a name="l00399"></a><a class="code" href="class_easylocal__NeighborhoodExplorer.html#a15">00399</a>     <font class="keyword">virtual</font> <font class="keywordtype">void</font> <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a15">InputMove</a>(<font class="keyword">const</font> State &amp;st, Move&amp; mv, std::istream&amp; is = std::cin)<font class="keyword"> const </font>{}
00400                                 
00401     <font class="keywordtype">void</font> <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a16">SetInput</a>(Input* in);
00402     Input* <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a17">GetInput</a>();
00403     <font class="keywordtype">void</font> <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a18">Check</a>();
00404   <font class="keyword">protected</font>:
00405     <a class="code" href="class_easylocal__NeighborhoodExplorer.html#b0">NeighborhoodExplorer</a>(StateManager&lt;Input,State&gt;* sm, Input* in = NULL);
00406     <a class="code" href="class_easylocal__NeighborhoodExplorer.html#b0">NeighborhoodExplorer</a>(StateManager&lt;Input,State&gt;* sm, ProhibitionManager&lt;Move&gt;* pm, Input* in = NULL);
00407                 
<a name="l00408"></a><a class="code" href="class_easylocal__NeighborhoodExplorer.html#n0">00408</a>     StateManager&lt;Input,State&gt;* p_sm; 
<a name="l00410"></a><a class="code" href="class_easylocal__NeighborhoodExplorer.html#n1">00410</a>     Input* p_in; 
00411     <font class="keyword">virtual</font> fvalue <a class="code" href="class_easylocal__NeighborhoodExplorer.html#b2">DeltaObjective</a>(<font class="keyword">const</font> State&amp; st, <font class="keyword">const</font> Move &amp; mv);
00412     <font class="keyword">virtual</font> fvalue <a class="code" href="class_easylocal__NeighborhoodExplorer.html#b3">DeltaViolations</a>(<font class="keyword">const</font> State&amp; st, <font class="keyword">const</font> Move &amp; mv);
00413                 
00414