Предисловие
Алгоритм поиска обычно известен как алгоритм A-Star. Это алгоритм, который имеет несколько узлов на плоскости графика, чтобы найти самую низкую стоимость прохождения. Обычно используется в играх
Лабиринт, построенный через двумерный массив, «%» представляет стену, а является отправной точкой, b-конечная точка, «#» представляет препятствие, а «*» представляет путь, рассчитанное по алгоритму
Структура кода этой статьи:
% % % % % % % % % % OOOO % OO # OO % % A o # O B % OO # OO % % OOOO % % % % % % % =========================================================================================== oo * oo % % o * # * o % % a o o o o b % oo # oo oo % oo % % % % % % % <
Теория алгоритма
Основная формула алгоритма: f = g+h
Подумайте об узлах на карте как о сетке.
G = Потребление движения движения к указанному узлу на сетке из начальной точки A вдоль сгенерированного пути. В этом примере мы делаем горизонтальное или вертикальное движение стоимостью 10, а диагональное направление стоимость 14. Мы принимаем эти значения, потому что мы вдоль диагонали
Расстояние составляет корень № 2 или примерно в 1,414 раза превышает количество, предпринимаемое для перемещения горизонтально или вертикально. Для простоты мы приближаемся к 10 и 14.
Поскольку мы рассчитываем значение G, приводящее к квадрату вдоль определенного пути, метод оценки заключается в том, чтобы взять значение G его родительского узла, а затем добавить 14 и 10 соответственно в соответствии с его диагональным направлением или правым углом (не-диагональным) относительно родительского узла. В примере это
Спрос на каждый метод становится больше, потому что мы получили более одного квадрата из -за пределов стартовой сетки.
H = расчетное потребление движения от текущей сетки до конечной точки B. Почему оно называется «оценка»? Потому что у нас нет возможности узнать длину пути заранее. Здесь мы используем метод Манхэттена, который вычисляет горизонтальный и вертикальный от текущей сетки до сетки назначения.
Сумма количества квадратов квадратов, игнорируя диагональное направление. Затем умножьте результат на 10.
Значение F - это сумма G и H, которая является стандартом, который мы используем для оценки приоритетного пути. Сетка с наименьшим значением F считается приоритетным узлом пути.
Шаги внедрения
Алгоритм написан на Java, сначала посмотрите на содержание класса узлов
пакет a_star_search; / ** * Класс узла * @author zx * */ public class node {private int x; // x координирует частный int y; // y координирует частное строковое значение; // значение узла частного двойного fvalue = 0; // f value private double Gvalue = 0; // g value private double hvalue = 0; // h value private boolean достигается; // это достижимо (это препятствие) частного узла PNODE; // родительский узел public node (int x, int y, строковое значение, логическое достижение) {super (); this.x = x; this.y = y; this.value = значение; Достижимо = достижимо; } public node () {super (); } public int getx () {return x; } public void setx (int x) {this.x = x; } public int gety () {return y; } public void sety (int y) {this.y = y; } public String getValue () {return Value; } public void setValue (строковое значение) {this.value = value; } public double getFvalue () {return fvalue; } public void setfValue (double fvalue) {fvalue = fvalue; } public double getGvalue () {return gvalue; } public void setGvalue (double gvalue) {gvalue = gvalue; } public double gethvalue () {return hvalue; } public void sethvalue (double hvalue) {hvalue = hvalue; } public boolean isReachable () {return достижимо; } public void setReachable (boolean quiebable) {reaicable = quiefable; } public node getPnode () {return pnode; } public void setPnode (узлы pnode) {pnode = pnode; }}Также нужен класс карты. В методе построения карты я реализую карту лабиринта, создав двухмерный массив узлов, который включает в себя начальные и конечные точки.
Пакет A_STAR_SEARCH; Public Class Map {Private Node [] [] MAP; // Массив узлов Private Node STARTNODE; // Запуск частного узла ENDNODE; // Конечная точка Public MAP () {MAP = новый узел [7] [7]; для (int i = 0; I <7; I ++) {для (int j = 0; j <7; j+{i] {n new j = 0; Узел (i, j, "O", true);}} for (int d = 0; d <7; d ++) {map [0] [d] .setValue ("%"); map [0] [d] .setReachable (false); map [d] [0] .setValue ("%"); Map [d] [0] .SetReachable (fal SE); MAP [6] [D] .SetValue ("%"); MAP [D] [6] .SetValue ("%"); MAP [D] [6] .SetReachable (false);} MAP [3] [1] .SetValue ("a"); StartNode = MAP [3] [1]; MAP [3] [5] .SetValue ("B"); EndNode = MAP [3] [5]; for (int k = 1; k <= 3; k ++) {map [k+1] [3] .setValue ("#"); Map [k+1] [3] .setReachable (false);}} <span style = "span/" span/"span/" span/"span/" span/"span/" span/"span/" span/"span/" span/"span/" span/"span/} Карта public void showmap () {for (int i = 0; i <7; i ++) {for (int j = 0; j <7; j ++) {System.out.print (map [i] [j] .getValue ()+"");} System.out.println ("");} public node [] getMap () {uped; setmap (node [] [] [] map) {this.map = map;} public node getStartNode () {return startNode;} public void setStartNode (node startNode) {this.StartNode = startNode;} public node getEndNode () {return endNode;} public setendNode (nodedode) {nodedondode) {nodedode) {nodedode) {nodedode) {nodedode) {nodedode). endnode;}}Вот самые важные классы ASTAR
Эксплуатационный процесс
1 Начните с начальной точки A и сохраните его в качестве ожидаемой точки в «открытый список», который представляет собой список квадратов, которые будут проверены.
2 Найдите все доступные или проходимые квадраты вокруг отправной точки и пропустите невозможные квадраты. Добавьте их в первый список. Сохраните точку A для всех этих сетей как «родительская сетка». Когда мы хотим описать путь, родительский квадрат
Материал очень важен. Его конкретная цель будет объяснена позже.
3 Удалите начальную точку A из открытого списка и добавьте ее в «Список закрытия», чтобы сохранить все квадраты, которые не нужно проверять снова.
После вышеуказанных шагов «открытый список» содержит все узлы вокруг начальной точки А, за исключением препятствий. Их родительские узлы - все A. Через формулу F = G+H, упомянутая ранее
Сортировка до большого. И сделать следующие операции на узле с наименьшим значением F
4. Удалите его из списка и добавьте в список вне списка.
5. Проверьте все соседние сетки. Пропустите те, которые не передаются (1. В «списке закрытия» и 2. препятствия) и добавьте их в открытый список, если они еще не в нем. Возьмите выбранный квадрат в качестве родительского узла нового квадрата.
6. Если соседняя сетка уже находится в открытом списке, проверьте, лучше ли текущий путь. Другими словами, проверьте, будет ли значение g ниже, если мы достигнем его с новым путем. Если нет, то ничего
Делать. (Здесь нет суждения в моем кодексе)
7. Мы повторяем этот процесс до тех пор, пока целевая сетка (конечная точка «B») не будет добавлена в «Открытый список», указывая, что конечная точка B уже находится вокруг предыдущего узла, добавленного в «Заклинательный список». Вам нужно сделать только один шаг, чтобы достичь конечной точки B.
8. Мы добавляем конечную точку B в «Список закрытия»
9. На последнем этапе мы должны представлять путь от начальной точки A до конечной точки B. отображается роль родительского узла. Изменив значение родительского узла узла конечной точки в «Закройте список», вы можете отобразить путь, следуя подсказкам.
Проверьте код
Пакет a_star_search; import java.util.arraylist; открытый класс astar {/*** Используйте массив ArrayList в качестве "Open List" и "Lock List"*/arraylist <node> open = new Arraylist <node> (); Arraylist <node> Close = new ArrayList <node> ();/*** atel wadles point* @return */public double getHValue(Node currentNode,Node endNode){ return (Math.abs(currentNode.getX() - endNode.getX()) + Math.abs(currentNode.getY() - endNode.getY()))*10;}/** * Get G value* @param currentNode: current node* @return */public double getGValue(Node CurrentNode) {if (currentNode.getPnode ()! = null) {if (currentNode.getx () == currentNode.getPnode (). getX () || currentNode.gety () == currentNode.getPnode (). gety ()) {// Судите по позиционной взаимосвязи между текущим Node и его родителем Node (). currentNode.getGvalue ()+10;} return TurningNode.getGvalue ()+14;} return TurningNode.getGvalue ();}/** * get f Значение: g+h * @param currentNode * @return */public getFvalue (node currentNode) {return Turning.getGvalue ()+currentNode (). * Добавьте узлы вокруг выбранного узла в «Открыть список» * @param node * @param map */public void inopen (узлы узла, карта карта) {int x = node.getx (); int y = node.gety (); для (int i = 0; i <3; i ++) {for (int j = 0; j <3; j+{//////////эдвое значение - это: inte j = 0; это не препятствие, а не в закрытом списке), первый список не включен, и он не выбран if (map.getMap () [x-1+i] [y-1+j] .isReachable () &&! open.contains (map.getMap () [x-1+i] [y-1+j]) & & &! (x == (x-1+i) && y == (y-1+j))) {map.getmap () [x-1+i] [y-1+j] .setpnode (map.getmap () [x] [y]); // Выбранный узел используется в качестве родительского узла map.getmap () [x-1+i] [y-1 +j] .setGvalue (getGvalue (map.getMap () [x-1+i] [y-1+j])); map.getmap () [x-1+i] [y-1+j] .sethvalue (gethvalue (map.getmap () [x-1+i] [y-1+j], map.ge tendnode ())); map.getmap () [x-1+i] [y-1+j] .setfvalue (getFvalue (map.getMap () [x-1+i] [y-1+j])); open.add (map.getMap () * Сортировать узлы в открытом списке от малого до большого значения f * @param arr */public void sort (arraylist <node> arr) {for (int i = 0; i <arr.size ()-1; i ++) {for (int j = i+1; j <arr.size (); j ++) {if (arr.gretfval ()>> arr.get(j).getFValue()){Node tmp = new Node();tmp = arr.get(i);arr.set(i, arr.get(j));arr.set(j, tmp);}}}}/** * Add node to "Close List" * @param node * @param open */public void inClose(Node node,ArrayList<Node> open) {if (open.contains (node)) {node.setReachable (false); // установить недостаток open.remove (node); close.add (node);}} public void search (map map) {// Операция узлов вокруг начальной точки, то есть inopen (map.getmap () [map.getStartNode (). getx ()] [map.getStartNode (). gety ()], map); close.add (map.getMap () [map.getStart Node (). Getx ()] [map.getStartNode (). Getx ()] [map.getStartNode (). Gety ()]); map.getMap () [map.getStartNode (). GetX ()] [map.g etStartNode (). gety ()]. setReachable (false); map.getMap () [map.getStartNode (). getx ()] [map.getStartNode (). gety ()]. setPnode (map.getMap () [map.getStartNode (). getEx ()] [map.getStartNode () do {inopen (open.get (0), map); inclose (open.get (0), open); sort (open);} while (! open.contains (map.getmap () [map.getendnode (). getx ()] [map.getendnode () Inclose (map.getMap () [map.getendNode (). getx ()] [map.getendNode (). getEy ()], open); showpath (close, map);}/** * Отметьте путь * @param arr * @param map */public void showpath (arraylist <node> arr, map) {if (if arr.size () node <node> arr, map) Node (); // <span style = "Белое пространство: pre"> </span> node = map.getmap () [map.getendnode (). Getx ()] [map.getendnode (). Gety ()]; == map.getStartNode (). gety ()) {// <span style = "Белое пространство: pre"> </span> node.getpnode (). setValue ("*"); style = "Белое пространство: pre"> </span> map.getmap () [map.getStartNode (). getX ()] [map.getStartNode (). gety ()]. setValue ("a");}}Наконец напишите основной метод
пакет a_star_search; public Class MainTest {public static void main (string [] args) {map map = new Map (); ASTAR ASTAR = новый ASTAR (); map.showmap (); astar.search (map); System.out.println ("================================================================================== ============================================================================================= ============================================================================================= ================================================================================================ map.showmap ();Изменить карту и проверить ее, чтобы увидеть эффект
% % % % % % % % % % OOOO % OO # OO % % A O # O B % OO # OO % % OOOO % % % % % % % % =============================================================================================================================== % % % % %
Суммировать
Чтобы гарантировать, что кратчайший путь (оптимальное решение) обнаруживается, ключ заключается в выборе функции оценки h (n): фактическое значение расстояния значения оценки h (n) <= n к целевому узлу. В этом случае есть много точек, которые ищут, диапазон поиска большой, а эффективность низкая. Но может получить
Оптимальное решение. Если предполагаемое значение> Фактическое значение, количество поиска точек невелико, диапазон поиска невелик, а эффективность высока, но не может гарантировать, что оптимальное решение получено.
Самое большое чувство: самая табу о рыбалке в течение трех дней и двух дней сушки в сети. Сумма может быть не большой, но она должна быть непрерывностью, а ключом является устойчивость.
Я надеюсь, что каждый программист сможет с радостью впечатать код и делать то, что ему нравится делать.
Выше приведено все содержание этой статьи о программировании Java и реализации полного кода алгоритма*. Я надеюсь, что это будет полезно для всех. Заинтересованные друзья могут продолжать ссылаться на другие связанные темы на этом сайте. Если есть какие -либо недостатки, пожалуйста, оставьте сообщение, чтобы указать это.