Рисунок 1 – Интерфейс программы
Символом «\\» на ней обозначены препятствия а пустые клетки (пробел) – проходимые участки. «S» и «F» старт и финиш. При необходимости можно изменить соответствия символов. Для этого необходимо нажать кнопку «Symbols» и задать соответствия.
Рисунок 2
Из рисунка видно, что для обозначения закрытой клетки (т.е. той где уже побывал робот) используется символ «$». Для анализа правильности прохождения пути в соответствии с алгоритмом, можно в поле Открытая клетка вместо двух пробелов (по умолчанию) внести любой символ, и тогда с каждым ходом будет видно какие еще открытые (доступные и проанализированные) клетки находятся в очереди робота. Лабиринт можно видоизменять. Для этого необходимо выделить нужную клетку и внести в нее изменения. При этом нужно учитывать специфику символов заданную в настройках символов и то, что стартовая и финишная вершины должны быть в единичном количестве.
Рисунок 3 Главное окно программы
Главное окно программы, представленное на рисунке 3. Оно состоит из таблицы, на которой отображается лабиринт и ходы робота и рабочей панели. На рабочей панели находится две группы кнопок. Верхняя BFS, DFS, Gradient – соответствуют трем варианта поиска пути: поиск в ширину, поиск в глубину и поиск по градиенту. Чуть ниже расположен checkbox StepByStep. При его активации поиск пути происходит в пошаговом режиме, т.е. в таблице отображается не сразу весь путь а по одному шагу. Пример пошагового выполнения поиска представлен на рисунке 4:
Рисунок 4 Пошаговый режим выполнения
Нижняя группа – служебные кнопки. Предназначена для настройки символов, очистки поля от сделанных шагов, «перезаливки» поля и выхода из программы. Настройка символов была рассмотрена в предыдущем пункте записки. Очистка поля от сделанных шагов используется после того как был завершен один из методов поиска пути для очистки поля от «следов» робота, ее целесообразно применять когда в лабиринт вносились изменения и не нужно их терять. Перезаливка поля используется для полного возвращения поля в исходное состояние, при этом убираются сделанные шаги, и убираются все изменения внесенные в лабиринт.
Алгоритм основан на последовательном переборе вариантов изменения начальной ситуации, начиная каждый раз с самого левого потомка. Исследуются дочерние решения до обнаружения целевой ситуации или тупика. В случае обнаружения тупика алгоритм осуществляет возврат к отцовской порождающей вершине и осуществляет попытку рассмотрения очередного варианта. Алгоритм заканчивается при отыскании любой из целевых вершин или когда не возможно найти решение (целевую вершину) или при обнаружении ситуации, в которой начальная вершина является тупиковой.
Для дерева вариантов использовался стек – «Первый зашёл, последний вышел», что позволяет просматривать решения в глубину.
Сначала вводим конфигурацию лабиринта. При этом необходимо пометить стартовую и финишную клетку и препятствия. При активации одного из методов поиска срабатывают функции поиска исходной и финишной вершин, их координаты запоминаются. Осуществляется поиск возможных ходов (слева на право) из стартовой вершины, при этом осуществляется ряд проверок: «не стена», «не открыта», «не целевая», «не исходная» и «не закрытая», возможные ходы помечаются как «открытые» и заносятся в стек либо в очередь либо в массив (в зависимости от типа поиска). Далее берется очередная вершина из очереди либо стека и если это поиск по градиенту, то вершина наиболее близкая к целевой, закрывается и в ней осуществляется поиск возможных ходов.
try
{
s = "";
stepCount = 0;
stI->Clear();
stJ->Clear();
findStart();
ScanUseDFS(startI,startJ);
if(chStep->Checked)MessageBox::Show("Step " + stepCount.ToString(),"ok");
while(stI->Count != 0 && s != "!")
{
mustCloseDFS(Convert::ToInt32(stI->Pop()), Convert::ToInt32(stJ->Pop()));
if(chStep->Checked)MessageBox::Show("Step " + stepCount.ToString(),"ok");
}
if(s == "!") MessageBox::Show("Решение найдено за " + stepCount.ToString() + " шагов!", "=)", MessageBoxButtons::OK, MessageBoxIcon::Information);
else MessageBox::Show("Решение не найдено!", "=(", MessageBoxButtons::OK, MessageBoxIcon::Information);
}
catch(Exception ^ ex)
{
MessageBox::Show("Ошибка! " + ex->Message, "Внимание!");
}
//Ищем возможные ходы для вершины, заносим их в стек для поиска в глубину
private: void ScanUseDFS(int i, int j)
{
stepCount++;
if(isFinish(i-1, j)) s = "!"; else if(canUse(i-1, j) && s != "!") {mustUse(i-1, j); stI->Push(i-1); stJ->Push(j);}
if(isFinish(i, j-1)) s = "!"; else if(canUse(i, j-1) && s != "!") {mustUse(i, j-1); stI->Push(i); stJ->Push(j-1);}
if(isFinish(i+1, j)) s = "!"; else if(canUse(i+1, j) && s != "!") {mustUse(i+1, j); stI->Push(i+1); stJ->Push(j);}
if(isFinish(i, j+1)) s = "!"; else if(canUse(i, j+1) && s != "!") {mustUse(i, j+1); stI->Push(i); stJ->Push(j+1);}
}
//Закрываем вершину, ищем возможные ходы с занесением их в стек для поиска в глубину
private: void mustCloseDFS(int i, int j)
{
if(!isNotUsed(i, j))
{
ScanUseDFS(i, j);
dgv->Rows[i]->Cells[j]->Value = sStep;
}
}
Поиск в ширину осуществляется следующим образом:
try
{
s = "";
quI->Clear();
quJ->Clear();
findStart();
ScanUseBFS(startI,startJ);
if(chStep->Checked)MessageBox::Show("Step " + stepCount.ToString(),"ok");
while(quI->Count != 0 && s != "!")
{
mustCloseBFS(Convert::ToInt32(quI->Dequeue()), Convert::ToInt32(quJ->Dequeue()));
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.