Предложите как избежать зацикливания в методе перебора
Перейти к содержимому

Предложите как избежать зацикливания в методе перебора

  • автор:

Предложите как избежать зацикливания в методе перебора

Для представления задач используются графы пространства состояний. Две вершины графа связаны ребром, если существует некоторое правило перехода (move) , согласно которому производится преобразование одного состояния в другое. Решение задачи состоит в поиске пути из заданного начального состояния в состояние, соответсвующее искомому решению посредством применения последовательности правил перехода.

Базовая программа для решения задач путем поиска на графах пространства состяний с применением поиска в глубину.

Переходы между состояниями будут описываться с помощью бинарного предиката move(State, Move), где

Move – правило перехода, которое применяется к состоянию State (состояние)

Предикат update(State, Move, State1) – используется для поиска состояния state1, достижимого из State с помощью правила Move.

Допустимость возможных переходов оценивается предикатом legal (State).

Для того, чтобы избежать зацикливания, программа сохраняет список ранее пройденных состояний. Последовательность переходов из начального состояния в конечное строится путем наращивания в 3 аргументе предиката solve_dfs.

Чтобы использовать базовую программу для решения конкретной задачи необходимо задать представление состояний и определить процедуры move, update, legal.

Solve_dfs (State, History,[ ]): — final_ state (State) – граничный предикат

Solve_dfs (State, History,[Move|Moves]): —

Move (State, Move), update (State, Move, State1),

Legal (State1), — получилось ли допустимое состояние

Not (member (State1, History)), – проверка на допустимость и входит ли в список ранее

Solve_dfs (State1, [State1| History], Moves).Предложение для тестрования базовой программы:

Применим ее при решении задачи о волке, козе и капусте. Состояние представляется тройкой — wgc(B,L,R), где В-местонахождение лодки (левый или правый берег), L- список находящихся на левом берегу,R- список находящихся на правом берегу. Начальным и конечным состояниями являются

W – волк, g – коза, c – капуста

B –место нахождения лодки (лево или право)

L – список находящихся на левом берегу

R — список находящихся на правом берегу

Wgc (left(wolf, goat, cаbbage), [])

Wgc (right, [], (wolf, goat, cabbage)) – конечное состояние. Использование двух списков упрощает описание переходов. Для проверки зацикливания удобно сохраняь списки обитателей в отсортированном виде: волк всегда будет в списке перед козой и оба перед капустой. Переходы между состояниями – это перевозка обитателей с одного берега на другой и их можно определить с указанием кого везем. Того кого везем, будем называть грузом (cargo). Ситуация, когда фермер едет в лодке один определяется грузом Alone.

Все возможные переходы классифицируются в 3 предложения:

  • перевозки слева направо
  • перевозки справа налево
  • одиночное плавание в любом направлении

Для каждого из указанных переходов определим предикат или процедуру:

Update_bоat – изменяет положение лодки

Update_banks – изменяет состав обитателей берегов

Предикат select дает описание процедур перемещения, предикат Update_banks – поддерживает список обитателей в упорядоченном виде и облегчает проверку на зацикливание. Проверка допустимости переходов делается двумя предикатами:

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

Как избежать зацикливания в методе перебора?? Даю 100баллов.

nika240409

Чтобы предотвратить зацикливание, нужно его обнаружить. Один из способов — создание хэш-таблицы, в которой после посещения страницы v устанавливается hash[v] = true.

Новые вопросы в Информатика

В чем преимущество трассировки алгоритма по сравнению с блок-схемой? ​
адресація клітини це

ЗАДАНИЯ: 1. Даны два числа а и b. Напишите программу вычисления с условием, если число b меньше а, заменяет b нулем, в противном случае оставляет b … без изменени

3. Напишите программу, в которой вычисляется сумма цифр а и b, если данное целое число a делится без остатка на целое число b, не равное нулю, в проти … вном случае вычисляется их произведение

Може додавати дописи, але не може змінювати структуру блогу та управляти підписниками • співавтор • хостинг • читач • адміністратор

Метод имитации отжига

Уже не один раз здесь обсуждалась такая разновидность оптимизационных алгоритмов, как генетические алгоритмы. Однако, существуют и другие способы поиска оптимального решения в задачах с многими степенями свободы. Один из них (и, надо сказать, один из наиболее эффективных) — метод имитации отжига, о котором здесь ещё не рассказывали. Я решил устранить эту несправедливость и как можно более простыми словами познакомить вас с этим замечательным алгоритмом, а заодно привести пример его использования для решения несложной задачки.

Я понимаю, почему генетические алгоритмы пользуются такой большой популярностью: они очень образны и, следовательно, доступны для понимания. В самом деле, несложно и крайне интересно представить решение некой задачи, как реальный биологический процесс развития популяции живых существ с определёнными свойствами. Между тем, алгоритм отжига также имеет свой прототип в реальном мире (это понятно и из самого названия). Правда, пришёл он не из биологии, а из физики. Процесс, имитируемый данным алгоритмом, похож на образование веществом кристаллической структуры с минимальной энергией во время охлаждения и затвердевания, когда при высоких температурах частицы хаотично движутся, постепенно замедляясь и застывая в местах с наименьшей энергией. Только в случае математической задачи роль частиц вещества выполняют параметры, а роль энергии — функция, характеризующая оптимальность набора этих параметров.

Для начала тем, кто забыл, напомню, что же за вид задач мы пытаемся решать такими экзотическими методами. Существует целый ряд задач, чьё точное решение крайне трудно найти в силу большого количества изменяемых параметров. В общем случае у нас есть функция F, чей минимум (максимум) нам нужно найти, и набор её параметров x1..xn, каждый из которых может независимо меняться в своих пределах. Параметры и, соответственно, функция могут изменяться как дискретно, так и непрерывно. Ясно, что у такой функции, скорее всего, будет сложная зависимость от входных данных, имеющая множество локальных минимумов, тогда как мы ищем минимум глобальный. Конечно, всегда остаётся вариант решить задачу полным перебором, но он работает только в дискретном случае и при крайне ограниченном наборе входов. Вот тут и начинают действовать оптимизационные алгоритмы.

Чтобы не быть сухим, сразу расскажу о задаче, которую я буду решать в рамках этой статьи. Представим себе клетчатую доску размером m на l. Сторона клетки равна единице. На доске нужно найти такую расстановку n точек, чтобы длина минимальной ломаной, соединяющей эти точки, была максимальной. Обычная минимаксная задача. Очевидно, что в данном случае функция F считает длину минимальной ломаной для определённой расстановки точек, а параметрами её являются x и y координаты точек, т.е. 2*n параметров.

Собственно, алгоритм
  1. сравниваем текущее значение F с наилучшим найденным; если текущее значение лучше — меняем глобальное наилучшее
  2. случайным образом генерируем новое состояние; распределение вероятности для него должно зависеть от текущего состояния и текущей температуры
  3. вычисляем значение функции для сгенерированной точки
  4. принимаем или не принимаем сгенерированное состояние в качестве текущего; вероятность этого решения должна зависеть от разности функций сгенерированного и текущего состояний и, конечно, от температуры (чем выше температура, тем больше вероятность принять состояние хуже текущего)
  5. если новое состояние не принято, генерируем другое и повторяем действия с третьего пункта, если принято — переходим к следующей итерации, понизив температуру (но чаще переход к следующему шагу производят в любом случае, чтобы избежать долгого зацикливания)
И снова о точках на доске

Теперь, когда общая схема алгоритма ясна, вернёмся к нашим баранам. Будем реализовывать задачу на java. Для начала опишем доску с точками на ней.
Доска:

public class Board < private Point[] points; private int N; private int width; private int height; public Board(int n, int w, int h) < points = new Point[n]; N = n; width = w; height = h; >public Board(Board board) < points = new Point[board.points.length]; for (int i = 0; i < points.length; i++) points[i] = new Point(board.points[i].getX(), board.points[i].getY()); this.width = board.width; this.height = board.height; >public int getPointsCount() < return points.length; >public int getWidth() < return width; >public int getHeight() < return height; >public Point getPoint(int index) < return points[index]; >public void setPoint(int index, Point p) < points[index] = p; >>
 public class Point < private int x; private int y; public Point(int x, int y) < this.x = x; this.y = y; >public double dist(Point p) < return Math.sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y)); >public void move(int dx, int dy, int xBorder, int yBorder)< if(((x + dx) < xBorder) && ((x + dx) >= 0)) x += dx; if(((y + dy) < yBorder) && ((y + dy) >= 0)) y += dy; > public int getX() < return x; >public int getY() < return y; >>

Так как для вычисления искомой функции нам важен порядок следования точек, введём их упорядоченный набор:

 public class Polyline < public Point p[]; public int N = 5; public Polyline(int Num) < N = Num; p = new Point[N]; >public double dist() < double d = 0; for (int i = 0; i < (N - 1); i++) < d += p[i].dist(p[i + 1]); >return d; > >

Теперь нам нужна функция F, ищущая минимальную ломаную заданной расстановки и считающая её длину.

public class MinPolyline < private double bestDist; private Polyline bestMinPolyl; private Board board; public Polyline F(Board b) < N = b.getPointsCount(); board = b; int[] perm = new int[N]; boolean used[] = new boolean[N]; for (int i = 0; i < N; i++) < perm[i] = i + 1; used[i] = false; >bestDist = Double.MAX_VALUE; permute (0, perm, used); return bestMinPolyl; > void permute(int first_index, int[] perm, boolean[] used) < if (first_index == N) < Polyline polyl = new Polyline(N); for (int i = 0; i < N; i++)< polyl.p[i] = board.getPoint(perm[i] - 1); >if (bestDist > polyl.dist()) < bestDist = polyl.dist(); bestMinPolyl = polyl; >return; > for (int i = 1; i < N+1; i++) < if (used[i - 1]) continue; perm[first_index] = i; used[i - 1] = true; permute(first_index + 1, perm, used); used[i - 1] = false; >> >

Ну что ж, все приготовления выполнены. Теперь мы можем начинать реализовывать сам алгоритм.

Реализация алгоритма

Вернувшись к общей схеме, мы встретим там упоминание о двух распределениях, зависящих от координат и температуры. Их нужно каким-то образом определить. Кроме того, нам нужен закон, по которому будет изменяться температура от итерации к итерации. Выбрав эти три функции, мы составим конкретную схему метода отжига. Надо сказать, что существует несколько модификаций алгоритма, отличающихся друг от друга распределениями и законом изменения температур. Они имеют свои плюсы и минусы, такие как быстрота, гарантия нахождения глобального минимума, сложность исполнения.
Я выбрал для своей задачи модификацию под названием сверхбыстрый отжиг («Very Fast Annealing»). Для начала определим распределение вероятности принятия нового состояния.

или в коде:

h = 1 / (1 + Math.exp(-(minPolyl.F(board).dist()- maxDist) / T));

Таким образом, вероятность принятия позиции с худшим результатом функции (с большей энергией) тем меньше, чем ниже температура и чем больше разница между текущей энергией и оптимальной. Далее установим закон убывания температуры. Отличительной особенностью сверхбыстрого отжига является то, что изменения по всем координатам рассматриваются независимо, и даже температура для каждой координаты определяется собственная:

Где D — количество координат (т.е. 2*n), k — номер хода. Однако для простоты сделаем всё-таки общую температуру:

T = To * Math.exp(-decrement * Math.pow(i, (double)(1) / (2*(double)N)));

Как видно, температура будет убывать экспоненциально, и процедура закончится быстро.
Наконец, распределение для новой координаты. Следующая величина характеризует относительное изменение одной координаты:

Где альфа — равномерно распределённая на отрезке [0, 1] величина. Если новая координата не укладывается в рамки своего изменения (в нашем случае — выходит за пределы доски), то расчёт производится снова.

z = (Math.pow((1 + 1/T), (2 * alpha - 1)) - 1) * T; x = board.getPoint(moveNum).getX() + (int)(z * border);

Теперь у нас есть все необходимые распределения и функции. Осталось лишь собрать всё воедино. В качестве входных данных нужно передать размеры доски, количество точек, начальную и конечную температуру и декремент затухания температурной экспоненты.

public class AnnealingOptimizer < public int N; public int width; public int height; public AnnealingOptimizer(int n, int width, int height) < N = n; this.width = width; this.height = height; >public Board optimize(double To, double Tend, double decrement) < Board board = new Board(N, width, height); Board bestBoard = new Board(N, width, height); Random r = new Random(); double maxDist = 0; double T = To; double h; MinPolyline minPolyl = new MinPolyline(); for (int j = 0; j < N; ++j)< board.setPoint(j, new Point(r.nextInt(height), r.nextInt(width))); bestBoard.setPoint(j, board.getPoint(j)); >int i = 1; while (T > Tend) < for (int moveNum = 0; moveNum < board.getPointsCount(); ++moveNum)< NewX(board, moveNum, T, width, true); NewX(board, moveNum, T, height, false); >if (minPolyl.F(board).dist() > maxDist)< bestBoard = new Board(board); >else < h = 1 / (1 + Math.exp(-(minPolyl.F(board).dist()- maxDist) / T)); if (r.nextDouble() >h)< board = new Board(bestBoard); >else < bestBoard = new Board(board); >> maxDist = minPolyl.F(board).dist(); T = To * Math.exp(-decrement * Math.pow(i, (double)(1) / (2*(double)N))); ++i; > return bestBoard; > private void NewX (Board board, int moveNum, double T, int border, boolean xCoord) < Random r = new Random(); int x; double z; double alpha = r.nextDouble(); z = (Math.pow((1 + 1/T), (2 * alpha - 1)) - 1) * T; if (xCoord)< x = board.getPoint(moveNum).getX() + (int)(z * border); if ((x < border) && (x >= 0)) < board.getPoint(moveNum).move((int)(z * border), 0, width, height); >else < NewX(board, moveNum, T, border, xCoord); >> else < x = board.getPoint(moveNum).getY() + (int)(z * border); if ((x < border) && (x >= 0)) < board.getPoint(moveNum).move(0, (int)(z * border), width, height); >else < NewX(board, moveNum, T, border, xCoord); >> > >

Нужно отметить, что некоторые модификации метода имитации отжига дают статистическую гарантию нахождения оптимального решения. Это значит, что при верном выборе параметров алгоритм найдёт оптимальное решение за разумное время без перебора всех входов. Данная реализация находит ответ для доски 12×12 и 5 точек примерно за 15000 итераций. Напомню, что полное число вариантов расстановки равно 12^10. Очевидно, что трудности настройки параметров стоят такого выигрыша. Кстати, метод отжига по быстроте и точности по крайней мере не проигрывает генетическому алгоритму, а чаще всего опережает его.
Напоследок наглядный результат действия алгоритма.

Использованная литература:
А. Лопатин «Метод отжига»

  • отжиг
  • метод имитации отжига
  • оптимизация
  • simulated annealing

как избежать зацикливания в методе перебора ?

Если имеется в виду программирование, то зацикливание-это грубая ошибка программиста. Надо просто писать программу без ошибок.

Александр ЧерниковУченик (121) 3 года назад

и как избежать, если допустил эту ошибку?

Похожие вопросы

Ваш браузер устарел

Мы постоянно добавляем новый функционал в основной интерфейс проекта. К сожалению, старые браузеры не в состоянии качественно работать с современными программными продуктами. Для корректной работы используйте последние версии браузеров Chrome, Mozilla Firefox, Opera, Microsoft Edge или установите браузер Atom.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *