Что вы всегда хотели узнать, но боялись спросить

NT · Сообщение NT » 08 дек 2012, 17:31

Swetlana писал(а):Source of the post алгоритм с возвратом с отсечением заведомо неподходящих вариантов ...

Я понял и вполне достаточно. Зайцам привет!

PS. В смысле код не обязателен. Мне достаточно к какому типу относиться.

Swetlana · Сообщение **Swetlana** » 08 дек 2012, 18:47

А вот и недостаточно
Схема алгоритма с возвратом реализована крайне неоптимально.
Добавляем к текущей сумме новую цифру j (для позиции i) и набираем больше, чем MaxS. Надо возвращаться на предыдущую i-1 -ю позицию, нет смысла продолжать это решение. А алгоритм продолжает заполнять оставшиеся позиции всеми возможными способами. Сколько лишних переборов!

Вот так будет оптимально. Хотя, вдруг кто-то сможет ещё уменьшить переборы?

Код: Выбрать все

program NT;

{$APPTYPE CONSOLE}

uses
 SysUtils;

const
N = 4; //количество цифр

var
//текущий код, код-решение и загаданный код
X,OptX,X0: array [1..N] of integer;
i: integer;
MinS, MaxS: integer; //минимальная и максимальная допустимая сумма цифр
flag: boolean; //нашли решение
Sum9: integer; //сумма N девяток

procedure search (i,sum,poss: integer);
//i - текущая позиция
//sum - сумма цифр с первой по i-1 -ю позиции
//poss - максимальная сумма, которую получим,
//если все оставшиеся пустые позиции заполним девятками
var
j,k: integer;
mm: integer;
begin
 if not(flag) then begin
 for j:= 0 to 9 do //выбор цифры для заполнения i-й позиции кода
 begin
 //проверка допустимости цифры
 //если текущая сумма + j >= MaxS, нет смысла увеличивать j
 //если poss, максимально возможная сумма, <= MinS, нет смысла продолжать подбор
 //поэтому по break выходим из цикла, выходим из рекурсии для i-й позиции
 //и возвращаемся на рекурсию для предыдущей i-1-й позиции
 if (sum+j >= MaxS) OR (poss-9+j <= MinS) then break;
 if i < N then //не последняя цифра
 begin
 X[i]:= j;
 search(i+1,sum+j,poss-9+j);
 end
 else if i=N then//последняя цифра
 begin //проверка на полное решение
 X[i]:= j;
 flag:= true;
 for k:=1 to N do
 if X0[k]<>X[k] then flag:= false;
 if flag then //нашли решение
 begin
 for k:= 1 to N do OptX[k]:= X[k];
 exit;
 end;
 end
 end;
 end;
end; //search

begin //main
 //задаём код 1234
 X0[1]:= 1; X0[2]:= 2; X0[3]:= 3; X0[4]:= 4;
 //задаём минимальную и максимальную сумму цифр
 MinS:= 5; MaxS:= 20;
 //инициализация текущего и оптимального решения
 for i:= 1 to N do
 begin X[i]:= -1; OptX[i]:= -1; end;
 flag:= false; //решение не найдено
 Sum9:= 9*N;
 //вызов рекурсии для заполнения 1-й цифры кода
 //текущая сумма кодовых цифр равна 0
 //по максимуму можно набрать сумму всех девяток
 search(1,0,Sum9);

 //печать решения
 for i:= 1 to N do write(OptX[i],' ');
 writeln; readln;
end.

Swetlana · Сообщение **Swetlana** » 08 дек 2012, 20:07

исправила очепятку
вот теперь работает быстро :rolleyes:

или мы уже перебрали, или мы уже недобираем, в любом случае по break выходим на предыдущий уровень рекурсии для i-1 позиции

if (sum+j >= MaxS) OR (poss-9+j <= MinS) then break;

alexBlack · Сообщение **alexBlack** » 08 дек 2012, 20:13

По второму условию нельзя прерывать, т.к. при следующем j условие может выполняться.

Код: Выбрать все

 if (sum+j >= MaxS) then break;
 if (poss-9+j <= MinS) then continue;

----
Можно уменьшить пространство поиска, если ввести ограничение "каждая следующая цифра не меньше предыдущей"

Код: Выбрать все

procedure search (i,sum,poss,b: integer);
...
 for j:= b to 9 do begin
...
 search(i+1,sum+j,poss-9+j, j);

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

Swetlana · Сообщение **Swetlana** » 08 дек 2012, 20:21

alexBlack писал(а):Source of the post
По второму условию нельзя прерывать, т.к. при следующем j условие может выполняться.

всё верно!

правильный вариант

Код: Выбрать все

if (sum+j >= MaxS) OR (poss <= MinS) then break;
...
search(i+1,sum+j,poss-9+j);

Можно уменьшить пространство поиска, если ввести ограничение "каждая следующая цифра не меньше предыдущей"

раз вы предлагаете новую задачу - подбор n-значного цифрового кода при условии, что каждая цифра не меньше предыдущей, оцените размер пространства поиска, сколько различных кодов мы можем загадать при таких условиях

Swetlana · Сообщение **Swetlana** » 09 дек 2012, 09:30

интересная комбинаторная задача - оценить размер пространства поиска для упорядоченных кодов
по-моему тут точно не подсчитаешь
или подсчитаешь?

alexBlack · Сообщение **alexBlack** » 09 дек 2012, 10:03

Swetlana писал(а):Source of the post
раз вы предлагаете новую задачу - подбор n-значного цифрового кода при условии, что каждая цифра не меньше предыдущей, оцените размер пространства поиска, сколько различных кодов мы можем загадать при таких условиях

по-моему это сочетания с повторениями, т.е. ${10+n-1\choose n}$

Swetlana · Сообщение **Swetlana** » 09 дек 2012, 11:19

в коде важен порядок цифр, поэтому это не сочетания, а размещения
и нужно принимать во внимание дополнительное условие о неубывании следующей цифры
пусть $$C_m^k$$

- количество кодов длины $$m$$

, в которых можно использовать цифры $$k, k+1, .., 9$$

.
Нам нужно оценить $$C_n^0$$

Заполняем первую позицию фиксированной цифрой $$i, i =0.. 9$$

. Оставшиеся $$n-1$$

позицию можно заполнить
$C_{n-1}^i$ .
Отсюда $C(n,0)=\sum_{i = 0}^{9}C(n-1,i)$
вот как-то так, имхо, нужно начинать рассуждения
а может и не так

Swetlana · Сообщение **Swetlana** » 25 дек 2012, 06:49

Взаимоотношение между классами $$P$$

и

. Задачи, не принадлежащие $$NP$$

.

Задачи, дополнительные к $$NP\ (ñîNP)$$
Сформулируем задачу $$\barÏ$$ , дополнительную к задаче распознования $$Ï$$ :
« Дано $$À$$, верно ли, что для $$À$$ не выполняется $$Õ$$ ? »
Если исходная задача $$Ï \in P$$, то есть решается полиномиальным детерминированным алгоритмом (ДМТ за полиномиальное время), то все вычисления сводятся к одной ветви, заканчивающейся либо в состоянии $$q_n$$

(ответ "нет"), либо в $$q_y$$

(ответ "да").
Достаточно поменять местами $$q_y$$

и

, чтобы получить ДМТ для решения задачи, дополнительной к $$Ï $$</span> ( <span class=

$$" title="$$ ( $$" align="middle" style="border: 0; vertical-align: middle">\barÏ$$ ).
Если исходная ДМТ – полиноминальна, то ДМТ для решения задачи, дополнительной к $$Ï$$, так же будет полиномиальной. Отсюда $P= \bar{P}$ , т.е. задачи, дополнительные к $$P$$

, так же лежат в классе $$P$$

.

Swetlana · Сообщение **Swetlana** » 25 дек 2012, 07:12

Теперь рассмотрим задачу $$\barÏ$$, дополнительную к задаче $$Ï \in NP$$.
Задача $$Ï$$ решается недетерминированной машиной Тьюринга, которая останавливается только в состоянии $$q_y$$

(ответ "да"), иначе ждем, пока все вычисления закончатся в состоянии $$q_n$$

.
После перестановки состояний $$q_y$$

(УСПЕХОВ) и $$q_n$$

(НЕУДАЧ) получим недетерминированную машину Тьюринга, которая не будет решать дополнительную задачу $$\barÏ$$.

В качестве примера рассмотрим задачу, дополнительную к задаче "Коммивояжер".
Вопрос в этой задаче формулируется следующим образом: "Верно ли, что не существует ни одного гамильтонова цикла стоимостью меньшей либо равной $$B$$

?"
Переставим в НДМТ, решающей задачу коммивояжера, $$q_n$$

и $$q_ó$$ местами.
После перестановки местами $$q_y$$

и

недетерминированная машина Тьюринга находит первый гамильтонов цикл стоимости, большей $$B$$

, и останавливается, ответ "да". А нам нужно показать, что все гамильтоновы циклы имеют стоимость большую $$B$$

.
Для решения этой задачи не известен способ, который был бы короче, чем проверка всех или почти всех возможных маршрутов. Другими словами, для решения "анти-коммивояжера" не найден недетерминированный полиномиальный алгоритм, но и не доказано, что такого алгоритма не существует. Таким образом, на сегодняшний день, эта задача является труднорешаемой, но не принадлежит ни классу $$Å$$, ни классу $$Ð$$, не классу $$NP$$

.

yourdomain.com