Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Цуканов Б.И. "Время в психике человека" (Медицина)

Суворов С. "Танк Т-64. Первенец танков 2-го поколения " (Военная промышленность)

Нестеров В.А. "Основы проэктирования ракет класса воздух- воздух и авиационных катапульных установок для них" (Военная промышленность)

Фогль Б. "101 вопрос, который задала бы ваша кошка своему ветеринару если бы умела говорить" (Ветеринария)

Яблоков Н.П. "Криминалистика" (Юриспруденция)
Реклама

Секреты разработки игр в Macromedia Flash MX - Макар Дж.

Макар Дж. Секреты разработки игр в Macromedia Flash MX — М.: КУДИЦ-ОБРАЗ , 2004. — 608 c.
ISBN 0-201-77021-0
Скачать (прямая ссылка): sekretirazrabotkiigr2004.djvu
Предыдущая << 1 .. 77 78 79 80 81 82 < 83 > 84 85 86 87 88 89 .. 210 >> Следующая

to false return path
remove it from closed
гпт алгоритм использует два списка (которые во Flash являются массивами),
от-ытый и замкнутый. Открытый массив содержит все узлы, которые были
раскры-! (то есть все его соседи, которые были посещены). Мы используем
открытый
¦ хив как приоритетную ветвь. Мы используем открытый массив не только
mi хранения узлов, но также для хранения узлов в определенном порядке. Мы
задерживаем массив отсортированным от меньшего счета (f) к большему. Каж-
I hi раз, когда мы добавляем узел в открытый массив или изменяем
значение g >зле открытого массива, мы должны сделать новую сортировку
массива, с тем юбы расположить узлы по значению стоимости от меньшей к
большей.
В строках 2 и 3 из кода выше мы создаем пустые открытый и замкнутый
масси-||. Для поиска пути нам необходима начальная точка и цель
назначения, куда \ кно идти. S - это объект, который представляет
начальный узел. Мы устанав-ипаем s.g в 0, поскольку начальный узел не
имеет родителей, так что стоимость ;) для его достижения равно 0 (строка
4). Далее мы находим эвристику h 1Я начального узла. (Помните, что
эвристика является оценочной стоимостью
I текущего узла до цели.) Затем сохраняем значение/ которое является
суммой g и s.h в начальном узле (строка 6). Поскольку s не имеет
родителей, мы уста-Маливаем s.родитель в ноль. Далее мы помещаем узел s в
открытый массив г фока 8). Узел s является теперь первым и лишь узлом в
открытом массиве.
В строке 9 мы устанавливаем переменную признакПоиска в true. Пока она ос-
пется в true, мы будем выполнять поиск А*. Когда мы определили, что нашли
|\ гь, что пути не существует или что мы ищем слишком долго, мы
устанавливаем |ризнакПоиска в false.
В строке 11 мы берем узел из приоритетной ветви. Затем проверяем,
является in этот узел целью. Если да, мы достигли цели; тогда мы
прекращаем поиск
I строим путь (строки 12 - 14). Если это не цель, мы раскрываем узел.
Раскрытие
248
Часть 2. Исследование oi
узла означает, что мы посещаем каждого соседа узла. В строке 16 мы находщ
соседнего узла, т, которую мы искали в данный момент. Затем мы проверяем,
I сещался ли когда-либо этот узел. Если он еще не посещался, то мы входим
в чн<Я алгоритма в строках 18 - 23. Мы устанавливаем значение g в т\
это/его роди id п. Далее мы вычисляем и сохраняем эвристику и/в т.
Наконец, мы устанавли ем свойство родителя на предыдущий узел п. Если
этот узел был посещен прел и теперь имеет более низкий g, то мы входим в
часть алгоритма в строках 25 - 11
О В этом месте я хочу сказать несколько больше о переменной g. Kof
узел посещается в первый раз, он назначает g, основываясь на пути, Г
обходимом, чтобы добраться до этого узла (как мы уже рассматривав Но
возможно и вероятно, что этот узел был посещен снова в процо поиска через
другой возможный путь. Если g из этого нового ini меньше, чем g из
предыдущего сохраненного пути, то мы заменяем рое значение g на новое
значение g (строка 27). В строке 26 мы ycTaiji ливаем переменную родителя
т на узел, из которого мы пришли. Св ство родителя мы используем в конце
поиска для конструирования ' нечного пути. Мы можем двигаться от узла
цели назад к начальной зиции, следуя свойствам родителей. Далее мы
пересчитываем / и зя! пересортируем массив открытый. Мы пересортируем
открытый масИ потому, что мы просто обновляем один из узлов наименьшим
значен|| f так что этот узел может теперь получить приоритет над другим.
Я должен быть с вами честен - я не вполне уверен, что строки 30 и 31
необходи(| Это было в псевдокоде, на котором я изучал алгоритм А*, и я
включил этот ф| мент в мою реализацию на ActionScript. Но эта часть
алгоритма ни разу не посс| лась ни в одном из примеров поиска, которые я
сконструировал (я поместил or тор трассировки в эту часть кода, с тем
чтобы получить информацию, если фрагмент кода сработает). В процессе
многих и многих испытаний я никогда не! блюдап этого. Алгоритм,
написанный в ActionScript, работает точно так, как J жен, и всегда
возвращает путь с наименьшим счетом. Однако я сохранил эту ч! алгоритма,
даже при том, что она кажется ненужной, просто на всякий случай, я я
однажды пойму, зачем она могла бы понадобиться. Если вы знаток в алгорн^
А*, то дайте мне знать ваши мысли по этому вопросу.
После того как все соседи п посещены, мы переходим к строке 32. В этой а
____
мы кладем п в замкнутый массив, потому что он был полностью раскрыт.
Зател^И проверяем время, чтобы удостовериться, что мы ищем не слишком
долго. ЕслиИ искали слишком долго, то мы устанавливаем признакПоиска в
false. В протип^И случае мы перемещаемся на следующий узел в ветви
(строка 11). Если признакЯ иска равен false, мы остановим поиск и
создадим путь.
стр#
а 9. Искусственный интеллект
249
Теперь вы формально познакомились с алгоритмом А*! Не огорчайтесь, если
ii.i i ываете проблемы с пониманием алгоритма; это не самая простая вещь
в мире быстрого восприятия. Мне потребовалось несколько статей из
Предыдущая << 1 .. 77 78 79 80 81 82 < 83 > 84 85 86 87 88 89 .. 210 >> Следующая