Описание задачи.

💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

Описание задачи.

Тема: Анализ работы «слепых» методов поиска при решении задач в пространстве состояний.

Цель: Дать представление о возможности использования «слепых» методов поиска в решении задач.

Задача: Провести относительный анализ эффективности использования различных процедур генерации «слепыми» методами поиска при различных условиях их проведения.

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

Для осуществления перестановки берем наш ряд 9“ ù õ и делим его на пары. Чтобы определить количество пар берем общее количество предметов и вычитаем из него единицу (l=n-1), в нашем случае 4-1=3, то есть делим ряд 9“ ù õ на три пары:

Берем 1ую пару и делим ее 2 части: первая часть - 9 и вторая часть - “, проделываем то же самое и с остальными парами.

Берем то, что осталось от 1 ряда (ù õ) и в его начало ставим 1 часть пары, и в конец ряда ставим 2 часть пары и получаем новый ряд 9ù õ “, то же самое проделываем с остальными парами и получаем в результате три новых ряда.

Любой ряд можно перестанавливать не до бесконечности, имеется определенное количество рядов (комбинаций), которые могут быть образованы в результате перестановок, оно рассчитывается по формуле: n=n! /2-12/2=6

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

Берем то, что осталось от 1 ряда (ù õ) и в его начало ставим 2 часть пары, и в конец ряда ставим 1 часть пары и получаем новый ряд “ ù õ 9, то же самое проделываем с остальными парами и получаем в результате три новых ряда.

Целью задачи является получение из некоторой заданной последовательности знаков, требуемую последовательность этих же знаков.

В качестве знаков могут быть использованы любые символы. Но предлагается использовать набор не повторяющихся цифр. Количество состояний (возможных сочетаний цифр) S =n!, где n –количество цифр в состоянии.

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

Рассмотрим пример преобразований на наборе цифр от 1 до 4.

Преобразование состояний «прямым» преобразованием. выполняется следующим образом:

1) В состоянии выделяются пары чисел (i, i+ 1). Например, для состояния 1234, парами являются (1, 2), (2, 3) и (3, 4), (их количество n –1 = 3);

2) Первое число пары i переносится в начало состояния, а второе i+ 1 в конец состояния (см. рисунок 1).

При «обратном» преобразовании первое число пары i переносится в конец состояния, а второе i+ 1 в начало состояния (см. рисунок 2).

Таким образом, всегда может быть сформировано (n – 1) состояний. На следующем этапе в полученных состояниях также выделяются пары, и алгоритм преобразования состояний повторяется до условия окончания поиска.

Рассмотрим пример преобразований так же на наборе цифр от 1 до 4.

Полная схема преобразования состояний прямым преобразованием представлена на рисунке 3.

Полная схема преобразования состояний обратным преобразованием представлена на рисунке 4.

Дополнительно организацию состояний можно отобразить с помощь матриц смежности и инцидентности. Матрица смежности позволяет представить бинарные отношения между вершинами орграфа. Отношение смежности обозначается «1», если между вершинами x_i и x_i₊ ₁существует дуга y_j, иначе «0». Матрица инцидентности позволяет представить отношения между количеством входящих и выходящих дуг некоторой вершины x_iÎ G. Отношение обозначается «1», если дуга y_j выходит из вершины x_i, иначе «0» (если дуга y_j входит в вершину x_i).

Матрица смежности для прямого преобразования

В таблице смежности как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот). Если связь вежду вершинами имеется то ставим «1», иначе «0». Заметим, что в главной диагонали получившейся матрицы стоят «0». Также, содержание i-того столбца соответствует содержанию i-той строки, так как и там, и там записаны вершины графа(например 1-ый столбец: 0 1 1 1 1 0 0 0 0 1 0 0 и первая строка: 0 1 1 1 1 0 0 0 0 1 0 0). Еще можно увидеть, что каждая строка(столбец) имеет пять «1», хотя из матрицы смежности следует, что каждая вершина имеет 6 дуг, это объясняется тем, что при прямом преобразовании каждая вершина имеет одну двойную связь(т.е. каждая вершина имеет парную себе вершину между которыми возникает связь «вход-выход» и «выход-вход»)

Матрица инцидентности для прямого преобразования.

Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (дуга и вершина). Столбцы матрицы соответствуют вершинам, строки — ребрам. Если y_j выходит из вершины x_i то «1», иначе «0». Заметим, что в строке каждого y_j имеется одна «1» и один «0», это значит что каждая дуга из одной вершины выходит и в другую входит, следовательно в графе нет корневых вершин(которые имеют только выходы). А также, каждая вершина имеет ранвое количество входов и выходов.

Например, для поиска по лучу всегда раскрывается только одна любая пара из состояния. Для поиска в глубину всегда раскрываются все пары одного любого состояния. Для «параллельного» поиска всегда раскрывается одна определенная пара из всех состояний фронта. Для поиска в ширину все пары всех состояний.

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

Условием окончания преобразования состояний будет являться множество дуг, исходящих из вершины хi, (родительской вершины), и множество вершин (называемых дочерними вершинами), в которые эти дуги приводят. Множество дуг, исходящих из вершины xi, должно соответствовать множеству операторов, которые могут быть применены к состоянию, соответствующему вершине хi. При использовании в состояниях 4х символов, количество входящих в состояние опереторов должно быть равно количеству выходящих из него операторов и равно n-1, т.е 3. После чего построение графа заканчивается.