Algorithm-Search
view release on metacpan or search on metacpan
example/15.pl view on Meta::CPAN
$puzzle->set_position(
'10 12 7 3
5 13 8 4
9 11 2 0
15 14 1 6');
print "pvalue is ".$puzzle->value."\n";
$fifteen_search->search({search_this=>$puzzle,
solutions_to_find=>1,
search_type => 'bfs',
do_not_repeat_values => 1,
max_steps => 200000
});
print "Solution found :\n";
use Data::Dumper;
print Dumper($fifteen_search->path)."\n";
lib/Algorithm/Search.pm view on Meta::CPAN
$self->{search_completed} = 1;
$self->{continue_search} = 0;
}
}
}
my %path_values;
my $value;
if ($self->{value_function}) {
$value = $initial_position->value;
if ($self->{do_not_repeat_values}) {
$self->{handled}->{$value} = 1;
}
$path_values{$value} = 1;
}
my $initial_commit;
if ($self->{committing}) {
$initial_commit = $initial_position->commit_level;
}
lib/Algorithm/Search.pm view on Meta::CPAN
$new_position = $position->copy;
#print STDERR "recovered from queue cost $cost\n";
my $new_cost = $new_position->move($move, $cost);
$self->{steps}++;
#print STDERR "new cost is $new_cost\n";
if (!defined $new_cost) {
return;
};
if ($self->{cost_cannot_increase} && ($new_cost > $cost) && (defined $cost))
{
return;
}
$self->{last_object} = $new_position;
my $new_path;
$new_path = [@$path, $move];
$self->{last_path} = $new_path;
my $new_path_values;
my $value;
if ($self->{value_function}) {
$value = $new_position->value;
if ($path_values->{$value}) {
return;
}
if ($self->{do_not_repeat_values}) {
if ($self->{handled}->{$value}) {
return;
}
$self->{handled}->{$value} = 1;
}
$new_path_values = {%$path_values};
$new_path_values->{$value} = 1;
}
if ($self->{return_search_trace}) {
lib/Algorithm/Search.pm view on Meta::CPAN
}
else {
$self->{moving_forward} = 1;
$self->{path} = [];
$self->{cost_list} = [];
$self->{commit_list} = [];
if ($self->{value_function}) {
$value = $search_this->value;
$self->{path_values} = {$value => 1};
$self->{value_list} = [$value];
if ($self->{do_not_repeat_values}) {
$self->{handled}->{$value} = 1;
}
}
push @{$self->{info}}, [$value, $self->{cost}, $self->{commit}];
}
if ($self->{return_search_trace}) {
push @{$self->{trace}}, {
cost => $self->{cost},
commit => $self->{commit},
value_before => undef,
lib/Algorithm/Search.pm view on Meta::CPAN
my $self = shift;
my $search_this = $self->{search_this};
my $next_move = $self->{next_move};
#print STDERR "frdfs next move is $next_move\n";
my $new_cost = $search_this->move($next_move);
$self->{steps}++;
if (!defined $new_cost) {
$self->{moving_forward} = 0;
return;
}
if (($self->{cost_cannot_increase}) && ($new_cost > $self->{cost})) {
#print STDERR "cost increased was ".$self->{cost}." to be $new_cost\n";
$search_this->reverse_move($next_move);
$self->{moving_forward} = 0;
return;
}
my $value;
if ($self->{value_function}) {
$value = $search_this->value;
#print STDERR "considering vf on $value\n";
if ($self->{do_not_repeat_values}) {
if ($self->{handled}->{$value}) {
#print STDERR "handled already\n";
$search_this->reverse_move($next_move);
$self->{moving_forward} = 0;
return;
}
$self->{handled}->{$value} = 1;
}
if ($self->{path_values}->{$value}) {
#print STDERR "repeating value\n";
lib/Algorithm/Search.pm view on Meta::CPAN
my $self = shift;
my $parameters = shift;
$self->{search_this} = $parameters->{search_this};
$self->{max_steps} = $parameters->{max_steps}
|| $self->{default_max_steps} || 20000;
$self->{solutions_to_find} = 1;
if (defined $parameters->{solutions_to_find}) {
$self->{solutions_to_find} = $parameters->{solutions_to_find};
}
#print STDERR "Start search\n";
$self->{do_not_repeat_values} = $parameters->{do_not_repeat_values};
$self->{maximum_depth} = $parameters->{maximum_depth};
if (defined $parameters->{maximum_depth}) {
$self->{maximum_depth_minus_one} = $parameters->{maximum_depth} - 1;
}
else {
$self->{maximum_depth_minus_one} = -1;
}
$self->{stop_search} = $parameters->{stop_search} || sub {return 0};
$self->{return_search_trace} = $parameters->{return_search_trace};
my $no_value_function = $parameters->{no_value_function};
$self->{initial_cost} = $parameters->{initial_cost};
$self->{cost_cannot_increase} = $parameters->{cost_cannot_increase};
#copy might not be defined for rdfs, others it is required
if (UNIVERSAL::can($self->{search_this},"copy")) {
$self->{preserve_solutions} = 1;
}
else {
$self->{preserve_solutions} = 0;
}
if (UNIVERSAL::can($self->{search_this},"is_solution")) {
lib/Algorithm/Search.pm view on Meta::CPAN
use Algorithm::Search;
my $as = new Algorithm::Search();
$as->search({ # Example parameters here are the default parameters
search_this => $object_to_search, #no default
search_type => 'dfs', # dfs, bfs, cost, or rdfs
max_steps => 20000, # number of moves to look at
maximum_depth => 0, # longest allowable path length if > 0
solutions_to_find => 0, # search stops when number reached, 0 finds all
do_not_repeat_values => 0, # only traverse position with value once
cost_cannot_increase => 0, # whether or not moves can increase cost
initial_cost => undef, # for cost based search
return_search_trace => 0, # does $as->search_trace return array ref of moves
});
if (!$as->completed) {
$as->continue_search({additional_steps => 300});
}
if ($as->solution_found) {
@solutions = $as->solutions;
@paths_to_solution = $as->paths;
lib/Algorithm/Search.pm view on Meta::CPAN
usage. A reversible traversal is more complicated to set up and only
allows depth first search.
=head1 Methods Required in object being searched.
=head2 Common to all Searches
sub move ($move, $cost)
#required, return undef if illegal move else return cost
If the parameter cost_cannot_increase is set, any move which
would decrease the cost is disallowed. The cost is the value
returned from the move method.
The search parameter initial_cost corresponds to where in the
queue the moves from the initial position belong.
sub value #optional - used to pare down search, a value cannot
#repeat on a search path, prevents loops in paths
If the parameter do_not_repeat_values is set, a value cannot
repeat any time in the search. Presumably this would be done to
find a single solution and not be concerned about the paths.
sub stop_search #optional - after every step, this procedure
#is passed the current position, the number of steps,
#and the path to the current position. If it returns
#a true value, the search stops. Useful for tracing the search.
=head2 Depth First, Breadth First, and Cost Queue-Based Searches
# $puzzle->set_position(
#'10 12 7 3
#5 13 8 4
#9 11 2 0
#15 14 1 6');
#
# print "pvalue is ".$puzzle->value."\n";
# $fifteen_search->search({search_this=>$puzzle,
# solutions_to_find=>1,
# search_type => 'bfs',
# do_not_repeat_values => 1,
# max_steps => 200000
# });
# print "NSolution found :\n";
# use Data::Dumper;
# print Dumper($fifteen_search->path)."\n";
# is_deeply($fifteen_search->path,
# [
# [
# 2,
# 2
# print "s2 in final\n";
}
else {
# print "s2 not in final\n";
}
# $fifteen_search->search({search_this=>$puzzle,
# max_steps => 40000,
# solutions_to_find=>1,
# search_type => 'bfs',
# do_not_repeat_values => 1,
# });
# is($fifteen_search->{steps}, 25211, 'number of steps');
#
# $fifteen_search->search({search_this=>$puzzle,
# max_steps => 40000,
# solutions_to_find=>1,
# search_type => 'bfs',
# do_not_repeat_values => 1,
# });
# is($fifteen_search->{steps}, 25211, 'number of steps a second time');
$fifteen_search->search({search_this=>$puzzle,
max_steps => 20000,
solutions_to_find=>1,
search_type => 'bfs',
do_not_repeat_values => 1,
});
is($fifteen_search->{steps}, 20000, 'number of steps 2');
$fifteen_search->continue_search({additional_steps => 2000});
is($fifteen_search->{steps}, 22000, 'number of steps 3');
is($fifteen_search->{search_completed},0,'search not completed yet');
$fifteen_search->continue_search({additional_steps => 3210});
is($fifteen_search->{steps}, 25210, 'number of steps 4');
return 1;
}
sub commit_level {
my $self = shift;
return $self->lock;
}
sub distance_to_final_state {
my $self = shift;
my $not_correct = 0;
my $distance = 0;
my $new_distance = 0;
$self->{number_locked} = $self->lock;
my @number_cost = (0);
foreach my $i (0..3) {
foreach my $j (0..3) {
my $number = ($j+1) + ($i*4);
if ($self->{board}->[$i]->[$j]) {
$col = ($self->{board}->[$i]->[$j] - 1) % 4;
$row = int(($self->{board}->[$i]->[$j] - 1) / 4);
$number_cost[$self->{board}->[$i]->[$j]] =
(abs($col - $j) + abs($row-$i));
if (($j+1) + ($i*4) != $self->{board}->[$i]->[$j]) {
$not_correct++;
$distance += ($j+1) + ($i*4);
}
}
}
}
my $count = 0;
for my $i (1..15) {
if ($number_cost[$i]) {
$new_distance += $number_cost[$i];
if (++$count == 2) {last};
}
}
#print STDERR $self->value."\n";
#print STDERR "nc ".join (" ",@number_cost)."\n";
#print STDERR "nd $new_distance\n";
#print STDERR "end \n";
#if ($full_count++ == 8) {exit};
#print STDERR "nd $new_distance and d $distance\n";
#print "NC is $not_correct\n";
return ($not_correct,$self->{number_locked});
}
sub next_moves {
my $self = shift;
my @moves;
if ($self->{zero_at}->[0] > 0) {
if (!(
$self->{locked}->[$self->{zero_at}->[0]-1]->[$self->{zero_at}->[1]]
))
{
#5 13 8 4
#9 11 2 0
#15 14 1 6');
#
# my ($ic,undef) = $puzzle->distance_to_final_state;
## print STDERR "pvalue is ".$puzzle->value."\n";
# $fifteen_search->search({search_this=>$puzzle,
# solutions_to_find=>1,
# search_type => 'cost',
# initial_cost => $ic,
# do_not_repeat_values => 1,
## stop_search => sub {
## my $self = shift;
## my $steps = shift;
## if ($steps % 5000 == 0) {
## print STDERR "steps is $steps and self is ".$self->value."\n";
## }
## return 0;
## },
# max_steps => 200000
# });
# print "s2 in final\n";
}
else {
# print "s2 not in final\n";
}
# $fifteen_search->search({search_this=>$puzzle,
# max_steps => 200000,
# solutions_to_find=>1,
# search_type => 'bfs',
# do_not_repeat_values => 1,
## stop_search => sub {
## my $self = shift;
## my $steps = shift;
## if ($steps % 5000 == 0) {
## print STDERR "steps is $steps and self is ".$self->value."\n";
## print STDERR " distance, commit ".join(" ", $self->distance_to_final_state)."\n";
## }
## return 0;
## },
# });
# is($fifteen_search->{steps}, 25211, 'number of steps');
$fifteen_search->search({search_this=>$puzzle,
max_steps => 20000,
solutions_to_find=>1,
search_type => 'bfs',
do_not_repeat_values => 1,
});
is($fifteen_search->{steps}, 20000, 'number of steps 2');
$fifteen_search->continue_search({additional_steps => 2000});
is($fifteen_search->{steps}, 22000, 'number of steps 3');
is($fifteen_search->{search_completed},0,'search not completed yet');
$fifteen_search->continue_search({additional_steps => 310});
is($fifteen_search->{steps}, 22310, 'number of steps 4');
#our $xx = 0;
sub new {return bless {count => 0}}
sub set_rules {
my $self = shift;
my $parameters = shift;
$self->{max_row} = $parameters->{max_row};
$self->{max_column} = $parameters->{max_column};
$self->{start} = $parameters->{start};
$self->{position} = $parameters->{start};
$self->{final} = $parameters->{final};
$self->{not_allowed} = $parameters->{not_allowed};
$self->{not_allowed_count} = 0;
$self->{final_count} = 0;
for my $i (0..$self->{max_row}) {
for my $j (0..$self->{max_column}) {
if ($self->{not_allowed}->[$i]->[$j]) {
$self->{not_allowed_count}++;
}
else {
$self->{final_count}++;
}
}
}
$self->{final_count} -= 1; #start
}
}
if ($self->{value}->[$row]->[$column]) {
return;
}
if (($self->{start}->[0]== $row) && ($self->{start}->[1] == $column)) {
return;
}
if ($self->{not_allowed}->[$row]->[$column]) {
return;
}
$self->{position} = [$row, $column];
if (($self->{final}->[0]== $row) && ($self->{final}->[1] == $column)) {
if ($self->{final_count} == $self->{count}) {return 1}
return;
}
else {
$self->{value}->[$row]->[$column] = $self->{count};
sub copy {
my $self = shift;
my $copy = $self->new;
$copy->{max_row} = $self->{max_row};
$copy->{max_column} = $self->{max_column};
$copy->{start} = $self->{start};
$copy->{final} = $self->{final};
$copy->{final_count} = $self->{final_count};
$copy->{count} = $self->{count};
$copy->{position} = $self->{position};
$copy->{not_allowed} = $self->{not_allowed};
$copy->{not_allowed_count} = $self->{not_allowed_count};
for my $i (0..$self->{max_row}) {
for my $j (0..$self->{max_column}) {
$copy->{value}->[$i]->[$j] = $self->{value}->[$i]->[$j];
}
}
return $copy;
}
for my $j (0..$self->{max_column}) {
if ($self->{value}->[$i]->[$j]) {
$bo .= $self->{value}->[$i]->[$j]." ";
}
elsif (($self->{start}->[0]== $i) && ($self->{start}->[1] == $j)) {
$bo .= "S ";
}
elsif (($self->{final}->[0]== $i) && ($self->{final}->[1] == $j)) {
$bo .= "F ";
}
elsif ($self->{not_allowed}->[$i]->[$j]) {
$bo .= "X ";
}
else {
$bo .= "? ";
}
}
$bo .= "\n";
}
return $bo;
}
package main;
my @solutions;
my $sol_count;
use Algorithm::Search;
my $puzzle = new easy_as_one_two_three;
my $not_allowed;
$not_allowed = [];
$not_allowed->[2][2] = 1;
$not_allowed->[3][0] = 1;
$puzzle->set_rules({
max_row => 3,
max_column => 3,
start => [0,0],
final => [2,1],
not_allowed => $not_allowed,
});
my $puzzle_search = new Algorithm::Search();
$puzzle_search->search({search_this=>$puzzle,
max_steps=>30000,
solutions_to_find=>0,
search_type => 'bfs'
});
# print STDERR "steps taken ".$puzzle_search->steps."\n";
# print STDERR "ps Number of solutions: ".$puzzle_search->{solutions_found}."\n";
"S 1 9 6
12 10 7 11
3 F X 2
X 4 8 5
", "board 1");
#
# $not_allowed = [];
# $not_allowed->[2][1] = 1;
# $puzzle->set_rules({
# max_row => 3,
# max_column => 3,
# start => [1,0],
# final => [3,0],
# not_allowed => $not_allowed,
# });
#
# $puzzle_search = new Algorithm::Search();
# $puzzle_search->search({search_this=>$puzzle,
# max_steps=>30000,
# solutions_to_find=>0,
# search_type => 'bfs'
# });
## print STDERR "steps taken ".$puzzle_search->steps."\n";
## print STDERR "ps Number of solutions: ".$puzzle_search->{solutions_found}."\n";
#8 X 7 9
#F 2 6 11
#", "board 2");
#
$not_allowed = [];
$not_allowed->[2][1] = 1;
$puzzle->set_rules({
max_row => 3,
max_column => 3,
start => [1,0],
final => [1,1],
not_allowed => $not_allowed,
});
$puzzle_search = new Algorithm::Search();
$puzzle_search->search({search_this=>$puzzle,
max_steps=>10000,
solutions_to_find=>0,
search_type => 'bfs'
});
# print STDERR "steps taken ".$puzzle_search->steps."\n";
# print STDERR "ps Number of solutions: ".$puzzle_search->{solutions_found}."\n";
"1 9 5 12
S F 10 13
2 X 4 3
11 8 6 7
", "board 3");
$not_allowed = [];
$puzzle->set_rules({
max_row => 3,
max_column => 3,
start => [1,1],
final => [2,3],
not_allowed => $not_allowed,
});
$puzzle_search = new Algorithm::Search();
$puzzle_search->search({search_this=>$puzzle,
max_steps=>30000,
solutions_to_find=>0,
search_type => 'bfs'
});
# print STDERR "steps taken ".$puzzle_search->steps."\n";
# print STDERR "ps Number of solutions: ".$puzzle_search->{solutions_found}."\n";
is ($solutions[0]->board_out,
"5 2 13 12
8 S 10 9
14 1 4 F
11 3 7 6
", "board 4");
$not_allowed = [];
$puzzle->set_rules({
max_row => 3,
max_column => 3,
start => [1,1],
final => [3,3],
not_allowed => $not_allowed,
});
$puzzle_search->search({search_this=>$puzzle,
max_steps=>30000,
solutions_to_find=>0,
search_type => 'bfs'
});
# print STDERR "steps taken ".$puzzle_search->steps."\n";
# print STDERR "ps Number of solutions: ".$puzzle_search->{solutions_found}."\n";
@solutions = $puzzle_search->solutions;
is ($solutions[0]->board_out,
"14 8 3 4
11 S 1 12
6 7 13 5
10 9 2 F
", "board 5");
$not_allowed = [];
$not_allowed->[0][0] = 1;
$not_allowed->[0][4] = 1;
$puzzle->set_rules({
max_row => 3,
max_column => 4,
start => [3,1],
final => [3,2],
not_allowed => $not_allowed,
});
$puzzle_search->search({search_this=>$puzzle,
max_steps=>30000,
solutions_to_find=>0,
search_type => 'bfs'
});
# print STDERR "steps taken ".$puzzle_search->steps."\n";
# print STDERR "ps Number of solutions: ".$puzzle_search->{solutions_found}."\n";
@solutions = $puzzle_search->solutions;
is ($solutions[0]->board_out,
"X 10 4 11 X
2 9 16 3 8
5 15 13 6 14
1 S F 12 7
", "board 6");
$not_allowed = [];
$not_allowed->[3][0] = 1;
$puzzle->set_rules({
max_row => 3,
max_column => 4,
start => [1,1],
final => [3,4],
not_allowed => $not_allowed,
});
$puzzle_search->search({search_this=>$puzzle,
max_steps=>20000,
solutions_to_find=>1,
search_type => 'dfs'
});
# print STDERR "steps taken ".$puzzle_search->steps."\n";
# print STDERR "ps Number of solutions: ".$puzzle_search->{solutions_found}."\n";
@solutions = $puzzle_search->solutions;
is ($solutions[0]->board_out,
"14 11 9 10 17
2 S 1 3 7
13 5 16 4 6
X 12 8 15 F
", "board 7");
#
# $not_allowed = [];
# $not_allowed->[4][0] = 1;
# $puzzle->set_rules({
# max_row => 4,
# max_column => 4,
# start => [1,2],
# final => [2,0],
# not_allowed => $not_allowed,
# });
#
# $puzzle_search->search({search_this=>$puzzle,
# max_steps=>50000,
# solutions_to_find=>1,
# search_type => 'dfs'
# });
## print STDERR "steps taken ".$puzzle_search->steps."\n";
## print STDERR "ps Number of solutions: ".$puzzle_search->{solutions_found}."\n";
# @solutions = $puzzle_search->solutions;
$full_path = '';
if ($travel_search->solution_found) {
$full_path = 'x';
}
is ($full_path, 'x', 'from duluth');
$r_driver->move([undef, 'Minneapolis']); #start out in Minneapolis
$travel_search->search({
search_this => $r_driver,
search_type => 'rdfs',
do_not_repeat_values => 1,
solutions_to_find => 0,
});
#print "md \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
# print join("..", travel_path($path))."\n";
is ($full_path,
"St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana
", 'rdfs max dci dnrv');
#print STDERR "xx md \n";
$r_driver->move([undef, 'Minneapolis']); #start out in Minneapolis
$travel_search->search({
search_this => $r_driver,
search_type => 'rdfs',
initial_cost => $r_driver->distance_to_final_state,
cost_cannot_increase => 1,
solutions_to_find => 2,
});
#print STDERR "md \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print STDERR "found path from Minneapolis to Urbana\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
# print join("..", travel_path($path))."\n";
St. Paul..Madison..Chicago..Urbana
", 'not distance increas sol 2');
$r_driver->move([undef, 'Minneapolis']); #start out in Minneapolis
$travel_search->search({
search_this => $r_driver,
search_type => 'rdfs',
solutions_to_find => 0,
initial_cost => $r_driver->distance_to_final_state,
cost_cannot_increase => 1,
maximum_depth => 5,
});
#print "md \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
# print join("..", travel_path($path))."\n";
}
is ($full_path,
"St. Paul..Madison..Chicago..Urbana
", 'rdfs max depth 5 all sol not inc dist');
$r_driver->move([undef, 'Minneapolis']); #start out in Minneapolis
$travel_search->search({
search_this => $r_driver,
search_type => 'rdfs',
solutions_to_find => 0,
do_not_repeat_values => 1,
});
#print "md \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
# print join("..", travel_path($path))."\n";
$full_path .= join("..", travel_path($path))."\n";
'move' => 'Urbana',
'value_before' => 'Chicago',
'value_after' => 'Urbana'
}
],
'dfs max depth trace');
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
do_not_repeat_values => 1
});
#print "dnr \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
# print join("..", @{$travel_search->path})."\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
# print join("..", @{$path})."\n";
'move' => 'Urbana',
'value_before' => 'Chicago',
'value_after' => 'Urbana'
}
],
'bfs max depth search trace');
$travel_search->search({search_this => $driver,
search_type => 'bfs',
solutions_to_find => 0,
do_not_repeat_values => 1
});
#print "dnr \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
# print join("..", @{$travel_search->path})."\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
# print join("..", @{$path})."\n";
}
}
is ($full_path,
"Duluth..Chicago..Urbana
St. Paul..Madison..Chicago..Urbana
", 'ts2 max depth dfs');
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
do_not_repeat_values => 1
});
#print "dnr \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
# print join("..", @{$travel_search->path})."\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
# print join("..", @{$path})."\n";
if ($travel_search->solution_found) { #should be false, no path to Urbana
$full_path = 'x';
#print "found path from Duluth to Urbana\n";
}
is ($full_path, 'x', 'ts2 from duluth dfs');
$driver->move('Minneapolis'); #start out in Minneapolis
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
cost_cannot_increase => 1,
initial_cost => $driver->distance_to_urbana,
});
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
# print join("..", @{$travel_search->path})."\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
# print join("..", @{$path})."\n";
$full_path .= join("..", @{$path})."\n";
}
}
is ($full_path,
"St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana
St. Paul..Madison..Chicago..Urbana
", 'ts2 nd minneapolis to urbana paths');
$travel_search->search({search_this => $driver,
solutions_to_find => 2,
cost_cannot_increase => 1,
initial_cost => $driver->distance_to_urbana,
});
#print "sf \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
# print join("..", @{$travel_search->path})."\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
}
is ($full_path,
"St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana
St. Paul..Madison..Chicago..Urbana
", 'ts2 d limit 2');
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
maximum_depth => 5,
cost_cannot_increase => 1,
initial_cost => $driver->distance_to_urbana,
});
#print "md \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
# print join("..", @{$travel_search->path})."\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
$full_path .= join("..", @{$path})."\n";
}
}
is ($full_path,
"St. Paul..Madison..Chicago..Urbana
", 'ts2 xnd max depth dfs');
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
do_not_repeat_values => 1,
cost_cannot_increase => 1,
initial_cost => $driver->distance_to_urbana,
});
#print "dnr \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
# print join("..", @{$travel_search->path})."\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
}
is ($full_path,
"St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana
",
'ts2 nd dfs no repeat values');
$driver->move('Duluth'); #start out in Duluth
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
cost_cannot_increase => 1,
initial_cost => $driver->distance_to_urbana,
});
$full_path = '';
if ($travel_search->solution_found) { #should be false, no path to Urbana
$full_path = 'x';
#print "found path from Duluth to Urbana\n";
}
is ($full_path, 'x', 'ts2 nd from duluth dfs');
$driver->move('Minneapolis'); #start out in Minneapolis
}
is ($full_path,
"Duluth..Chicago..Urbana
St. Paul..Madison..Chicago..Urbana
", 'ts2 bfs max depth');
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
search_type => 'bfs',
do_not_repeat_values => 1
});
#print "dnr \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
# print join("..", @{$travel_search->path})."\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
# print join("..", @{$path})."\n";
$full_path = 'x';
#print "found path from Duluth to Urbana\n";
}
is ($full_path, 'x', 'ts2 from duluth bfs');
$driver->move('Minneapolis'); #start out in Minneapolis
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
search_type => 'bfs',
cost_cannot_increase => 1,
initial_cost => $driver->distance_to_urbana,
});
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
# print join("..", @{$travel_search->path})."\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
# print join("..", @{$path})."\n";
}
}
is ($full_path,
"St. Paul..Madison..Chicago..Urbana
St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana
", 'ts2 bfs nd minneapolis to urbana paths');
$travel_search->search({search_this => $driver,
search_type => 'bfs',
solutions_to_find => 2,
cost_cannot_increase => 1,
initial_cost => $driver->distance_to_urbana,
});
#print "sf \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
# print join("..", @{$travel_search->path})."\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
}
is ($full_path,
"St. Paul..Madison..Chicago..Urbana
St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana
", 'ts2 bfs nd limit 2');
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
search_type => 'bfs',
maximum_depth => 5,
cost_cannot_increase => 1,
initial_cost => $driver->distance_to_urbana,
});
#print "md \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
# print join("..", @{$travel_search->path})."\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
}
}
is ($full_path,
"St. Paul..Madison..Chicago..Urbana
", 'ts2 nd max depth bfs');
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
search_type => 'bfs',
do_not_repeat_values => 1,
cost_cannot_increase => 1,
initial_cost => $driver->distance_to_urbana,
});
#print "dnr \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
# print join("..", @{$travel_search->path})."\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
'value_before' => 'Chicago',
'value_after' => 'Urbana'
}
],
'cost based max depth search trace');
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
search_type => 'cost',
initial_cost => $driver->distance_to_urbana,
do_not_repeat_values => 1,
});
#print "dnr \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
# print join("..", @{$travel_search->path})."\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
# print join("..", @{$path})."\n";
$full_path = 'x';
#print "found path from Duluth to Urbana\n";
}
is ($full_path, 'x', 'ts2 from duluth cost');
$driver->move('Minneapolis'); #start out in Minneapolis
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
search_type => 'cost',
cost_cannot_increase => 1,
initial_cost => $driver->distance_to_urbana,
});
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
# print join("..", @{$travel_search->path})."\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
# print join("..", @{$path})."\n";
}
}
is ($full_path,
"St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana
St. Paul..Madison..Chicago..Urbana
", 'ts2 cost nd minneapolis to urbana paths');
$travel_search->search({search_this => $driver,
search_type => 'cost',
solutions_to_find => 2,
cost_cannot_increase => 1,
initial_cost => $driver->distance_to_urbana,
});
#print "sf \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
# print join("..", @{$travel_search->path})."\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
}
is ($full_path,
"St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana
St. Paul..Madison..Chicago..Urbana
", 'ts2 cost nd limit 2');
$travel_search->search({search_this => $driver,
search_type => 'cost',
solutions_to_find => 0,
maximum_depth => 5,
cost_cannot_increase => 1,
initial_cost => $driver->distance_to_urbana,
});
#print "md \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
# print join("..", @{$travel_search->path})."\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
}
is ($full_path,
"St. Paul..Madison..Chicago..Urbana
", 'ts2 nd max depth cost');
$travel_search->search({search_this => $driver,
search_type => 'cost',
initial_cost => $driver->distance_to_urbana,
solutions_to_find => 0,
do_not_repeat_values => 1
});
#print "dnr \n";
$full_path = '';
if ($travel_search->solution_found) { #should be true, path to Urbana
#print "found path from Minneapolis to Urbana\n";
# print join("..", @{$travel_search->path})."\n";
my $path_count = 0;
foreach my $path ($travel_search->paths) {
# print "Path ".$path_count++." ";
# print join("..", @{$path})."\n";
( run in 1.313 second using v1.01-cache-2.11-cpan-cc502c75498 )