Форум программистов, компьютерный форум CyberForum.ru

Из Java в С++ (алгоритм А* для поиска кратчайшего пути до терминального состояния) - C++

Восстановить пароль Регистрация
 
bez
0 / 0 / 0
Регистрация: 04.07.2014
Сообщений: 83
04.07.2014, 12:39     Из Java в С++ (алгоритм А* для поиска кратчайшего пути до терминального состояния) #1
Помогите реализовать алгоритм *А для плюсов

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
package ru.dokwork.algorithms.astar; import java.util.*; /** * Реализует алгоритм поиска решения А*. */ 
public class Astar <TState extends State, TRules extends Rules<TState>> { 
/** * Применяет алгоритм А* для поиска крадчайшего пути до терминального 
* состояния от указанного. 
* * @param startState - начальное состояние. 
* @return последовательность состояний от заданного до терминального. 
*/ 
public Collection<State> search(TState startState) { 
LinkedList<TState> close = new LinkedList<TState>(); 
LinkedList<TState> open = new LinkedList<TState>(); 
open.add(startState); 
startState.setG(0); 
startState.setH(rules.getH(startState)); 
 
while (!open.isEmpty()) { 
TState x = getStateWithMinF(open); 
if (rules.isTerminate(x)) { 
closedStates = close.size(); 
return completeSolution(x); 
} 
open.remove(x); 
close.add(x);
 List<TState> neighbors = rules.getNeighbors(x); 
for (TState neighbor : neighbors) { 
if (close.contains(neighbor)) 
{ 
continue; 
} 
int g = x.getG() + rules.getDistance(x, neighbor); 
boolean isGBetter; 
if (!open.contains(neighbor)) { 
neighbor.setH(rules.getH(neighbor));
 open.add(neighbor); 
isGBetter = true; 
} 
else 
{ 
isGBetter = g < neighbor.getG(); 
} 
if (isGBetter) { 
neighbor.setParent(x);
 neighbor.setG(g); 
} 
} 
} 
return null; 
} 
/** * Создает объект для поиска терминального состояния по указанным правилам. 
* * @param rules правила, в соответствии с которыми будет производиться поиск 
* терминального состояния. 
*/ 
public Astar(TRules rules) { 
if (rules == null) 
{ 
throw new IllegalArgumentException("Rules can`t be null."); 
} 
this.rules = rules; 
} 
/** * Находит вершину в списке open с наименьшим значением веса. 
* * @param open список открытых вершин. * @return вершину с наименьшим весом. 
*/
 private TState getStateWithMinF(Collection<TState> open) 
{ 
TState res = null; 
int min = Integer.MAX_VALUE; 
for (TState state : open) 
{ 
if (state.getF() < min) 
{ 
min = state.getF(); 
res = state; 
} 
} 
return res; 
} 
/** * Составляет последовательность состояний пройденных от начального 
* состояния до конечного. 
* * @param terminate найденное конечное состояние. 
* @return последовательность состояний пройденных от начального 
* состояния до конечного. 
*/ 
private Collection<State> completeSolution(TState terminate) 
{ 
Deque<TSate> path = new LinkedList<TState>(); 
State c = terminate; 
while (c != null) 
{ 
path.addFirst(c); 
c = c.getParent(); 
} 
return path; 
} 
private TRules rules; 
}
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
actions = new int[] {-sideSize, sideSize, -1, 1}; 
/* Выполняется поиск пустой клетки */ 
int zero = 0; 
for (; zero < field.length; zero++) 
{ 
if (field[zero] == 0) 
{ 
break; 
} 
if (zero >= field.length) 
{ 
return null; 
} 
} 
/* Вычисляется индекс перемещаемой клетки */ 
int number = zero + action; 
/* Проверяется допустимость хода */ 
if (number < 0 || number >= field.length) 
{ 
return null; 
}
 if ((action == 1) && ((zero + 1) % sideSize == 0)) 
{ 
return null; 
}
 if ((action == -1) && ((zero + 1) % sideSize == 1)) 
{ 
return null; 
} 
/* * Создается новый экземпляр поля, на котором меняются местами пустая и 
* перемещаемая клетки */ 
byte[] newField = Arrays.copyOf(field, field.length);
 byte temp = newField[zero]; 
newField[zero] = newField[number];
 newField[number] = temp;
 return newField;
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
byte[] generateStartState(FifteenRules rules, int swapCount) { 
int stepCount = swapCount; 
byte[] startState = rules.getTerminateState();
 int[] actions = rules.getActions(); 
Random r = new Random(); 
while (stepCount > 0) 
{
 int j = r.nextInt(actions.length);
 byte[] state = rules.doAction(startState, actions[j]);
 if (state != null) 
{ 
startState = state; stepCount--; 
} 
} 
return startState; 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.07.2014, 12:39     Из Java в С++ (алгоритм А* для поиска кратчайшего пути до терминального состояния)
Посмотрите здесь:

C++ Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе
C++ Разработать алгоритм и программу для определения кратчайшего слова в тексте
Волновой алгоритм поиска пути C++
Нахождение кратчайшего пути в графе, алгоритм Уоршелла C++
Подкиньте линк на готовую библиотеку для прокладки кратчайшего пути от кубика А до кубика Б C++
C++ Алгоритм поиска пути в лабиринте, заданном связным графом
C++ Нахождение кратчайшего пути
Поиск кратчайшего пути на графе C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 19:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru