Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > PHP: Общие вопросы > Вычисление точек достижимости

Автор: awers 22.3.2006, 17:00

На самом деле я уже не знаю у кого можно спросить.
Перерыл весь инет но ничего не нешел.
Суть в чем..

Есть массив значений, в последствии матрица

Код


$arr=array(
0,0,1,0,1,
1,0,1,0,0,
1,1,1,0,1,
1,0,0,0,1,
0,1,1,1,1
);

Мы находимся в центре массива (13 эллемент).
Мне необходимо получить номера эллементов, к которым я могу пройти по эллементам "1".
Другими словами это карта дороги.

Поясняю, я могу с 13 эллемента перейти на 3, 6, 10, 16....
Но не могу на 5, 25...

Хочу услышать ваши идеи или уже готовые предложения.

Заранее благодарен, Адам Адамович.

Автор: Ivushka 22.3.2006, 17:10

Идея не очень но может пригодиться...

Если создать 2-й массив:
№ячейки=>(*,*,*,*,*,*)//здесь номера ячеек которые окружают от 3 до 6 элементов
а потом когда знаеш № ячейки из матрицы, из этого массива береш ячейки круговые и проверяеш их на 1/0

Автор: awers 22.3.2006, 17:17

ММ..... а ты можешь немного подробнее описать свои мысли ...
Просто немного не понял твоей идеи. Если можно мини-листинг

Автор: Darhazer 22.3.2006, 17:18

Рекурсивною функцию надо написать. Если $arr будет двумерний очень просто:

Код

$arr=array(
 Array ( 0,0,1,0,1),
 Array ( 1,0,1,0,0),
 Array ( 1,1,1,0,1 ),
 Array ( 1,0,0,0,1),
 Array ( 0,1,1,1,1)
);

Иначе не много сложнее считать координат smile

Код


<?
function getAccess($y, $x)
{
global $arr, $access;
   if (isset ($access[$y][$x]) ) return;
   if ( $arr[$y][$x] == 1 )
  {
    $access[$y][$x] = true;
    if ($y>0) getAccess($y-1, $x);
    if ($y<4) getAccess($y+1, $x);
    if ($x>0) getAccess($y, $x-1);
    if ($x<count($arr[0])) getAccess($y, $x+1);
  }
  return;
}

$arr=array(
 Array ( 0,0,1,0,1),
 Array ( 1,0,1,0,0),
 Array ( 1,1,1,0,1 ),
 Array ( 1,0,0,0,1),
 Array ( 0,1,1,1,1)
);

$access = Array();
getAccess(2,2);
ksort($access);
print_r($access);

?>

Автор: awers 22.3.2006, 17:29

К сожелению пример не подходит.
Объясняю почему:

Есть БД с описанием точек:

Цитата

type | ojbect | owner....
0 1577 878
15 81 68758

Значит тип 0 - Это дорога
Тип 15 - завод....

Эта база огромная, примероно 150000 записей.
Я оттуда беру 25 значений (поле видимости 5х5)
И потом я должен отрисовать саму карту.
Необязательно 0-можно, 1- нельзя
Необходимо что-бы и в завод можно было войти.

Т.е. с таким массивом

Код


$arr=array(
 Array ( 0,0,1,0,1),
 Array ( 1,0,1,0,0),
 Array ( 1,1,1,0,1 ),
 Array ( 1,0,0,0,1),
 Array ( 0,1,1,1,1)
);

Это будет не так уж и просто

Автор: Darhazer 22.3.2006, 17:34

Алгоритм тоже самый, только надо отредактировать условия :-) И возможно не много оптимизировать конечно
Вы сам дали пример с 0 и 1, я сделал с 0 и 1 smile

Автор: awers 22.3.2006, 17:35

Кажется я ещё чайник... Спасибо за внимание smile

Автор: _hunter 22.3.2006, 17:53

awers, введение доаолнительных символов алгоритм не усложняют, но при 150000-х точек реккурсия считаться будет несколько лет ( IMHO ( расчитывать время влом ) )
тут уже об эвристике думать нужно...

Автор: awers 22.3.2006, 18:01

Хм... Вопервых загружаться будет не все 150000 точек, а только 25 (к примеру Select * from `pic` limit 750,25)
Во вторых, как ты себе представляешь эвристический анализ такого массива?

На сколько я понимаю эвристические методы не обеспечивают абсолютного достижения цели и оптимальность результата.

Автор: Darhazer 22.3.2006, 18:02

awers
Вообще этот алгоритьм очень близкий к "path finding" (найти траекторию, по которой можно передвигаться с точкой 13 до точку 1), так что почитай о него

Автор: _hunter 22.3.2006, 18:10

если будут загружаться по 25 точек -- зачем упоминать о 150000? они всеравно ни на что не влияют...

Автор: awers 23.3.2006, 01:57

Цитата(Darhazer @ 22.3.2006, 17:18)

Код


<?
function getAccess($y, $x)
{
global $arr, $access;
   if (isset ($access[$y][$x]) ) return;
   if ( $arr[$y][$x] == 1 )
  {
    $access[$y][$x] = true;
    if ($y>0) getAccess($y-1, $x);
    if ($y<4) getAccess($y+1, $x);
    if ($x>0) getAccess($y, $x-1);
    if ($x<count($arr[0])) getAccess($y, $x+1);
  }
  return;
}

$arr=array(
 Array ( 0,0,1,0,1),
 Array ( 1,0,1,0,0),
 Array ( 1,1,1,0,1 ),
 Array ( 1,0,0,0,1),
 Array ( 0,1,1,1,1)
);

$access = Array();
getAccess(2,2);
ksort($access);
print_r($access);

?>

Прошу пояснения к логике функции...
Я жутко запутался.. Все работает, но как - не пойму =)

Автор: Darhazer 23.3.2006, 11:12

awers,
У нас есть массив $arr в котором все точки и массив $access - в котором те точки, к которых мы можем пройти
Что делаеть getAccess()
Мы передаем координати точки, для которой хочим узнать можем ли пройти
Она проверяет если уже была на этой точки и можеть пройти - return
(иначе 2-2 проверить доступ на 1-2, а 1-2 опять на 2-2 и будеть бесконечний loop)
Потом, если можно пройти на эту точки, записиваем в access и проверяем:
Можно ли пройти на верхную точку

Код

if ($y>0) getAccess($y-1, $x);

Можно ли пройти на нижную точки

Код

if ($y<4) getAccess($y+1, $x);

Можно ли пройти на лево

Код

if ($x>0) getAccess($y, $x-1);

Можно ли на право:

Код

if ($x<count($arr[0])) getAccess($y, $x+1);

Для каждой из них, если можно пройти, то функция проверяеть можно ли еще ввърх, вниз, налево и направо
Если добавиш echo $y."-".$x."\n" увидеш как функция проходит массив:

Код


<?
function getAccess($y, $x)
{
global $arr, $access;
echo $y."-".$x."\n";
   if (isset ($access[$y][$x]) ) return;
   if ( $arr[$y][$x] == 1 )
  {
    $access[$y][$x] = true;
    if ($y>0) getAccess($y-1, $x);
    if ($y<4) getAccess($y+1, $x);
    if ($x>0) getAccess($y, $x-1);
    if ($x<count($arr[0])) getAccess($y, $x+1);
  }
  return;
}

Автор: awers 23.3.2006, 17:54

Огромнейшее спасибо за помощь!!!