Так как А* алгоритм строит свой путь, он должен содержать два основных набора точек:

• первый набор "открытые точки" или точки, которые еще должны быть рассмотрены алгоритмом А*;

• второй набор "закрытые точки" или точки, которые уже были рассмотрены алгоритмом A* и их не надо будет снова рассматривать.

Каждая итерация А* алгоритма довольно проста: найти наименее дорогостоящий пункт из набора открытых точек, сделать шаг в любом направлении от этой точки для создания новой открытой точки, а затем переместить путевую точку из открытого набора в закрытый набор. Это повторяется до тех пор, пока текущая точка не достигнет пункта назначения! Если во время этого процесса алгоритм открытых точек заканчивается, то нет пути от начальной точки до пункта назначения. Такая обработка в первую очередь зависит от расположения точек, поэтому он очень полезен для хранения путевых точек как отображение от места до соответствующих точек. Таким образом, вы будете использовать хранилище java.util. hashmap для каждого из этих наборов с расположением объектов в качестве кодов, и путевых точек объектов в качестве значений.

Прежде чем начать

Прежде чем начать, вы должны скачать исходные файлы для данного учебно-методического пособия:

• Map2D.java - представляет собой карту, по которой А* алгоритм двигается, в том числе проходимы ли клетки.

• Location.java - этот тип представляет собой координаты конкретной ячейки на карте.

• Waypoint.java - представляет отдельные точки в созданный путь.

• AStarPathfinder.java - этот тип реализует А* алгоритм поиска пути как статический метод.

• AStarState.java - этот тип хранит набор открытых точек и закрытых точек и обеспечивает базовые операции, необходимые для функционирования алгоритма поиска А*.

• AStarApp.java - простое Swing - приложение, которое обеспечивает редактируемый вид 2D карты, и запускает поиск пути по запросу.

• JMapCell.java - это Swing - компонент, который используется для отображения состояния клеток на карте.

Обратите внимание, что приложение будет успешно компилироваться как оно и есть, но путь к установлению функций не будет работать, пока вы не выполните задание. Единственные типы, которые вы должны изменить это расположение и AStarState. Все остальное-это код платформы, которая позволяет редактировать карту и показывать путь, по которому алгоритм генерирует. (Если вы редактируете любой из других исходных файлов, чтобы выполнить практикум, то остановитесь и попросите о помощи!)

Размещение

Первое, что должно быть сделано – тип должен быть подготовлен для использования с наборами типов Java. Поскольку вы будете использовать кеширование хранилищ для выполнения данного задания, то это предполагает:

• обеспечение реализации метода equals ();

• обеспечение реализации метода hashcode().

Добавьте реализацию каждого из этих методов в тип Location, как описано описано в общих чертах в типе. Как только это будет завершено, вы можете использовать тип Location как ключевой код хеширования в хранилище, то есть hashset и hashmap.

---

А* форма

После того как тип Location готов к использованию в качестве кода, вы можете закончить реализацию типа AStarState. Это тип, который хранит наборы открытых и закрытых точек, так что это действительно обеспечивает базовую функциональность для А* реализации.

Как упоминалось ранее, А* форма состоит из двух наборов путевых точек: одна из открытых точек, и другие из закрытых точек. Чтобы облегчить алгоритм, путевые точки будут храниться в хэш-карте, в месте, в котором находятся коды, путевые точки и сами значения. Таким образом, у вас будет тип такой:

HashMap<Location, Waypoint>

(Очевидный вывод из всего этого заключается в том, что каждая локация карты может иметь только один путь, связанный с ней. Это именно то, что мы хотим.)

Добавить две (нестатические) области класса AStarState с этим типом: одну для "открытых точек" и другую для "закрытых точек." Кроме того, убедитесь, что нужно инициализировать каждую из этих областей, чтобы отнести в новую пустую коллекцию.

Если у вас есть созданные и инициализированые области, вы должны реализовать следующие методы типа AStarState:

1. public int numOpenWaypoints()

Этот метод просто возвращает количество точек в набор открытых точек. (Да, это будет остроумное замечание...)

2. public Waypoint getMinOpenWaypoint()

Эта функция должна проверить все точки в наборе открытых точек и вернуть ссылку на точку с наименьшей общей стоимостью. Если нет точки в "открытых" наборах, вернитесь NULL.

Не удаляйте путевую точку из набора, когда вы вернули ее, просто верните ссылку на точку с наименьшей общей стоимостью.

3. public boolean addOpenWaypoint(Waypoint newWP)

Это самый сложный способ в А* форме. А делает его сложнее, чем остальные то, что он должен только добавить указанную точку при существующей путевой точке. Вот то, что этот метод должен делать:

• Если в настоящее время нет точек для этого места в "открытых точках" набора, то просто добавить новую точку.

• Если точка уже в этом месте в "открытой точке" набора, то потом добавить новый пункт, только если "старая цена" за новую точку меньше "старой цены" за текущую точку. (Убедитесь, что используете прежнюю стоимость, а не общую стоимость.) Другими словами, если новая точка представляет собой более короткий путь к этому месту, чем текущий маршрут, заменить текущую точку на новую.

Вы можете заметить, что вам придется вернуть существующую маршрутную точку с «открытого» набора, если он есть, и действовать в соответствии с правилом открытого набора. К счастью, это очень просто - заменить предыдущую точку на новую; просто используйте метод hashmap.put (), как обычно, и он заменит старый код, а значения сопоставит с новым кодом.

Наконец, верните действительный метод, если новый пункт был добавлен в набор открытых точек, или ошибочный, если новые точки не добавляются.

4. public boolean isLocationClosed(Location loc)

Эта функция должна вернуть действительный метод, если указанное расположение появляется в наборе закрытых точек или в случае неверного метода. Так как закрытые методы сохранены в хэш-таблице с расположениями значений кода, это довольно просто реализовать.

---

5. public void closeWaypoint(Location loc)

Эта функция берет точку и перемещает её от набора «открытых точек» к набору «закрытых точек». Так как точки закодированы их расположением, метод берет расположение точек.
Процесс должен быть простым:

• удалите соответствие точки указанному расположению из набора «открытых точек»;

• добавьте точку, которую вы просто удалили из набора закрытых точек. Конечно, ключ должен быть расположением точки.

Компиляция и тестирование

Как только вы получаете вышеупомянутую реализованную функциональность, даете новаторской программе выполнить работу, чтобы у видеть правильное выполнение. Если вы реализовали все правильно, у вас не должно быть проблем при создании помех, а затем и нахождении путей вокруг них.

Вы можете скомпилировать и выполнить программу тем же путем, что и всегда:

javac*.java
    java AStarApp

Задача № 4: Фрактал Эксплорер

Для следующих нескольких задач вы соедините небольшое JAVA-приложение, которое может нарисовать некоторые удивительные фракталы. Если вы никогда не играли с фракталами прежде, вы будете поражены тем, как просто можно создать некоторые захватывающие дух красивые изображения. Мы сделаем это все с платформами Swing, API Java, которые позволяют вам создавать графические интерфейсы пользователя.

Мы будем создавать это приложение по многократным задачам, таким образом, наша начальная версия будет довольно проста, но само приложение мы создадим в следующих задачах, чтобы добавить другие функции, такие, как способность сохранять образы, которые мы генерируем, и способность переключаться между различными видами фракталов. И GUI, и механизм для поддержки различных фракталов, будут зависеть от иерархий классов.

Вот простой пример GUI в его начальном состоянии:

И, вот некоторые интересные области фрактала: слоны и морские коньки!

Создание пользовательского интерфейса

Прежде чем мы сможем нарисовать любые фракталы, мы должны будем создать графический виджет, который позволит нам отображать их. Swing не обеспечивает такой компонент, но очень просто создать его самостоятельно. Обратите внимание на то, что мы будем использовать широкий спектр Java AWT и классы Swing в этой задаче, и нет никакого простого способа, которым мы можем объяснить их детали . Однако нет никакой потребности в этом, потому что онлайновые документы API Java очень всесторонни и просты в использовании. Просто переместитесь к пакету данного класса Java, выберите сам класс и затем прочтите подробную информацию о том, как использовать класс.

Создайте класс JImageDisplay, который возьмём из javax.swing. JComponent. У класса должны быть одно частное поле, пример java.awt.image. BufferedImage. Класс BufferedImage управляет изображением, в содержание которого мы можем записать информацию.

Конструктор JImageDisplay должен взять целочисленную ширину и высоту и инициализировать ее члена BufferedImage, чтобы быть новым изображением той ширины и высоты, и типом изображения TYPE_INT_RGB. Тип просто определяет, как цвета каждого пикселя представлены в изображении; это определенное значение означает, что красные, зеленые, и синие компоненты - каждые 8 бит, и они появляются в интервале в том порядке.

---

Ваш конструктор должен сделать еще одну вещь: это должно вызвать setPreferredSize родительского класса () - метод с указанной шириной и высотой. (Вы должны будете передать эти значения в java.awt. Объект размерности вы создаете, в частности, для этого вызова.) Таким образом, когда ваш компонент будет включен в пользовательский интерфейс, он на самом деле выведет на экран все изображение.

Пользовательские компоненты Swing должны обеспечить свой собственный код для прорисовки, переопределив защищенный paintComponent (графика g) - метод JComponent. Так как наш компонент просто выведет на экран сами данные изображения, наша реализация будет очень проста! Во-первых, реализацию суперкласса paintComponent (g) нужно всегда вызывать так, чтобы любые границы или другие функции были оттянуты правильно. Как только вы вызвали версию суперкласса, вы можете вовлечь изображение в компонент, используя работу:

g.drawImage (изображение, 0, 0, image.getWidth (), image.getHeight (),0);

(Мы передаем нуль для ImageObserver, так как нам не нужна эта функциональность.)

Вы также должны обеспечить два открытых метода для записи данных в изображение: clearImage () - метод, который устанавливает все пиксели в данных изображения к черному цвету (значение RGB 0), и drawPixel (интервал x, интервал y, интервал rgbColor) - метод, который устанавливает определенный цвет для пикселя. Оба эти метода должны будут использовать один из setRGB () - метод на классе BufferedImage.

Конечно, не забывайте писать четкую, полную и краткую документацию для своего класса и методы, объясняя, что все делает.

Вычисления фрактала Mandelbrot

Затем вы запишете код, чтобы вычислить очень известный фрактал Мальдерброта. Чтобы поддерживать многократные фракталы в будущем, вам предоставляют исходный файл FractalGenerator.java, из которого произойдут все Ваши фрактальные генераторы. вы также заметите, что некоторые очень полезные операции обеспечены, чтобы перевести из экранных координат в систему координат вычисляемого фрактала.

Виды фракталов, с которыми мы будем работать, вычислены в комплексной плоскости и включают очень простые математические функции, которые неоднократно выполняются с помощью итераций, пока некоторое условие не удовлетворено. Для фрактала Мальдерброта функция - цинк = цинк 12 + c, где все значения - комплексные числа, z0 = 0, и c - определенная точка во фрактале, который мы выводим на экран. Это вычисление выполнено с помощью итераций до любого |z |&gt; 2 (в этом случае точка не находится во множестве Мандельброта), или пока количество итераций не поражает максимальное значение, например, 2000 (в этом случае, мы предполагаем, что точка находится в наборе).

Процесс графического изображения множества Мандельброта очень прост: мы просто выполняем итерации по каждому пикселю в нашем изображении, вычисляем количество итераций для соответствующей координаты, и затем устанавливаем пиксель в цвет на основе количества итераций, которые мы вычислили. Но, мы доберемся до этого через секунду - на данный момент, вы просто должны реализовать вышеупомянутое вычисление.

---

• Создайте подкласс FractalGenerator по имени Mandelbrot. Вы будете видеть, что есть только два метода, которые вы должны обеспечить в подклассе, getInitialRange () и numIterations ().

• getInitialRange (Rectangle2D.Double) метод позволяет фрактальному генератору определять, какая часть комплексной плоскости является самой "интересной" для определенного фрактала. Обратите внимание на то, что прямоугольный объект передан как параметр методу, и метод должен изменить поля прямоугольника, чтобы отразить надлежащий начальный диапазон для фрактала. (Вы видите пример этого в методе FractalGenerator.recenterAndZoomRange ().) Реализация этого метода должна установить начальный диапазон в (-2 - 1.5i) - (1 + 1.5i). Т.е. x и значения y будут -2 и -1.5 соответственно, и ширина и высота будут равняться 3.

• numIterations - метод реализует итеративную функцию для фрактала Мальдерброта. Вы можете определить константу для "максимальных итераций",

public static final int MAX_ITERATIONS = 2000;

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

Обратите внимание на то, что у Java нет типа данных для комплексных чисел, таким образом, вы должны будете реализовать итеративную функцию, используя отдельные двойные компоненты для действительных и мнимых частей. (Я предполагаю, что вы могли реализовать свой собственный класс комплексного числа, но это не будет стоить того). Вы должны попытаться сделать свою реализацию быстро; например, не сравнивайте |z | с 2; сравните |z| 2 с 22, чтобы избежать сложных и медленных вычислений квадратного корня. И не используйте Math.pow (), чтобы вычислить маленькие целочисленные числа; умножьте их непосредственно, иначе ваш код будет очень медленным.

Наконец, при переборе, ваша функция, если вы попали MAX_ITERATIONS, потом просто возвращает значение -1, чтобы указать, что точка не выходит за границы.

Соединим всё это

Наконец мы готовы начать отображать фракталы! Теперь вы создадите класс FractalExplorer, который позволяет вам исследовать различные части фрактала, создавая и показывая GUI Swing и обрабатывая события, вызванные различным взаимодействием с пользователем.

Как вы видите от вышеупомянутых изображений пользовательского интерфейса, Фрактальный Проводник очень прост, состоит из JFrame, содержащего JImageDisplay, который выводит на экран фрактал, и единственный JButton для сброса дисплея, чтобы показать весь фрактал. Вы можете достигнуть этого простого расположения, установив фрейм, имещий BorderLayout, затем поместив дисплей в центр расположения и кнопку сброса в "южной" части расположения.

• Ваш класс FractalExplorer должен будет отслеживать несколько важных полей для состояния программы:

1. целое число "выводит на экран размер", который является просто шириной и высотой дисплея в пикселях. (Наш фрактальный дисплей будет квадратным);

2. ссылка JImageDisplay, так, чтобы мы могли обновить наш дисплей из различных методов, поскольку мы вычисляем фрактал;

3. объект FractalGenerator. Мы будем использовать ссылку базового класса так, чтобы мы могли показать другие виды фракталов в будущем;

4. определение объекта Rectangle2D.Double диапазона комплексной плоскости, которую мы в настоящее время выводим на экран.

---

Смотрите также файлы

• Лабораторная 2.doc

• Основы инфокоммуникационны технологий.pdf

• Задание для теоретической части курсовой работы.pdf

• Методические указания по информатике.docx

• Методические для курсовых работ.doc