Breadth-First Search Algorithm JAVA 8-puzzle -


im trying implement breadth-first algorithm 8 puzzle game. know not new case , theres bunch of solutions on web, want make on way of thinking.

this code finds node result, 

123 456 780

but takes 350,000 steps it!

any thoughts appreciated! =)

    //this method receives collection of `nodo` objects, each 1 checked , compare finalgoal       public void percorrenodos(collection<nodo> nodosbase)             {                 //in class have array has ids os nodes has been checked                 //the id of node, representation: 123456780, 354126870 , etc..                 system.out.println("idspercorrido.size() = " + idspercorridos.size());                 //check if collection nodosbase contains finalgoal                 iterator<nodo> iterator =  nodosbase.iterator();                 while( iterator.hasnext() )                 {                     nodo nodobase = (nodo) iterator.next();                     //if current node has been checked, dont have check again                     idspercorridos.add( nodobase.getid() );                             //just print node (sysout)                     nodobase.print();                     contpassos++;                     system.out.println( "\n" + contpassos + " steps(number of nodes checked)..." );                     //check if node final goal                     if( nodobase.isobjetivofinal() )                     {                                     //set variable indicating result has been found                         encontrouobjetivo = true;                         system.out.println( "resultado alcancado em " + contpassos + " passos..." );                         nodobase.print();                         break;                     }                 }                  // know no 1 node of nosobase collection final goal, going generate next children checked, , call function recursively                  //just confirm didnt find goal                  if(encontrouobjetivo == false)                 {                             //creates next frontier                     collection<nodo> novafronteira = new hashset<nodo>();                      for(nodo nodopai : nodosbase)                     {                                     //generate each node childrens , add collection called "novafronteira"                         collection<nodo> filhos = nodopai.gerarfilhos();                         for(nodo filho : filhos)                         { //idspercorridos collection<string> contains nodes ids checked, dont want check node more 1 time !                             if( idspercorridos.contains( filho.getid() ) == false )                             {                                 novafronteira.add( filho );                              }                         }                     }                     this.percorrenodos( novafronteira );                 }              }

you make sure don't add duplicate elements novafronteira.

there's nothing preventing code:

for(nodo nodopai : nodosbase) {     collection<nodo> filhos = nodopai.gerarfilhos();     for(nodo filho : filhos)     {         if( idspercorridos.contains( filho.getid() ) == false )         {             novafronteira.add( filho );         }     } }

from adding many duplicate nodes novafronteira.

if add idspercorridos inside if-statement, prevent happening, , result in less steps, although, depending on data , data structures looks like, added running time of call may make take longer did originally.

if problem running time, should make sure idspercorridos treeset or hashset, these allow efficient contains calls, opposed arraylist or linkedlist, don't.

if doesn't help, try using the a* algorithm instead, involves adding heuristic function each node, distance target - allows explore nodes closer target first, resulting in less steps there.

a heuristic function might sum of manhattan distances between each tile , target location.

note involve quite few changes current code.


Comments

Post a Comment

Popular posts from this blog

apache - Remove .php and add trailing slash in url using htaccess not loading css -

i have add following code htaccess file removing .php extension , add trailing slash urls. worked fine reduced page loading speed , css code not loading @ all. pages ugly. please help rewriteengine on rewritebase / ## hide .php extension snippet # externally redirect /dir/foo.php /dir/foo rewritecond %{the_request} ^[a-z]{3,}\s([^.]+)\.php [nc] rewriterule ^ %1/ [r,l] # add trailing slash rewritecond %{request_filename} !-f rewritecond %{request_uri} !/$ rewriterule . %{request_uri}/ [l,r=301] # internally forward /dir/foo /dir/foo.php rewritecond %{request_filename} !-d rewritecond %{request_filename}.php -f rewriterule ^(.*?)/?$ $1.php [l] we can rewrite urls using .htaccess files. before writing in .htaccess files need verify kind of server using. can check server adding a <?php phpinfo(); ?> in php page. ensure mod_rewrite module enabled in apache server. can identified checking phpinfo included page. common methods used url rewriting follows ...
Read more

javascript - jQuery show full size image on click -

pretty self explanatory not workking . i want display full image when user click on image... yes know there tons of plugins but i want keep simple. any idea ? css : .full { display: none; width: 500px; height: 500px; margin-left: 100px; margin-top: -300px; position: fixed; background-color: #f00; z-index: 6; } .thumbnail { width: 50px; height: 50px; } html: <img class="thumbnail" src="http://4.bp.blogspot.com/-uhbdp2esxng/txneptvi92i/aaaaaaaaaky/upfqis7zto0/s1600/rihanna-wallpaper.jpg"> jquery: $(document).ready(function() { $('.thumbnail').on('click', function() { var img = $('<img />',{src:this.src,'class':'full'}); $('.full').html(img).show(); console.log('done!'); }); }); try looking how jquery works. $(document).ready(function() { $('.thumbnail').on('click', function(...
Read more