easylocaltemplates_cpp-source.html

一个tabu search算法框架

00266     <a class="code" href="class_easylocal__TabuListManager.html#b4">UpdateAspirationFunction</a>(mv_cost,curr,best); 
00267   }
00268 
00278   template &lt;class Move&gt;
<a name="l00279"></a><a class="code" href="class_easylocal__TabuListManager.html#a1">00279</a>   <font class="keywordtype">bool</font> TabuListManager&lt;Move&gt;::ProhibitedMove(<font class="keyword">const</font> Move&amp; mv, fvalue mv_cost, fvalue curr, fvalue best)<font class="keyword"> const</font>
00280 <font class="keyword">  </font>{ <font class="keywordflow">return</font> <a class="code" href="class_easylocal__TabuListManager.html#b5">ListMember</a>(mv) &amp;&amp; !<a class="code" href="class_easylocal__TabuListManager.html#b2">Aspiration</a>(mv,mv_cost,curr,best); }
00281 
00285   template &lt;class Move&gt;
<a name="l00286"></a><a class="code" href="class_easylocal__TabuListManager.html#a3">00286</a>   <font class="keywordtype">void</font> TabuListManager&lt;Move&gt;::Clean()<font class="keyword"></font>
00287 <font class="keyword">  </font>{ tlist.clear(); }
00288 
00296   template &lt;class Move&gt;
<a name="l00297"></a><a class="code" href="class_easylocal__TabuListManager.html#b5">00297</a>   <font class="keywordtype">bool</font> TabuListManager&lt;Move&gt;::ListMember(<font class="keyword">const</font> Move&amp; mv)<font class="keyword"> const</font>
00298 <font class="keyword">  </font>{
00299     std::list&lt;ListItem&lt;Move&gt; &gt;::const_iterator p = tlist.begin();
00300     <font class="keywordflow">while</font> (p != tlist.end())
00301       {
00302         <font class="keywordflow">if</font> (<a class="code" href="class_easylocal__TabuListManager.html#a6">Inverse</a>(mv,p-&gt;elem))
00303           <font class="keywordflow">return</font> <font class="keyword">true</font>;
00304         <font class="keywordflow">else</font>
00305           p++;
00306       }
00307     <font class="keywordflow">return</font> <font class="keyword">false</font>;
00308   }
00309 
00316   template &lt;class Move&gt;
<a name="l00317"></a><a class="code" href="namespace_easylocal.html#a5">00317</a>   std::ostream&amp; operator&lt;&lt;(std::ostream&amp; os, const TabuListManager&lt;Move&gt;&amp; tl)
00318   {
00319     std::list&lt;ListItem&lt;Move&gt; &gt;::const_iterator p = tl.tlist.begin();
00320     <font class="keywordflow">while</font> (p != tl.tlist.end())
00321       {
00322         os &lt;&lt; p-&gt;elem &lt;&lt; <font class="stringliteral">" ("</font> &lt;&lt; p-&gt;out_iter - tl.iter &lt;&lt; <font class="stringliteral">")"</font> &lt;&lt; std::endl;
00323         p++;
00324       }
00325     <font class="keywordflow">return</font> os;
00326   }
00327 
00339   template &lt;class Move&gt;
<a name="l00340"></a><a class="code" href="class_easylocal__TabuListManager.html#b2">00340</a>   <font class="keywordtype">bool</font> TabuListManager&lt;Move&gt;::Aspiration(<font class="keyword">const</font> Move&amp; mv, fvalue mv_cost, fvalue curr, fvalue best)<font class="keyword"> const </font>
00341 <font class="keyword">  </font>{ <font class="keywordflow">return</font> curr + mv_cost &lt; best; }
00342 
00349   template &lt;class Move&gt;
<a name="l00350"></a><a class="code" href="class_easylocal__TabuListManager.html#b3">00350</a>   <font class="keywordtype">void</font> TabuListManager&lt;Move&gt;::InsertIntoList(<font class="keyword">const</font> Move&amp; mv)<font class="keyword"></font>
00351 <font class="keyword">  </font>{
00352     <font class="keywordtype">int</font> tenure = <a class="code" href="namespace_easylocal.html#a3">Random</a>(min_tenure,max_tenure);
00353     ListItem&lt;Move&gt; li(mv, iter+tenure);
00354     tlist.push_front(li);
00355         
00356     std::list&lt;ListItem&lt;Move&gt; &gt;::iterator p = tlist.begin();
00357     <font class="keywordflow">while</font> (p != tlist.end())
00358       <font class="keywordflow">if</font> (p-&gt;out_iter == iter)
00359         p = tlist.erase(p);
00360       <font class="keywordflow">else</font>
00361         p++;
00362     iter++;
00363   }
00364 
00365   <font class="comment">// Neighborhood explorer functions</font>
00366 
00374   template &lt;class Input, class State, class Move&gt;  
<a name="l00375"></a><a class="code" href="class_easylocal__NeighborhoodExplorer.html#b0">00375</a>   NeighborhoodExplorer&lt;Input,State,Move&gt;::NeighborhoodExplorer(StateManager&lt;Input,State&gt;* sm, Input* in) 
00376     :  p_sm(sm), p_in(in), p_pm(NULL)
00377   {}
00378 
00388   template &lt;class Input, class State, class Move&gt;  
<a name="l00389"></a><a class="code" href="class_easylocal__NeighborhoodExplorer.html#b1">00389</a>   NeighborhoodExplorer&lt;Input,State,Move&gt;::NeighborhoodExplorer(StateManager&lt;Input,State&gt;* sm, ProhibitionManager&lt;Move&gt;* pm, Input* in) 
00390     :  p_sm(sm), p_in(in), p_pm(pm)
00391   {}
00392 
00403   template &lt;class Input, class State, class Move&gt;  
<a name="l00404"></a><a class="code" href="class_easylocal__NeighborhoodExplorer.html#a12">00404</a>   fvalue NeighborhoodExplorer&lt;Input,State,Move&gt;::DeltaCostFunction(<font class="keyword">const</font> State&amp; st, <font class="keyword">const</font> Move &amp; mv)<font class="keyword"></font>
00405 <font class="keyword">  </font>{ <font class="keywordflow">return</font> HARD_WEIGHT * <a class="code" href="class_easylocal__NeighborhoodExplorer.html#b3">DeltaViolations</a>(st,mv) + <a class="code" href="class_easylocal__NeighborhoodExplorer.html#b2">DeltaObjective</a>(st,mv); }
00406 
00412   template &lt;class Input, class State, class Move&gt;  
<a name="l00413"></a><a class="code" href="class_easylocal__NeighborhoodExplorer.html#a10">00413</a>   <font class="keywordtype">void</font> NeighborhoodExplorer&lt;Input,State,Move&gt;::SetProhibitionManager(ProhibitionManager&lt;Move&gt;* pm)<font class="keyword"> </font>
00414 <font class="keyword">  </font>{ p_pm = pm; }
00415 
00416 
00426   template &lt;class Input, class State, class Move&gt;  
<a name="l00427"></a><a class="code" href="class_easylocal__NeighborhoodExplorer.html#a4">00427</a>   fvalue NeighborhoodExplorer&lt;Input,State,Move&gt;::BestMove(<font class="keyword">const</font> State &amp;st, Move&amp; mv)<font class="keyword"></font>
00428 <font class="keyword">  </font>{  
00429     <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a1">FirstMove</a>(st,mv); 
00430     fvalue mv_cost = <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a12">DeltaCostFunction</a>(st,mv);
00431     best_move = mv; 
00432     fvalue best_delta = mv_cost;
00433     <font class="keywordflow">do</font> <font class="comment">// look for the best move</font>
00434       { 
00435         mv_cost = <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a12">DeltaCostFunction</a>(st,mv);
00436 <font class="preprocessor">#ifdef COST_DEBUG</font>
00437 <font class="preprocessor"></font>        std::cerr &lt;&lt; mv &lt;&lt; <font class="charliteral">' '</font> &lt;&lt; mv_cost &lt;&lt; std::endl;
00438 <font class="preprocessor">#endif</font>
00439 <font class="preprocessor"></font>        <font class="keywordflow">if</font> (mv_cost &lt; best_delta) 
00440           { 
00441             best_move = mv;
00442             best_delta = mv_cost;
00443           }
00444         <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a2">NextMove</a>(st,mv);
00445       }
00446     <font class="keywordflow">while</font> (!<a class="code" href="class_easylocal__NeighborhoodExplorer.html#a8">LastMoveDone</a>(mv));
00447     mv = best_move;
00448     <font class="keywordflow">return</font> best_delta;
00449   }
00450 
00458   template &lt;class Input, class State, class Move&gt;  
<a name="l00459"></a><a class="code" href="class_easylocal__NeighborhoodExplorer.html#a13">00459</a>   <font class="keywordtype">void</font> NeighborhoodExplorer&lt;Input,State,Move&gt;::NeighborhoodStatistics(<font class="keyword">const</font> State &amp;st)<font class="keyword"></font>
00460 <font class="keyword">  </font>{  
00461     <font class="keywordtype">unsigned</font> <font class="keywordtype">int</font> neighbors = 0, improving_neighbors = 0, 
00462       worsening_neighbors = 0, non_improving_neighbors = 0;
00463     Move mv;
00464     fvalue mv_cost;
00465 
00466     <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a1">FirstMove</a>(st,mv);
00467     <font class="keywordflow">do</font> 
00468       {         
00469         neighbors++;
00470         mv_cost = <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a12">DeltaCostFunction</a>(st,mv);
00471         <font class="keywordflow">if</font> (mv_cost &lt; 0)
00472           improving_neighbors++;
00473         <font class="keywordflow">else</font> <font class="keywordflow">if</font> (mv_cost &gt; 0)
00474           worsening_neighbors++;
00475         <font class="keywordflow">else</font>
00476           non_improving_neighbors++;
00477         <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a2">NextMove</a>(st,mv);
00478       }
00479     <font class="keywordflow">while</font> (!<a class="code" href="class_easylocal__NeighborhoodExplorer.html#a8">LastMoveDone</a>(mv));
00480     std::cout &lt;&lt; <font class="stringliteral">"Neighborhood size: "</font> &lt;&lt;  neighbors &lt;&lt; std::endl
00481               &lt;&lt; <font class="stringliteral">"   improving moves: "</font> &lt;&lt; improving_neighbors &lt;&lt; <font class="stringliteral">" ("</font>
00482               &lt;&lt; (100.0*improving_neighbors)/neighbors &lt;&lt; <font class="stringliteral">"\%)"</font> &lt;&lt; std::endl
00483               &lt;&lt; <font class="stringliteral">"   worsening moves: "</font> &lt;&lt; worsening_neighbors &lt;&lt; <font class="stringliteral">" ("</font>
00484               &lt;&lt; (100.0*worsening_neighbors)/neighbors &lt;&lt; <font class="stringliteral">"\%)"</font> &lt;&lt; std::endl
00485               &lt;&lt; <font class="stringliteral">"   non-improving moves: "</font> &lt;&lt; non_improving_neighbors &lt;&lt; <font class="stringliteral">" ("</font>
00486               &lt;&lt; (100.0*non_improving_neighbors)/neighbors &lt;&lt; <font class="stringliteral">"\%)"</font> &lt;&lt; std::endl;
00487   }
00488 
00497   template &lt;class Input, class State, class Move&gt;
<a name="l00498"></a><a class="code" href="class_easylocal__NeighborhoodExplorer.html#a1">00498</a>   <font class="keywordtype">void</font> NeighborhoodExplorer&lt;Input,State,Move&gt;::FirstMove(<font class="keyword">const</font> State&amp; st, Move&amp; mv)<font class="keyword"> </font>
00499 <font class="keyword">  </font>{ 
00500     <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a3">RandomMove</a>(st,mv); 
00501     start_move = mv;
00502   }
00503 
00513   template &lt;class Input, class State, class Move&gt;  
<a name="l00514"></a><a class="code" href="class_easylocal__NeighborhoodExplorer.html#a5">00514</a>   fvalue NeighborhoodExplorer&lt;Input,State,Move&gt;::SampleMove(<font class="keyword">const</font> State &amp;st, Move&amp; mv, <font class="keywordtype">int</font> samples)<font class="keyword"></font>
00515 <font class="keyword">  </font>{  
00516     <font class="keywordtype">int</font> s = 1;
00517     <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a3">RandomMove</a>(st,mv);
00518     fvalue mv_cost = <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a12">DeltaCostFunction</a>(st,mv);
00519     best_move = mv;
00520     fvalue best_delta = mv_cost;
00521     <font class="keywordflow">do</font> <font class="comment">// look for the best sampled move</font>
00522       { 
00523         mv_cost = <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a12">DeltaCostFunction</a>(st,mv);
00524         <font class="keywordflow">if</font> (mv_cost &lt; best_delta)
00525           { 
00526             best_move = mv;
00527             best_delta = mv_cost;
00528           }
00529         <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a3">RandomMove</a>(st,mv);
00530         s++;
00531       }
00532     <font class="keywordflow">while</font> (s &lt; samples);
00533     mv = best_move;
00534     <font class="keywordflow">return</font> best_delta;
00535   }
00536 
00546   template &lt;class Input, class State, class Move&gt;  
<a name="l00547"></a><a class="code" href="class_easylocal__NeighborhoodExplorer.html#a6">00547</a>   fvalue NeighborhoodExplorer&lt;Input,State,Move&gt;::BestNonProhibitedMove(<font class="keyword">const</font> State &amp;st, Move&amp; mv, fvalue curr, fvalue best)<font class="keyword"> </font>
00548 <font class="keyword">  </font>{
00549     <font class="keyword">register</font> fvalue mv_cost;
00550     <font class="keywordtype">bool</font> tabu_move;
00551     <font class="keywordtype">bool</font> all_moves_tabu = <font class="keyword">true</font>;
00552         
00553     <a class="code" href="class_easylocal__NeighborhoodExplorer.html#a1">FirstMove</a>(st,mv);