Модераторы: skyboy, MoLeX, Aliance, ksnk
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Вычисление точек достижимости 
V
    Опции темы
awers
  Дата 22.3.2006, 17:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Участник
Сообщений: 1465
Регистрация: 22.3.2006
Где: Россия, Таганрог

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

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

$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...

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

Заранее благодарен, Адам Адамович.
PM MAIL WWW ICQ Skype   Вверх
Ivushka
Дата 22.3.2006, 17:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 121
Регистрация: 28.10.2005
Где: Москва

Репутация: 2
Всего: 2
Идея не очень но может пригодиться...

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

Это сообщение отредактировал(а) Ivushka - 22.3.2006, 17:11
--------------------
Программист - это диагноз!
PM MAIL ICQ   Вверх
awers
Дата 22.3.2006, 17:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Участник
Сообщений: 1465
Регистрация: 22.3.2006
Где: Россия, Таганрог

Репутация: 21
Всего: 31
ММ..... а ты можешь немного подробнее описать свои мысли ...
Просто немного не понял твоей идеи. Если можно мини-листинг

Это сообщение отредактировал(а) awers - 22.3.2006, 17:17
PM MAIL WWW ICQ Skype   Вверх
Darhazer
Дата 22.3.2006, 17:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 429
Регистрация: 28.9.2005
Где: HellCity (Sofia, Bulgaria)

Репутация: 7
Всего: 29
Рекурсивною функцию надо написать. Если $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);

?>



--------------------
I'm a wheel, I'm a wheel, I can roll, I can feel
But you can't stop me turning
'Cause I'm the sun, I'm the sun, I can move, I can run
But you'll never stom me burning
PM MAIL WWW ICQ YIM   Вверх
awers
Дата 22.3.2006, 17:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Участник
Сообщений: 1465
Регистрация: 22.3.2006
Где: Россия, Таганрог

Репутация: 21
Всего: 31
К сожелению пример не подходит.
Объясняю почему:

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

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)
);

Это будет не так уж и просто
PM MAIL WWW ICQ Skype   Вверх
Darhazer
Дата 22.3.2006, 17:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 429
Регистрация: 28.9.2005
Где: HellCity (Sofia, Bulgaria)

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


--------------------
I'm a wheel, I'm a wheel, I can roll, I can feel
But you can't stop me turning
'Cause I'm the sun, I'm the sun, I can move, I can run
But you'll never stom me burning
PM MAIL WWW ICQ YIM   Вверх
awers
Дата 22.3.2006, 17:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Участник
Сообщений: 1465
Регистрация: 22.3.2006
Где: Россия, Таганрог

Репутация: 21
Всего: 31
Кажется я ещё чайник... Спасибо за внимание smile
PM MAIL WWW ICQ Skype   Вверх
_hunter
Дата 22.3.2006, 17:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник Клуба
Сообщений: 8564
Регистрация: 24.6.2003
Где: Europe::Ukraine:: Kiev

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


--------------------
Tempora mutantur, et nos mutamur in illis...
PM ICQ   Вверх
awers
Дата 22.3.2006, 18:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Участник
Сообщений: 1465
Регистрация: 22.3.2006
Где: Россия, Таганрог

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

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

Это сообщение отредактировал(а) awers - 22.3.2006, 18:07
PM MAIL WWW ICQ Skype   Вверх
Darhazer
Дата 22.3.2006, 18:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 429
Регистрация: 28.9.2005
Где: HellCity (Sofia, Bulgaria)

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


--------------------
I'm a wheel, I'm a wheel, I can roll, I can feel
But you can't stop me turning
'Cause I'm the sun, I'm the sun, I can move, I can run
But you'll never stom me burning
PM MAIL WWW ICQ YIM   Вверх
_hunter
Дата 22.3.2006, 18:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник Клуба
Сообщений: 8564
Регистрация: 24.6.2003
Где: Europe::Ukraine:: Kiev

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


--------------------
Tempora mutantur, et nos mutamur in illis...
PM ICQ   Вверх
awers
  Дата 23.3.2006, 01:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Участник
Сообщений: 1465
Регистрация: 22.3.2006
Где: Россия, Таганрог

Репутация: 21
Всего: 31
Цитата(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);

?>

Прошу пояснения к логике функции...
Я жутко запутался.. Все работает, но как - не пойму =)
PM MAIL WWW ICQ Skype   Вверх
Darhazer
Дата 23.3.2006, 11:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 429
Регистрация: 28.9.2005
Где: HellCity (Sofia, Bulgaria)

Репутация: 7
Всего: 29
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;
}



--------------------
I'm a wheel, I'm a wheel, I can roll, I can feel
But you can't stop me turning
'Cause I'm the sun, I'm the sun, I can move, I can run
But you'll never stom me burning
PM MAIL WWW ICQ YIM   Вверх
awers
Дата 23.3.2006, 17:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Участник
Сообщений: 1465
Регистрация: 22.3.2006
Где: Россия, Таганрог

Репутация: 21
Всего: 31
Огромнейшее спасибо за помощь!!!
PM MAIL WWW ICQ Skype   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "PHP"
Aliance
IZ@TOP
skyboy
SamDark
MoLeX

Новичкам:

  • PHP редакторы собираются и обсуждаются здесь
  • Электронные книги по PHP, документацию можно найти здесь
  • Интерпретатор PHP, полную документацию можно скачать на PHP.NET

Важно:

  • Не брезгуйте пользоваться тегами [code=php]КОД[/code] для повышения читабельности текста/кода.
  • Перед созданием новой темы воспользуйтесь поиском и загляните в FAQ
  • Действия модераторов можно обсудить здесь

Внимание:

  • Темы "ищу скрипт", "подскажите скрипт" и т.п. будут переноситься в форум "Web-технологии"
  • Темы с именами: "Срочно", "помогите", "не знаю как делать" будут УДАЛЯТЬСЯ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, IZ@TOP, skyboy, SamDark, MoLeX, awers.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | PHP: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0585 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.