Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.73/11: Рейтинг темы: голосов - 11, средняя оценка - 4.73
2 / 2 / 1
Регистрация: 16.04.2013
Сообщений: 45
1

Волновой алгоритм

11.12.2013, 15:32. Показов 2170. Ответов 20
Метки нет (Все метки)

Нужно найти кратчайший путь в лабиринте размерностью 10х10 , и выводить ответ. Помогите
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.12.2013, 15:32
Ответы с готовыми решениями:

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; void lab...

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

Волновой алгоритм
Подскажите пожалуйста, на сколько сложно изготовить из матрицы 0000 0000 0000 напр.4345 3234...

Волновой алгоритм
Скажите почему программа зацикливается. #include<bits/stdc++.h> using namespace std; int a =...

20
60 / 60 / 19
Регистрация: 11.07.2013
Сообщений: 304
11.12.2013, 15:51 2
В каком лабиринте?... Где лабиринт?
0
0 / 0 / 0
Регистрация: 25.10.2020
Сообщений: 10
25.10.2020, 13:45 3
Здравствуйте. Нужно найти путь в матрице размерностью 10х10 , и выводить ответ Да если путь существует. Нужно использовать очередь и волновой алгоритм. Помогите пожалуйста.
0
55 / 45 / 14
Регистрация: 23.02.2016
Сообщений: 379
25.10.2020, 14:00 4
gaggag11, AkmaL96, вы один человек?) С чем сложности конкретно?
0
0 / 0 / 0
Регистрация: 25.10.2020
Сообщений: 10
25.10.2020, 14:03 5
нет просто написал под постом)) эта новая тема и не представляю как реализовать(((
0
55 / 45 / 14
Регистрация: 23.02.2016
Сообщений: 379
25.10.2020, 14:05 6
gaggag11, там всяко разно можно, например так можно сделать.
Алгоритм состоит из двух этапов -- распространение волны (ниже это forward) и восстановление пути (ниже это reverse).

C++
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
209
210
211
212
213
214
215
216
217
218
219
220
221
#include <iostream>
#include <vector>
#include <deque>
#include <ctime>
 
using std::cout;
using std::vector;
using std::deque;
 
#define W 10
#define H 10
#define st -3
#define fn -4
 
enum Stage { forward, reverse };
 
vector<int> left(vector<int> Point, int map[W][H], Stage switch_on, bool &stop, bool &priority) {
    vector<int> newPoint(3);
    int i = Point[0], j = Point[1], k = Point[2];
    switch (switch_on) {
 
    case forward:
        if (j != 0 && map[i][j - 1] == -1) { newPoint = { i, j - 1, k + 1 }; map[i][j - 1] = k + 1; }
        else if (j != 0 && map[i][j - 1] == fn) { newPoint = { i, j - 1, k + 1 }; stop = true; priority = true; }
        else { newPoint = { -1, -1, -1 }; }
        break;
 
    case reverse:
        if (j == 0) newPoint = { -1, -1, -1 };
        else if (map[i][j - 1] == k - 1) newPoint = { i, j - 1, k - 1 };
        else newPoint = { -1, -1, -1 };
        break;
 
    default:
        break;
    }
 
    return newPoint;
}
 
vector<int> right(vector<int> Point, int map[W][H], Stage switch_on, bool &stop, bool &priority) {
    vector<int> newPoint(3);
    int i = Point[0], j = Point[1], k = Point[2];
    switch (switch_on) {
 
    case forward:
        if (j != H - 1 && map[i][j + 1] == -1) { newPoint = { i, j + 1, k + 1 }; map[i][j + 1] = k + 1; }
        else if (j != H - 1 && map[i][j + 1] == fn) { newPoint = { i, j + 1, k + 1 }; stop = true; priority = true; }
        else { newPoint = { -1, -1, -1 }; }
        break;
 
    case reverse:
        if (j == H - 1) newPoint = { -1, -1, -1 };
        else if (map[i][j + 1] == k - 1) newPoint = { i, j + 1, k - 1 };
        else newPoint = { -1, -1, -1 };
        break;
 
    default:
        break;
    }
 
    return newPoint;
}
 
vector<int> up(vector<int> Point, int map[W][H], Stage switch_on, bool &stop, bool &priority) {
    vector<int> newPoint(3);
    int i = Point[0], j = Point[1], k = Point[2];
    switch (switch_on) {
 
    case forward:
        if (i != 0 && map[i - 1][j] == -1) { newPoint = { i - 1, j, k + 1 }; map[i - 1][j] = k + 1; }
        else if (i != 0 && map[i - 1][j] == fn) { newPoint = { i - 1, j, k + 1 }; stop = true; priority = true; }
        else { newPoint = { -1, -1, -1 }; }
        break;
 
    case reverse:
        if (i == 0) newPoint = { -1, -1, -1 };
        else if (map[i - 1][j] == k - 1) newPoint = { i - 1, j, k - 1 };
        else newPoint = { -1, -1, -1 };
        break;
 
    default:
        break;
    }
 
    return newPoint;
}
 
vector<int> down(vector<int> Point, int map[W][H], Stage switch_on, bool &stop, bool &priority) {
    vector<int> newPoint(3);
    int i = Point[0], j = Point[1], k = Point[2];
    switch (switch_on) {
 
    case forward:
        if (i != W - 1 && map[i + 1][j] == -1) { newPoint = { i + 1, j, k + 1 }; map[i + 1][j] = k + 1; }
        else if (i != W - 1 && map[i + 1][j] == fn) { newPoint = { i + 1, j, k + 1 }; stop = true; priority = true; }
        else { newPoint = { -1, -1, -1 }; }
        break;
 
    case reverse:
        if (i == W - 1) newPoint = { -1, -1, -1 };
        else if (map[i + 1][j] == k - 1) newPoint = { i + 1, j, k - 1 };
        else newPoint = { -1, -1, -1 };
        break;
 
    default:
        break;
    }
 
    return newPoint;
}
 
int main() {
 
    vector<int> Start = { 1, 2, 0 };
    vector<int> End = { 18, 19, 0 };
    deque<vector<int>> tmpPoint;
    tmpPoint = { Start };
 
    int map[W][H];
    srand(time(0));
    for (int i = 0; i < W; i++) {
        for (int j = 0; j < H; j++) {
            map[i][j] = -1;
        }
    }
 
    /*Задание препятствий*/
    int obstacle = 200;
    while (obstacle > 0) {
        int i = rand() % W;
        int j = rand() % H;
        map[i][j] = -2;
        obstacle--;
    }
 
    map[Start[0]][Start[1]] = st;
    map[End[0]][End[1]] = fn;
 
    /*Начало замера времени*/
    clock_t startTime = clock();
 
    bool stop = false, dock = false, priority = false;
    int i = 0;
 
    /*Прямой путь*/
    vector<int> tmp(3);
    while (!stop) {
        tmp = left(tmpPoint[i], map, forward, stop, priority);
        if (tmp[0] != -1) tmpPoint.push_back(tmp);
 
        tmp = up(tmpPoint[i], map, forward, stop, priority);
        if (tmp[0] != -1) tmpPoint.push_back(tmp);
 
        tmp = right(tmpPoint[i], map, forward, stop, priority);
        if (tmp[0] != -1) tmpPoint.push_back(tmp);
 
        tmp = down(tmpPoint[i], map, forward, stop, priority);
        if (tmp[0] != -1) tmpPoint.push_back(tmp);
 
        tmpPoint.pop_front();
        if (tmpPoint.size() == 0) { dock = true; break; } // тупик
    }
 
    if (!dock) {
        /*Поставили на цель номер волны*/
        if (priority) End[2] = tmpPoint[tmpPoint.size() - 1][2] + 1;
        else End[2] = tmpPoint[tmpPoint.size() - 1][2];
 
        /*Очистили вектор и добавили цель*/
        tmpPoint.clear();
        tmpPoint.push_back(End);
 
        /*Обратный путь*/
        i = End[2];
        while (i > 0) {
            i--;
            vector<int> tmp(3);
 
            tmp = left(tmpPoint[tmpPoint.size() - 1], map, reverse, stop, priority);
            if (tmp[0] == -1) { ; }
            else {
                tmpPoint.push_back(tmp);
                continue;
            }
 
            tmp = up(tmpPoint[tmpPoint.size() - 1], map, reverse, stop, priority);
            if (tmp[0] == -1) { ; }
            else {
                tmpPoint.push_back(tmp);
                continue;
            }
 
            tmp = right(tmpPoint[tmpPoint.size() - 1], map, reverse, stop, priority);
            if (tmp[0] == -1) { ; }
            else {
                tmpPoint.push_back(tmp);
                continue;
            }
 
            tmp = down(tmpPoint[tmpPoint.size() - 1], map, reverse, stop, priority);
            if (tmp[0] == -1) { ; }
            else {
                tmpPoint.push_back(tmp);
                continue;
            }
        }
    }
    else cout << "\nDock Lee! " << "\n";
 
    /*Конец замера времени*/
    clock_t endTime = clock();
 
 
    double seconds = endTime - startTime;
    cout << "\nSeconds: " << seconds << "\n";
    cout << "\nSeconds: " << seconds / CLOCKS_PER_SEC << "\n";
 
    system("pause");
    return 0;
}
1
0 / 0 / 0
Регистрация: 25.10.2020
Сообщений: 10
25.10.2020, 14:09 7
#define W 10
#define H 10
#define st -3
#define fn -4
#include <deque>
#include <ctime> не проходили еще

новая тема queue. нужно максимально просто ))
0
Nishen
25.10.2020, 14:16
  #8

Не по теме:

Цитата Сообщение от gaggag11 Посмотреть сообщение
не проходили еще
Смотри в армии так не скажи... :D

0
55 / 45 / 14
Регистрация: 23.02.2016
Сообщений: 379
25.10.2020, 14:36 9
gaggag11, ситайм это для того, чтобы препятствия генерировать рандомно (при неоднократном запуске программы), а не руками выставлять, то есть она нужна лишь для строки
C++
1
srand(time(0));
#define W 10 -- это WIDTH строк
#define H 10 -- это HEIGHT столбцов
#define st -3 -- число, обозначающее start
#define fn -4 -- число, обозначающее final, finish и т.п.
#include <deque> дек это умная очередь, думаю если просто очередь поставить ничего не изменится.

map -- это наша карта, на которой мы ищем путь.
То есть
C++
1
2
3
4
5
6
7
int map[W][H];
    srand(time(0));
    for (int i = 0; i < W; i++) {
        for (int j = 0; j < H; j++) {
            map[i][j] = -1;
        }
    }
числом -1 обозначается пустая клетка в матрице width x height, а препятствия задаются рандомно
C++
1
2
3
4
5
6
7
8
/*Задание препятствий*/
    int obstacle = 200;
    while (obstacle > 0) {
        int i = rand() % W;
        int j = rand() % H;
        map[i][j] = -2;
        obstacle--;
    }
и обозначаются числом -2, именно для этого <ctime> и инклудится.
На этом моменте мы лишь имеем карту с проходимыми и непроходимыми клетками/полями.
Далее задаем начальную точку и конечную или как обычно говорят старт и цель.
C++
1
2
map[Start[0]][Start[1]] = st;
map[End[0]][End[1]] = fn;
Вот это map[Start[0]][Start[1]] это по сути map[row][col] = st, но чуть более хитро -- точка задаётся 3-ёх компонентным вектором {i, j, k}, где i - это row/строка, j - это col/столбец(колонка) и k - это номер волны/волнового фронта.
У меня изначально карта была 20x20, поэтому вам тут поправить надо будет
C++
1
2
vector<int> Start = { 1, 2, 0 };
vector<int> End = { 18, 19, 0 };
Например, на
C++
1
2
vector<int> Start = { 1, 2, 0 };
vector<int> End = { 8, 9, 0 };
То есть начало и конец задаются вручную.
0
0 / 0 / 0
Регистрация: 25.10.2020
Сообщений: 10
25.10.2020, 14:43 10
0 1 0 0 0 0 0 0 0 0
0 1 0 0 1 0 1 0 0 0
0 1 1 1 1 0 1 1 1 0
0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 0 1 1 1 0
0 1 0 0 0 0 0 0 0 0
0 1 1 1 1 1 0 1 1 1
0 1 1 1 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0
1 1 1 1 0 0 0 0 0 0

при входе нам будет дана такая матрица с0 и 1 у нужно получить "да" если путь есть и "нет" если его нет.
0
55 / 45 / 14
Регистрация: 23.02.2016
Сообщений: 379
25.10.2020, 14:47 11
gaggag11, также подредактируйте под свою размерность карты количество препятствий, у меня карта была 20 на 20, и препятствий было 50% грубо говоря
C++
1
int obstacle = 200;
Можете тоже 50% сделать
C++
1
int obstacle = 50; // (W*H / 100) * number %
Добавлено через 1 минуту
gaggag11, вот видите, 1 непроходимая клетка у вас, а 0 проходимая клетка. Вот надо было сразу про это и писать)
0
0 / 0 / 0
Регистрация: 25.10.2020
Сообщений: 10
25.10.2020, 14:56 12
так как у нас начало это левый верхний угол(будет 0 точно) у конец правый нижний угол(0) можно первый элемент очереди задать arr[0,0] , а потом проверять есть ли путь если пойти 1 шаг вдеред, назад , направо или налево и добавить в очередь те координаты где нет 1?где 0?
0
55 / 45 / 14
Регистрация: 23.02.2016
Сообщений: 379
25.10.2020, 15:05 13
gaggag11,
Цитата Сообщение от gaggag11 Посмотреть сообщение
так как у нас начало это левый верхний угол(будет 0 точно)
на вашей карте
Код
0 1 0 0 0 0 0 0 0 0
0 1 0 0 1 0 1 0 0 0
0 1 1 1 1 0 1 1 1 0
0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 0 1 1 1 0
0 1 0 0 0 0 0 0 0 0
0 1 1 1 1 1 0 1 1 1
0 1 1 1 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0
1 1 1 1 0 0 0 0 0 0
лично я не вижу ни начала, ни конца. Каким числом вы обозначаете начало, а каким конец? По вашей карте любому программисту очевидно, что 0 и 1 -- это два состояния клетки, проходимая она или же нет. Но где тут начало, а где конец неизвестно -- они не обозначены на карте.
0
0 / 0 / 0
Регистрация: 25.10.2020
Сообщений: 10
25.10.2020, 15:12 14
в задаче дано что конец левых верхний угол, а конец правый нижний. это условие задачи.

Добавлено через 1 минуту
начало* левый верхний
0
55 / 45 / 14
Регистрация: 23.02.2016
Сообщений: 379
25.10.2020, 15:29 15
gaggag11, ясно
Цитата Сообщение от gaggag11 Посмотреть сообщение
в задаче дано что конец левых верхний угол, а конец правый нижний. это условие задачи.
Цитата Сообщение от Timurs Посмотреть сообщение
gaggag11, вот видите, 1 непроходимая клетка у вас, а 0 проходимая клетка. Вот надо было сразу про это и писать)
надо было тоже сразу писать, как остальные то должны догадаться, что там в задаче дано.

Цитата Сообщение от gaggag11 Посмотреть сообщение
можно первый элемент очереди задать arr[0,0]
ок, задали.
Цитата Сообщение от gaggag11 Посмотреть сообщение
а потом проверять есть ли путь если пойти 1 шаг вдеред, назад , направо или налево и добавить в очередь те координаты где нет 1?где 0?
ок, добавили в очередь клетку, в которую можно шагнуть.
Следующая клетка в очереди у вас теперь arr[1,0], верхняя клетка arr[0,0] свободна, опять её добавите? Это собственно к чему, вы понимаете, что вы так бесконечно будете ходить туда-сюда) В волновом алгоритме после прохождения волны состояние карты изменяется.
0
0 / 0 / 0
Регистрация: 25.10.2020
Сообщений: 10
25.10.2020, 15:34 16
вот я и хочу принцип понять, чтобы реализовать. мы пока что не проходили % итд поэтому я много чего не понимаю в коде выше) хочу принцип понять чтобы суметь написать код лишь при помощи queue u wave algorithm.)
0
55 / 45 / 14
Регистрация: 23.02.2016
Сообщений: 379
25.10.2020, 15:49 17
gaggag11, так весь принцип и состоит в том, что есть начало обозначьте на карте эту начальную точку каким-то числом, чтобы понимать собственно что это начало, аналогично с целевой точкой (можно конечно и по координатам сделать типа 00 или 99, но не знаю, такое себе), затем одну волну пустили, обозначили на карте, что вот была пущена первая волна и первый шаг можно сделать в такие-то клетки, то есть в эти клетки записали какое-то число, по которому вы поймете, что тут был первый фронт волны. И так далее пока не доберетесь до цели или не заполните все клетки карты номерами фронтов волны, если это возможно, есть случай тупика ещё. Первый шаг алгоритма будет сделан. Далее обратный процесс -- от конца к началу.
1
0 / 0 / 0
Регистрация: 25.10.2020
Сообщений: 10
25.10.2020, 15:52 18
спасибо большое
0
55 / 45 / 14
Регистрация: 23.02.2016
Сообщений: 379
25.10.2020, 16:16 19
gaggag11, пишите код, посмотрим. Когда вы запишите в клетку номер фронта волны, например первый фронт, логично его и обозначить числом 1, но единицей уже обозначены препятствия, поэтому не знаю, вроде бы никто так не обозначает непроходимые клетки, но раз так, то попробуйте волны обозначать через декремент, то есть первая волна это -1, вторая -2, ну и так далее -3, -4, -5, ... -n. Когда у вас клетка обозначена каким-то числом, то это число уже показывает состояние клетки, что она уже не 0, не пустая, что вы уже там были и повторно её вносить в очередь не следует.

p.s. также сразу проверяйте клетки против часовой стрелки лучше (ну или по часовой), а не хаотично, тоже хорошим тоном считается насколько понимаю.

Добавлено через 17 минут
gaggag11,
Цитата Сообщение от gaggag11 Посмотреть сообщение
мы пока что не проходили % итд
а вот это если честно какой-то позор, когда учился нам это на первой лабе давали либо имелось ввиду, что сами ознакомимся. Это обычная операция, несколько умнее того же умножения или сложения, берет остаток от деления на какое-то число, например x % 10 это будет одно из чисел {0,1,2,3,4,5,6,7,8,9}. Имеет смысл по идее для целых чисел только, так как вещественные числа делятся друг на друга без всяких остатков, но и для них бывают определяют эту операцию по тем или иным соображениям (читать надо).
C++
1
rand() % W
когда W это 10 будет
C++
1
rand() % 10
. Функция rand() возвращает какое-то число. Если прям интересно по какому алгоритму она его возвращает, то не подскажу, но вроде по этому https://ru.wikipedia.org/wiki/... 0%BE%D0%B4
1
0 / 0 / 0
Регистрация: 25.10.2020
Сообщений: 10
25.10.2020, 23:46 20
спасибо ))
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.10.2020, 23:46

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

Волновой алгоритм
Нужно реализовать волновой алгоритм поиска кратчайшего пути на поле 20*20, причем координаты начала...

Волновой алгоритм
Доброго времени суток, дорогие форумчане. Никак не додумаю волновой алгоритм, помогите, кто чем...

Лабиринт - волновой алгоритм
Помогите пожалуйста. Я написал код, который мне выведет на экран кратчайший путь... Но чего-то не...

Tiled Map и волновой алгоритм
Делаю игру пакман. Нашла, что для привидений хорошо подходит волновой алгоритм. Нашла примеры...


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

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

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