Форум программистов, компьютерный форум, киберфорум
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.94/18: Рейтинг темы: голосов - 18, средняя оценка - 4.94
0 / 0 / 0
Регистрация: 05.11.2015
Сообщений: 1
1

Поиск кратчайшего пути в лабиринте. Алгоритм А*

05.11.2015, 14:16. Просмотров 3285. Ответов 2
Метки нет (Все метки)


Добрый день, реализовал алгоритм A* на java, довольно коряво, но проблема в другом. Мне нужно найти кратчайшее расстояние из левого верхнего угла в правый нижний, в матрице 4000х4000, которая состоит из "." и "^". На небольших матрицах программа работает довольно быстро, а в матрице 4000х4000 зависает на очень долго.
Вот сам код:
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
public class Point {
 
    public int X;
    public int Y;
    public Point(int X,int Y)
    {
        this.X=X;
        this.Y=Y;
    }
}
public class PathNode extends Point {
    public Point goal;
    public Point position;
    public PathNode(Point point, PathNode pathNode, Point goal) {
        super(point.X, point.Y);
        position = point;
        setCameFrome(pathNode);
        this.goal = goal;
        if (pathNode!=null)//нужно только для стартовой точки
        setLengthFromStart(pathNode.getLengthFromStart());
        else setLengthFromStart(-1);
        setLengthToGoal(goal);
        setFullLength(getLengthFromStart()+getLengthToGoal());
    }
 
    public PathNode CameFrome;//родительская точка
 
    public void setCameFrome(PathNode CameFrome) {
        this.CameFrome = CameFrome;
    }
 
    public int LengthFromStart;
 
    public void setLengthFromStart(int i) {
        LengthFromStart = i + 1;
    }
 
    public int getLengthFromStart() {
        return LengthFromStart;
    }
 
    public int LengthToGoal;
    public void setLengthToGoal(Point goal)//манхэттенское расстояние до цели
    {
        LengthToGoal = Math.abs(goal.X - this.position.X) + Math.abs(goal.Y - this.position.Y);
    }
    public int getLengthToGoal()
    {
        return LengthToGoal;
    }
 
    public int FullLength;
    public void setFullLength(int i)
    {
        this.FullLength=i;
    }
    public int getFullLength() {
       return FullLength;
    }
 
}
 
public class newSolution {
    public static char[][] matrix;
    public static void main(String[] args) throws IOException{
        matrix = creatFile(args[0]);//читает файл и создает матрицу.
        Point start = new Point(0,0);
        Point goal = new Point(600,600);
        ArrayList<Point> list = FindPath(start,goal);
 
        for (Point point : list)
        {
            System.out.print(point.X + " " + point.Y + " , ");
        }
        System.out.println();
        System.out.println(list.size()-1);
        //FileWriter outFile = new FileWriter("C:\\Users\\������������\\IdeaProjects\\���������\\src\\PAth\\2A");
       // outFile.write(list.size());
 
    }
 
 
    public static char[][] creatFile(String fileName) throws IOException { //читает файл и создает матрицу.
        BufferedReader inFile = new BufferedReader(new FileReader(fileName));
        String[] size = inFile.readLine().split(" ");//из первой строки считывает размерность матрицы
        int size1 = Integer.parseInt(size[0]);
        int size2 = Integer.parseInt(size[1]);
        System.out.println(size1 + " " + size2);
        char[][] matr = new char[size1][size2];
        String s;
        for (int i = 0; i<size1; i++) {
            s = inFile.readLine();
            matr[i]=s.toCharArray();
        }
        inFile.close();
        System.out.println();
        return matr;
 
    }
    public static ArrayList<Point> FindPath(Point start, Point goal)
    {
        ArrayList<PathNode> closedSet = new ArrayList<>();//список рассмотренных точек
        ArrayList<PathNode> openSet = new ArrayList<>();//список еще не рассмотренных точек
 
        PathNode startNode = new PathNode(start,null,goal);
 
        startNode.LengthFromStart=0;
        int z=0;
        openSet.add(startNode);
        while (openSet.size() > 0)
        {
            PathNode currentNode = minLength(openSet);//находит точку с min "Полным путем"
            if (currentNode.position.X == goal.X && currentNode.position.Y == goal.Y)
                return GetPath(currentNode);//если в конечной точке, то возращает весь путь
            closedSet.add(currentNode);
            openSet.remove(currentNode);
 
            for (PathNode neighbourNode : GetNeighbours(currentNode, goal))//рассматривает соседей текущей точки
            {
                if (CountInList(closedSet,neighbourNode)>0)//проверяет есть ли точка с этими координатами в closedSet
                    continue;//если да, то берем следующию
                PathNode openNode = getInList(openSet, neighbourNode);//ищет точку с такими же координатами в openSet
                if (openNode == null) {//если нет, то добавляет
                    openSet.add(neighbourNode);
                } else {//если есть то проверяет не большее ли у нее путь от старта, чем у соседа текущей точки
                    if (openNode.LengthFromStart > neighbourNode.LengthFromStart) {
                        //если больше то заменяем ее данные на данные соседа
                        openNode.setCameFrome(currentNode);
                        openNode.LengthFromStart = neighbourNode.LengthFromStart;
                        openNode.FullLength = neighbourNode.FullLength;
                    }
                }
            }
        }
        return null;
    }
    private static ArrayList<PathNode> GetNeighbours(PathNode pathNode, Point goal)//возвращает список "годных" соседей
    {
        ArrayList<PathNode> result = new ArrayList<>();
        Point[] neighbourPoints = new Point[4];
        neighbourPoints[0] = new Point(pathNode.position.X + 1, pathNode.position.Y);
        neighbourPoints[1] = new Point(pathNode.position.X - 1, pathNode.position.Y);
        neighbourPoints[2] = new Point(pathNode.position.X, pathNode.position.Y + 1);
        neighbourPoints[3] = new Point(pathNode.position.X, pathNode.position.Y - 1);
 
        for(Point point : neighbourPoints)
        {
            if (point.X < 0 || point.X >= matrix.length)
                continue;
            if (point.Y < 0 || point.Y >= matrix[0].length)
                continue;
            if (matrix[point.X][point.Y] == '^')
            continue;
            PathNode neighbourNode = new PathNode(point,pathNode,goal);
            result.add(neighbourNode);
        }
        return result;
    }
    public static int CountInList (ArrayList<PathNode> list, PathNode pathNode)//проверяет есть ли точка с этими координатами в closedSet
    {
 
        for (PathNode point : list)
        {
            if (point.position.X == pathNode.position.X && point.position.Y==pathNode.position.Y)
            {
                return 1;
            }
        }
        return 0;
    }
    public static PathNode getInList (ArrayList<PathNode> list,PathNode pathNode)//ищет точку с такими же координатами в openSet
    {
        for (PathNode point : list)
        {
            if (point.position.X == pathNode.position.X && point.position.Y==pathNode.position.Y) {
 
                return point;
            }
        }
        return null;
    }
 
    public static ArrayList<Point> GetPath (PathNode pathNode)//возвращает список точек до данной.
    {
        ArrayList<Point> result = new ArrayList<>();
        PathNode current = pathNode;
        while (current!=null)
        {
            result.add(new Point(current.X,current.Y));
            current = current.CameFrome;
        }
        return result;
    }
 
 
    public static PathNode minLength (ArrayList<PathNode> set)//находит точку с min "Полным путем"
    {
        PathNode result = set.get(0);
        for (PathNode min : set)
        {
            if (min.FullLength<result.getFullLength())
            {
                result = min;
            }
        }
        return result;
    }
}
Сама я нашел реализацию на С# и переделал на java. Но похоже, что криво переделал.

Добавлено через 24 минуты
Пожалуйста, помогите найти ошибку
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.11.2015, 14:16
Ответы с готовыми решениями:

Поиск кратчайшего пути в лабиринте. Выход за границы массива
Собственно сабж. При лабиринте, например, 4х4 или 5х5 программа работает верно. А если пытаюсь...

Рекурсия поиска кратчайшего пути в двумерном массиве
пример массива (ходить можно только по точкам, S- начало, F- конец) # # # # # # # # # # # . ....

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

Поиск кратчайшего пути в лабиринте
Пишу программу для нахождения (и вывода) кратчашего пути в лабиринте, заданном в текстовом файле в...

2
0 / 0 / 0
Регистрация: 26.03.2018
Сообщений: 1
26.03.2018, 20:41 2
Много искал нормальную реализацию А* на джаве, спасибо тебе)))). А по поводу что долго ищет, у тебя эвристика не правильная. Наоборот надо вычислять манхетанское растояние.
Поменяй:
LengthToGoal = Math.abs(goal.X - this.position.X) + Math.abs(goal.Y - this.position.Y);
на:
LengthToGoal = Math.abs(this.position.X - goal.X ) + Math.abs(this.position.Y - goal.Y);

Ну по крайней мере тут так написано:https://neerc.ifmo.ru/wiki/ind... 2%D0%BC_A*
=)
0
2 / 2 / 1
Регистрация: 24.01.2018
Сообщений: 8
29.03.2018, 12:23 3
Поменяй:
LengthToGoal = Math.abs(goal.X - this.position.X) + Math.abs(goal.Y - this.position.Y);
на:
LengthToGoal = Math.abs(this.position.X - goal.X ) + Math.abs(this.position.Y - goal.Y);
В чем разница, если берется модуль вычитания?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.03.2018, 12:23

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

Поиск кратчайшего пути в лабиринте
Добрый день, знаю два алгоритма. 1. А - стар 2. Волновой Нужен какой нибудь 3... Ссылки...

Поиск пути в лабиринте. Маршрутный алгоритм
Доброго времени суток! Получил задание от препода. Необходимо написать программу поиска пути в...

Поиск кратчайшего пути (алгоритм Уоршала)
В области имеется N городов, соединены автобусными маршрутами. Стоимость билета с i-го города в j-й...

Алгоритм Флойда (графы - поиск кратчайшего пути)
Собственно очень нужен алгоритм на VBA. Народ если кто то видел, или у кого то есть, поделитесь...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.