<?php
/**
* User: MaximAL
* Date: 12.09.2010
* Time: 17:47:55
*/
header("Content-Type: text/html; charset=utf-8");
require_once("html-templates.php");
/*
* Правила, которые описывают возможные проезды перекрёстков
*/
$rules = array(
"0" => array("fa", "fg"),
"a" => array("bg", "fg", "fk", "f0"),
"b" => array("gh", "gl", "gf", "af"),
"c" => array("bg"),
"d" => array("ej", "cb"),
"e" => array("ji", "dc"),
"f" => array("ab", "gh", "gl", "kl", "kp"),
"g" => array("hm", "hi", "lm", "fa", "f0"),
"h" => array("cb", "ij", "mr", "gf", "gl"),
"i" => array("de", "je", "no", "ns", "hc", "hg"),
"j" => array("ed", "ih", "in"),
"k" => array("pq", "pu", "lq", "lm", "fa"),
"l" => array("mh", "mr", "gf", "gh", "qp", "qr", "kp", "kf"),
"m" => array("rs", "hg", "hc"),
"n" => array("ot", "sr", "st", "ij", "id"),
"o" => array("ts", "ty", "je"),
"p" => array("uv", "ql", "qr", "kf", "kl"),
"q" => array("rs", "rm", "pk", "pu", "lk", "lm"),
"r" => array("sn", "st", "mh"),
"s" => array("to", "ni", "rm"),
"t" => array("oj", "sn", "sr", "yx"),
"u" => array("vq", "vw", "pq", "pk"),
"v" => array("wr", "wx", "qr", "up"),
"w" => array("xs", "xy", "rm", "rs", "vu", "vq"),
"x" => array("yt", "sr", "st", "wr", "wv"),
"y" => array("tz", "xw", "xs"),
"z" => array("yx"),
);
/*
* Найти смежные вершины для заданной вершины
* За вершину принимаем разрешённый поворот — то есть, два пункта на карте.
*/
function co_vert($node)
{
global $rules;
$res = array();
$cross = substr($node, 0, 1);
$next = substr($node, 1, 1);
foreach ($rules[$cross] as $rule)
{
if ((substr($rule, 0, 1) === $next) || ($next === FALSE))
$res[] = $rule;
}
return $res;
}
/*
* Функции поиска возвращают массив, в котором ключами и значениями являются вершины.
* Например, если в массиве в элементе с ключом «bc» находится значение «ab»,
* bc => ab
* это значит, что в вершину «bc» мы попали из вершины ab
*
* Исходя из этого пишем функции получения полного пути и его вывода на экран.
*/
/*
* Получить полный путь от одной вершины до другой из массива $path
*/
function get_full_path($path, $start, $goal)
{
$res = array();
array_push($res, $goal);
$v = $goal;
do
{
$v = $path[$v];
array_push($res, $v);
}
while ($v != $start);
// Обращаем массив
return array_reverse($res);
}
/*
* Распечатать массив с полным путём
*/
function full_patch_to_string($full_path)
{
$res = "";
$pre = "";
foreach ($full_path as $p)
{
$res .= $pre . substr($p, 0, 1);
$pre = " → ";
}
return $res;
}
/*
* Поиск пути в ширину
*/
function BreadthFirstSearch($start, $goal)
{
if ($start === $goal)
return array(0 => $goal);
$queue = array($start); // Для поиска в ширину нужна очередь, в которую мы сначала помещаем начальную вершину
$checked = array(); // Массив пройденных вершин
$path = array(); // Путь
// Пока очередь не пуста
while (($node = array_pop($queue)) !== NULL)
{
// Если достигли цели, выходим
if (($next = substr($node, 1, 1)) === $goal)
{
$path[$next] = $node;
return get_full_path($path, $start, $goal);
break;
}
// Если до цели не дошли, проходим все смежные вершины и помещаем их в очередь
foreach (co_vert($node) as $vert)
{
if (!isset($checked[$vert]))
{
$checked[$vert] = 1;
array_unshift($queue, $vert);
$path[$vert] = $node;
}
}
}
return FALSE;
}
/*
* Волновой поиск пути
*/
function WaveSearch($start, $goal)
{
if ($start === $goal)
return array(0 => $goal);
$time = 0; // Переменная времени
$path = array(); // Путь
$wave_tags = array(); // Волновые метки для вершин
$old_front = array($start); // Старый фронт волны
$new_front = array(); // Новый фронт волны
$wave_tags[$start] = 0; // Волновая метка начальной вершины равна нулю
while (true)
{
// Проходим по старой волне и проверяем её вершины
foreach ($old_front as $node)
{
// Обрабатываем каждую смежную вершину
foreach (co_vert($node) as $vert)
{
// Если вершина ещё не была отмечена меткой
if (!isset($wave_tags[$vert]))
{
// Приравниваем метку вершины к значению времени, увеличенному на единицу
$wave_tags[$vert] = $time + 1;
array_push($new_front, $vert);
$path[$vert] = $node;
}
}
}
// Если в новом фронте волны больше нет вершин, значит искомая вершина не достигнута
if (count($new_front) == 0)
return FALSE;
// Если в новом фронте волны есть конечная вершина, задача решена, возвращаем путь
foreach ($new_front as $node)
{
if (($next = substr($node, 1, 1)) === $goal)
{
$path[$next] = $node;
return get_full_path($path, $start, $goal);
}
}
// Инкрементируем время, переназначаем фронты
$time++;
$old_front = $new_front;
$new_front = array();
}
return FALSE;
}
/*
* Обработка входных параметров и вывод результатов
*/
print $xhtml_header;
if (isset($_GET["start"]) && isset($_GET["goal"]))
{
$start = trim($_GET["start"]);
$goal = trim($_GET["goal"]);
print_form($start, $goal);
if (isset($rules[$start]) && isset($rules[$goal]))
{
print " <p>Поиск в ширину (один из путей):</p>";
print " <ol>\n";
print " <li>Путь из «{$start}» в «{$goal}»: " . full_patch_to_string(BreadthFirstSearch($start, $goal)) . "</li>\n";
print " <li>Путь из «{$goal}» в «{$start}»: " . full_patch_to_string(BreadthFirstSearch($goal, $start)) . "</li>\n";
print " </ol>\n";
print " <p>Волновой поиск (кратчайший путь):</p>";
print " <ol>\n";
print " <li>Путь из «{$start}» в «{$goal}»: " . full_patch_to_string(WaveSearch($start, $goal)) . "</li>\n";
print " <li>Путь из «{$goal}» в «{$start}»: " . full_patch_to_string(WaveSearch($goal, $start)) . "</li>\n";
print " </ol>\n";
}
else
print "<p>Таких мест нет на карте.</p>\n";
}
else if (isset($_GET["getcode"]))
{
print "\n <div>\n";
highlight_file(__FILE__);
print "\n </div>\n";
}
else
print_form("0", "z");
print $xhtml_footer;
?>