Algorithm-Search
view release on metacpan or search on metacpan
# 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,
"Duluth..Chicago..Urbana
St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana
St. Paul..Madison..Rockford..Bloomington..Champaign..Chicago..Urbana
St. Paul..Madison..Chicago..Urbana
", 'ts2 minneapolis to urbana paths');
$travel_search->search({search_this => $driver,
solutions_to_find => 2
});
#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++." ";
# print join("..", @{$path})."\n";
$full_path .= join("..", @{$path})."\n";
}
}
is ($full_path,
"Duluth..Chicago..Urbana
St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana
", 'ts2 limit 2');
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
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";
# 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,
"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";
$full_path .= join("..", @{$path})."\n";
}
}
is ($full_path,
"Duluth..Chicago..Urbana
",
'ts2 dfs no repeat values');
$driver->move('Duluth'); #start out in Duluth
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
});
$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 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++." ";
# 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 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++." ";
# print join("..", @{$path})."\n";
$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++." ";
# print join("..", @{$path})."\n";
$full_path .= join("..", @{$path})."\n";
}
}
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
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
maximum_depth => 8,
no_value_function => 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";
# 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,
"Duluth..Chicago..Minneapolis..St. Paul..Madison..Chicago..Urbana
Duluth..Chicago..Minneapolis..Duluth..Chicago..Urbana
Duluth..Chicago..Urbana
St. Paul..Minneapolis..St. Paul..Minneapolis..Duluth..Chicago..Urbana
St. Paul..Minneapolis..St. Paul..Madison..Chicago..Urbana
St. Paul..Minneapolis..Duluth..Chicago..Urbana
St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana
St. Paul..Madison..Rockford..Bloomington..Champaign..Chicago..Urbana
St. Paul..Madison..Rockford..Madison..Chicago..Urbana
St. Paul..Madison..St. Paul..Minneapolis..Duluth..Chicago..Urbana
St. Paul..Madison..St. Paul..Madison..Chicago..Urbana
St. Paul..Madison..Chicago..Minneapolis..Duluth..Chicago..Urbana
St. Paul..Madison..Chicago..Urbana
", 'ts2 nd dfs distance can increase, no value function');
# as bfs
$driver->move('Minneapolis'); #start out in Minneapolis
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
search_type => 'bfs',
});
$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,
"Duluth..Chicago..Urbana
St. Paul..Madison..Chicago..Urbana
St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana
St. Paul..Madison..Rockford..Bloomington..Champaign..Chicago..Urbana
", 'ts2 bfs minneapolis to urbana paths');
$travel_search->search({search_this => $driver,
search_type => 'bfs',
solutions_to_find => 2
});
#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++." ";
# print join("..", @{$path})."\n";
$full_path .= join("..", @{$path})."\n";
}
}
is ($full_path,
"Duluth..Chicago..Urbana
St. Paul..Madison..Chicago..Urbana
", 'ts2 bfs limit 2');
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
search_type => 'bfs',
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";
# 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,
"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 .= join("..", @{$path})."\n";
}
}
is ($full_path,
"Duluth..Chicago..Urbana
",
'ts2 bfs no repeat values');
$driver->move('Duluth'); #start out in Duluth
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
search_type => 'bfs',
});
$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 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";
$full_path .= 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++." ";
# print join("..", @{$path})."\n";
$full_path .= join("..", @{$path})."\n";
}
}
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++." ";
# print join("..", @{$path})."\n";
$full_path .= join("..", @{$path})."\n";
}
}
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++." ";
# print join("..", @{$path})."\n";
$full_path .= join("..", @{$path})."\n";
}
}
is ($full_path,
"St. Paul..Madison..Chicago..Urbana
",
'ts2 nd bfs no repeat values');
$driver->move('Duluth'); #start out in Duluth
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
search_type => 'bfs',
});
$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 bfs');
$driver->move('Minneapolis'); #start out in Minneapolis
$travel_search->search({search_this => $driver,
search_type => 'bfs',
maximum_depth => 8,
no_value_function => 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";
# 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,
"Duluth..Chicago..Urbana
St. Paul..Madison..Chicago..Urbana
St. Paul..Minneapolis..Duluth..Chicago..Urbana
Duluth..Chicago..Minneapolis..Duluth..Chicago..Urbana
St. Paul..Minneapolis..St. Paul..Madison..Chicago..Urbana
St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana
St. Paul..Madison..Rockford..Madison..Chicago..Urbana
St. Paul..Madison..St. Paul..Madison..Chicago..Urbana
'move' => 'St. Paul',
'value_before' => 'Minneapolis',
'value_after' => 'St. Paul'
},
{
'commit' => undef,
'cost' => 505,
'move' => 'Madison',
'value_before' => 'St. Paul',
'value_after' => 'Madison'
},
{
'commit' => undef,
'cost' => 252,
'move' => 'Rockford',
'value_before' => 'Madison',
'value_after' => 'Rockford'
},
{
'commit' => undef,
'cost' => 185,
'move' => 'Bloomington',
'value_before' => 'Rockford',
'value_after' => 'Bloomington'
},
{
'commit' => undef,
'cost' => 252,
'move' => 'Chicago',
'value_before' => 'Madison',
'value_after' => 'Chicago'
},
{
'commit' => undef,
'cost' => 140,
'move' => 'Urbana',
'value_before' => 'Chicago',
'value_after' => 'Urbana'
},
{
'commit' => undef,
'cost' => 575,
'move' => 'Chicago',
'value_before' => 'Duluth',
'value_after' => 'Chicago'
},
{
'commit' => undef,
'cost' => 140,
'move' => 'Urbana',
'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 .= join("..", @{$path})."\n";
}
}
is ($full_path,
"St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana
",
'ts2 cost no repeat values');
$driver->move('Duluth'); #start out in Duluth
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
search_type => 'cost',
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 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";
$full_path .= 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++." ";
# 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 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++." ";
# print join("..", @{$path})."\n";
$full_path .= join("..", @{$path})."\n";
}
}
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";
$full_path .= join("..", @{$path})."\n";
}
}
is ($full_path,
"St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana
",
'ts2 nd cost no repeat values');
$driver->move('Duluth'); #start out in Duluth
$travel_search->search({search_this => $driver,
solutions_to_find => 0,
search_type => 'cost',
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 cost');
$driver->move('Minneapolis'); #start out in Minneapolis
$travel_search->search({search_this => $driver,
search_type => 'cost',
maximum_depth => 8,
no_value_function => 1,
solutions_to_find => 0,
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++." ";
# print join("..", @{$path})."\n";
$full_path .= join("..", @{$path})."\n";
}
}
is ($full_path,
"St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana
St. Paul..Madison..Rockford..Bloomington..Champaign..Chicago..Urbana
St. Paul..Madison..Chicago..Urbana
St. Paul..Madison..Rockford..Madison..Chicago..Urbana
St. Paul..Madison..St. Paul..Madison..Chicago..Urbana
St. Paul..Minneapolis..St. Paul..Madison..Chicago..Urbana
Duluth..Chicago..Urbana
( run in 1.161 second using v1.01-cache-2.11-cpan-9581c071862 )