4511
правок
K-КНФ-алгоритмы на основе поиска с возвратом: различия между версиями
Перейти к навигации
Перейти к поиску
м
K-КНФ-алгоритмы на основе поиска с возвратом (посмотреть исходный код)
Версия от 23:28, 24 февраля 2018
, 24 февраля 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 22: | Строка 22: | ||
Функция Modify(КНФ-формула <math>G(x_1, x_2, ..., x_n) \;</math>, перестановка <math>\pi \;</math> = ({1, 2, ..., n}, присваивание y) <math>\to</math> (присваивание u) | Функция '''Modify'''(КНФ-формула <math>G(x_1, x_2, ..., x_n) \;</math>, перестановка <math>\pi \;</math> = ({1, 2, ..., n}, присваивание y) <math>\to</math> (присваивание u) | ||
<math>G_0 = G</math>. | <math>G_0 = G</math>. | ||
| Строка 31: | Строка 31: | ||
'''then''' <math>u_{\pi(i)} = 0</math> | '''then''' <math>u_{\pi(i)} = 0</math> | ||
'''else''' <math>u_{\pi(i)} = y_{\pi(i)}</math> | '''else''' <math>u_{\pi(i)} = y_{\pi(i)}</math> | ||
<math>G_i = G_{i - 1} \lceil_{x_{\pi (i)} = u_{\pi (i)}} \;</math> | |||
end /* | '''end''' /* конец цикла for */ | ||
'''return''' u; | |||
Алгоритм Search получается в результате выполнения алгоритма Modify(G, | Алгоритм '''Search''' получается в результате выполнения алгоритма '''Modify'''<math>(G, \pi, y) \;</math> на нескольких парах <math>(\pi, y) \;</math>, где <math>\pi \;</math> – случайная перестановка, а y – случайное присваивание. | ||
Search(КНФ-формула F, целое число I) | '''Search'''(КНФ-формула F, целое число I) | ||
'''repeat''' I раз | |||
<math>\pi</math> = равномерно распределенная случайная перестановка 1, ..., n | |||
then output(u); exit; end/* | у = равномерно распределенный случайный вектор <math>\in \{ 0, 1 \}^n \;</math> | ||
u = '''Modify'''<math>(F, \pi, у)</math>; | |||
'''if''' при u формула F выполнима | |||
'''then''' output(u); '''exit'''; | |||
'''end''' /* конец цикла repeat */ | |||
output("Невыполнимо"); | |||