c# - Backtracking Search Algorithms -

-

my real question is, 'why doesn't backtracking speed search?' i'm not sure if makes sense without more context...

this question academic - code 'works' , program finds solutions i'm expecting....but want make sure understand terminology. illustrate things, let's use specific example we'd need search algorithm - n-queens problem.

n-queens problem - placing n queens on n×n chessboard in such way no queen can attack another.

one solution

example solution

there lots of example code on internet can found searching for, 'n-queens backtracking', , wikipedia's article on backtracking uses n-queens in explanation of backtracking (http://en.wikipedia.org/wiki/backtracking). idea, understand it, given board configuration invalid - let's 2 places queens can attack each other, algorithm disregards board configurations made adding additional pieces.

i've implemented (non-recursive/non-backtracking) depth-first , breadth-first version of search. expected, both variations test exact same number of states. expected recursive, depth-first backtracking algorithm should test fewer states. i'm not seeing that.

depth first     found 92 solutions in 10.04 seconds     tested 118969 nodes (1.2k nodes per second)     largest memory set 64 nodes backtracking     found 92 solutions in 9.89 seconds     tested 118969 nodes (1.2k nodes per second)     largest memory set 170 nodes breadth first     found 92 solutions in 12.52 seconds     tested 118969 nodes (0.95k nodes per second)     largest memory set 49415 nodes

my actual implementation intended generic, i'm not taking advantage of board mirrors/rotations or else clever.

i feel must misunderstanding, don't see benefit backtracking gives me?

wikipedia's explains once given state found invalid, it's sub-tree skipped (pruned), placing queens rationally (avoiding q1 in a8 , q2 in a7) seems prevent situations can pruned?

what board configurations should breath-first implementation consider backtracking avoids?

backtracking 1 of several ways avoid searching down bad paths. heuristics, placing queens "rationally" another. non-backtracking solutions must have had enough heuristics avoid searching invalid paths. solution no pruning @ have tested every (64 choose 8) arrangement of queens on board.


Comments

Post a Comment

Popular posts from this blog

html5 - What is breaking my page when printing? -

-
Image
i have questioner , don't know why when printing it's creating break before first question. live demo (link) i able resolve issue removing fieldset container had wrapped in.. having fieldset element causing of fields grouped together, , since not fit on first page, being pushed second page. removing fieldset element, able firefox print first 2 questions on page 1 identically chrome. it seems not new problem firefox , fieldset not playing nice found old bugzilla ticket 2008 has persisted , still being commented on in 2014 (link) if retaining fieldset important, found solution else came here (link) <script type='text/javascript'> $(window).bind('beforeprint', function(){ $('fieldset').each( function(item) { $(this).replacewith($('<div class="fieldset">' + this.innerhtml + '</div>')); } ) }); $(window).bind(
Read more

c# - must be a non-abstract type with a public parameterless constructor in redis -

-
when save object, got below error must non-abstract type public parameterless constructor in order use parameter 't' in generic type or method 'servicestack.redis.redisclient.store<t>(t) redisclass.getinstnace().store(msg); // error here redisclass.getinstnace().save(); as third party's class, can not edit how save object? could create wrapper around third party object call constructor, store wrapper? e.g. public class mywrapper { public thirdpartyobject thirdpartyinstance { get; set; } public mywrapper() { thirdpartyinstance = new thirdpartyobject("constructors"); } }
Read more

ajax - PHP/JSON Login script (Twitter style) not setting sessions -

-
i'm having trouble getting twitter style login work properly, reason gets stuck at session_register("useremail"); session_register("userpass"); and doesn't redirect after it. if enter wrong account data, works , appropriate error message pops up. this full code: <?php if(empty($_post['email']) || empty($_post['password'])) { die(msg(0,"all fields required")); } if(!(preg_match("/^[\.a-z0-9_\-\+]+[@][a-z0-9_\-]+([.][a-z0-9_\-]+)+[a-z]{1,4}$/", $_post['email']))) die(msg(0,"you haven't provided valid e-mail")); $host="localhost"; $username="root"; $password="x"; $db_name="x"; $tbl_name="x"; mysql_connect("$host", "$username", "$password")or die("cannot connect"); mysql_select_db("$db_name")or die("cannot select db"); $useremail=$_post['email']; $userpass=
Read more