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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ В двумерном динамическом массиве найти максимум в каждой строке http://www.cyberforum.ru/cpp-beginners/thread1222439.html
В двумерном динамическом массиве найти максимум в каждой строке. Функции реализовать, как шаблоны Заранее спасибо!
C++ Конструктор, деструктор: теория 1.Что такое конструктор инициализации чем он отличается от других ? 2.В каком случае нужно создать в классе деструктор? http://www.cyberforum.ru/cpp-beginners/thread1222437.html
Как отобразить в блок схеме действие C++
Как отобразить в блок схеме действие: цифра -> решение (да или нет), цифра -> решение(да или нет)..... без лимита ввода цифр
Изменить внешний вид текстового редактора C++
Привет всем, нужна ваша помощь, пишу курсовую, текстовый редактор, всю активную часть я сделал, осталось графическое оформление, я хотел бы сделать в окне, где пользователь вводит свой текст, такое оформление : обычный синий фоновый экран и рамочка, прямо как в Borland C++ for DOS, вот только не знаю как сделать, я нашел чужую программу, в которой это реализовано, но я не могу разобраться, может...
C++ Соединить обе строки и выделить подстроку заключенную между символами ' -' http://www.cyberforum.ru/cpp-beginners/thread1222420.html
Задача : Текст в файле : "Если душа родилась крылатой -что ей хоромы -и что ей хаты !" Используя функции обработки строковых и символьных переменных ,соединить обе строки и выделить подстроку заключенную между символами ' -'. Требования : 1) Подготовить текстовый файл с входными данными в редакторе . 2) Составить алгоритм программы. 3) Выделить функции ввода , обработки и вывода . ...
C++ Cтруктура "Знаки Зодиака". В файле структура-знаки Зодиака. Структура с полями:фамилия,год рождения,Знак Зодиака Ввести с клавиатуры знак Зодиака Найти в файле запись с таким знаком и вывести его. Прокоментируйте каждую строчку пожалуйста . подробнее

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

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; 
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 07:14. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru