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

Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом.

25.12.2009, 17:33. Просмотров 4070. Ответов 4
Метки нет (Все метки)

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

Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом.
Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом.

Какими методами лучше реализовать генерацию и поиск выхода из лабиринта?
Нужно сделать генерацию рандомнго лабиринта, и поиск выхода с него на С++. Подскажите пожалуйста...

Программа поиска выхода из лабиринта
Программа не заходит в цикл(pyt) для поиска пути в направлениях,при запуске пишет no, а если...

Поиск выхода из лабиринта
Здравствуйте! Изучаю C#, застрял на одном моменте в задании. Суть такова: нужно найти выход из...

4
эволюционирую потихоньку
468 / 466 / 91
Регистрация: 30.06.2009
Сообщений: 1,401
25.12.2009, 17:53 2
алгоритм простой.
1) определяешь все возможные направления движения
2) если после п.1 больше одного варианта движения, шагаешь в любую сторону остальные заносишь в буфер, и вновь п.1
если один вариант шагаешь по этому маршруту и п.1
если вариантов ноль, читаешь последный вариант из буфера и п.1
если вариантов ноль и буфер пуст, а цель не достигнута, то время паниковать
0
0 / 0 / 0
Регистрация: 22.12.2009
Сообщений: 11
25.12.2009, 18:19  [ТС] 3
хочу примерный код
0
эволюционирую потихоньку
468 / 466 / 91
Регистрация: 30.06.2009
Сообщений: 1,401
25.12.2009, 18:25 4
Цитата Сообщение от SNROK Посмотреть сообщение
хочу примерный код
а я хочу медленно потягивать коньяк сидя в кресло-качалке у камина в своём особняке и чтобы шкура белого медведя на полу. и кому щас легко?
0
0 / 0 / 0
Регистрация: 22.12.2009
Сообщений: 11
25.12.2009, 18:36  [ТС] 5
Pascal
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
const max_graf = 100;(максимальное число комнат в лабиринте}
type list =^elem;
         elem = record
                            num : integer;
                            next : list;
                      end;
var
Graf: array [1. . rnax_graf] of elem;
ref: list;
       n, i, a : integer;
       goal, go_on : boolean; {признаки достижения цели и необходимости продолжения}
      beg_num,end_num : integer;
      beg_st, end_st, elem_st : list; { начало, конец и элемент стека }
. . .
Procedure CreateGraf(n:integer);
{чтение исходных данных из текстового файла и формирование графа}
var
        sosed, sosed1 : list;
begin
        for i:=l to n do
          begin
                     new(sosed);
                     graf[i].next := sosed;
                    repeat
                              Readln(inf,a) ;
                              sosed^.num := a;
                              if а<>0 then
                              begin
                                         new(sosed1);
                                         sosed^.next := sosed1;
                                         sosed := sosed1
                              end
                    until a=0
          end
end;
 
  Формирование маршрута ведется с использованием стека. Процедуры Add и Del предназначены соответственно для добавления и удаления элементов стека.
 
Procedure Add (num: integer; var beg_st : list );
{ добавление элемента к стеку }
var
          elem_st : list;
begin
          new(elem_st); { выделили память под следующий элемент стека}
          elem_st^.next:=beg_st; {присоединили новый элемент к стеку }
                 elem_st^.num:=num; {занесли информацию)
                 beg_st:=elem_st {установили указатель на новое начало стека}
end;
 
Procedure Del (var begin_st : list ) ;
{ удалить элемент из стека }
var
        elem_st : list;
begin
        elem_st:=beg_st;
        beg_st:=beg_st^.next; { переносим указатель начала (вершины) стека на второй элемент}
        Dispose(elem_st) { освобождаем память, уничтожив первый элемент}
end;
 
  Основное действие алгоритма — это обработка очередной вершины графа, в результате чего мы либо добавляем к маршруту новую вершину, либо возвращаемся в предыдущую. Порядок просмотра соседей определяется порядком следования полей-ссылок в перечне вершин-соседей, который соответствует одной записи в текстовом файле.
 
Procedure Way (num_begin, num_end : integer); { номера вершин начала и конца пути }
var
      num : integer; { номер текущей вершины }
      flag : boolean; { признак необходимости продолжения пути }
begin
      Graf [num_begin] .num : = 1; { начальный этап }
      Add (num_begin, beg_st) ; {поместили начало пути в. стек }
      flag := true; {нужно продолжать построение пути }
      while flag and (not goal) do { строим очередной фронт }
      begin
             num := beg_st^.num ;
             { берем значение вершины стека }
             ref := graf [num].next;
          go_on := false; {признак того, что путь увеличился}
             repeat
                     a: =ref^ .num;
                     if а<>0 then
                             begin
                                        {обработка очередного соседа}
                                        if Graf[a]. num=0 {пометить вершину следующим фронтом}
                                        then begin
                                                      Graf [a].num := 1;
                                                      Add(a, beg_st) ;
                                                    go_on := true; {путь увеличился на шаг}
                                        end
 
                               else
                                       ref := ref^.next { переходим к следующему соседу }
                             end;
            until (a=0) or (go_on);
                 if Graf [num_end].num<>0 then goal :=true { дошли до цели. }
                  else
                    if not go_on then
                        begin
                             del (beg_st) ;
                             if beg_st=end_st then flag:=false
                                { стек пуст, задача неразрешима }
                        end
      end
end;
 
  Теперь программу поиска маршрута можно записать так (структура графа считывается из текстового файла):
 
program BackTracking;
. . .
begin
        for i:=1 to Max_Graf do Graf [i].num :=0;
        assign (inf, 'graf.txt');
        { в файле приведен пример, разобранный в тексте (рис.3)}
        reset (inf);
        readln (inf,n); { число вершин графа }
        CreateGraf (n) ;
        close (inf) ;
        new (elem_st) ; { инициализация стека }
        beg_st:=elem_st; { стек пока пуст,}
        end_st:=elem_st; { призак этого: beg_st = end_st}
        goal := false;
        Writeln;
        Writeln('Введите номер начальной и конечной вершины'};
        Readln (beg_num, end_num) ;
        Way (beg_num, end_num) ;
        if goal then
            { построение и печать маршрута }
      . . .
end.
как это на C++?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.12.2009, 18:36

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

Поиск выхода из лабиринта
Необходимо реализовать поиск выхода из лабиринта вот допустим лабиринт,но тут он выводит только...

Поиск выхода из лабиринта
Доброго времени суток! Помогите написать процедуру использующую стек для отыскания прохода по...

Поиск выхода из лабиринта
Здравствуйте! Изучаю C#, застрял на одном моменте в задании. Суть такова: нужно найти выход из...

Поиск выхода из лабиринта
Такой вопрос. почему у меня не находит выход из лабиринта? предположительно ошибка в функции Solve...


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

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

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