Алгоритм
|
|||
---|---|---|---|
#18+
Усовершенствованный брутфорс 3-sat выражения. За 6 минут на старом дряхлом ноуте в один поток выдаёт все варианты решения задачи из 50 переменных. ... |
|||
Хуск - трусливое анусное ссыкло. 3174775
Трахая козу, Квейд наивно полагает, что приобщается к великой культуре 3399661 :
Нравится:
Не нравится:
|
|||
23.07.2021, 22:26 |
|
Алгоритм
|
|||
---|---|---|---|
#18+
Да, забыл. Обычный брутфорс на том же ноуте считает это же больше двух суток, может дольше, ждать не стал. ... |
|||
Хуск - трусливое анусное ссыкло. 3174775
Трахая козу, Квейд наивно полагает, что приобщается к великой культуре 3399661 :
Нравится:
Не нравится:
|
|||
23.07.2021, 22:36 |
|
Алгоритм
|
|||
---|---|---|---|
#18+
Посчитал сложность. Если для брутфорса сложность равна O(2^n), то для моего алгоритма она равна O((7/8)^m*2^n), где n - число переменных, m - число клозов в выражении. ... |
|||
Хуск - трусливое анусное ссыкло. 3174775
Трахая козу, Квейд наивно полагает, что приобщается к великой культуре 3399661 :
Нравится:
Не нравится:
|
|||
24.07.2021, 20:39 |
|
Алгоритм
|
|||
---|---|---|---|
#18+
Не вижу никакого алгоритм а ... |
|||
:
Нравится:
Не нравится:
|
|||
24.07.2021, 20:41 |
|
Алгоритм
|
|||
---|---|---|---|
#18+
помощник менеджера 24.07.2021, 20:41 Не вижу никакого алгоритм а ... |
|||
Хуск - трусливое анусное ссыкло. 3174775
Трахая козу, Квейд наивно полагает, что приобщается к великой культуре 3399661 :
Нравится:
Не нравится:
|
|||
24.07.2021, 20:43 |
|
Алгоритм
|
|||
---|---|---|---|
#18+
Ё 24.07.2021, 20:39 Посчитал сложность. Если для брутфорса сложность равна O(2^n), то для моего алгоритма она равна O((7/8)^m*2^n), где n - число переменных, m - число клозов в выражении. ... |
|||
Хуск - трусливое анусное ссыкло. 3174775
Трахая козу, Квейд наивно полагает, что приобщается к великой культуре 3399661 :
Изменено: 24.07.2021, 20:51 - Ё
Нравится:
Не нравится:
|
|||
24.07.2021, 20:47 |
|
Алгоритм
|
|||
---|---|---|---|
#18+
Сам алгоритм. 1. Пронумеруем все n битов задачи. 2. Отсортируем переменные в каждом клозе выражения в порядке возрастания. 3. Отсортируем все клозы выражения в порядке возрастания переменных, которые в них входят. 4. Инициализируем переменные нулями. 5. В порядке сортировки клозов проверяем их на выполнимость, пока не найдём невыполнимую клозу. 6. В невыполнимой клозе увеличим значение последнего бита, что бы клоза стала выполнимой. Если последний бит был единицей, применим правило переноса на следующий бит задачи. 7. Повторяем пункты 5 - 7 до тех пор, пока выражение не будет выполнимо. Если при выполнении переноса мы получаем все биты равные 0, выражение не имеет решений. Тут еще есть момент с улучшением. Если клоза выполнима и следующее её значение при увеличении последней переменной приводит к невыполнимости, пометим эту переменную признаком блокировки, указывающим, что она заблокирована предыдущей переменной клозы. При последующем распространении переноса, перенос происходит через заблокированные переменные, пока не изменится переменная, которая их заблокировала. ... |
|||
Хуск - трусливое анусное ссыкло. 3174775
Трахая козу, Квейд наивно полагает, что приобщается к великой культуре 3399661 :
Изменено: 24.07.2021, 21:15 - Ё
Нравится:
Не нравится:
|
|||
24.07.2021, 21:10 |
|
Алгоритм
|
|||
---|---|---|---|
#18+
Ё 24.07.2021, 21:10 Сам алгоритм. 1. Пронумеруем все n битов задачи. 2. Отсортируем переменные в каждом клозе выражения в порядке возрастания. 3. Отсортируем все клозы выражения в порядке возрастания переменных, которые в них входят. 4. Инициализируем переменные нулями. 5. В порядке сортировки клозов проверяем их на выполнимость, пока не найдём невыполнимую клозу. 6. В невыполнимой клозе увеличим значение последнего бита, что бы клоза стала выполнимой. Если последний бит был единицей, применим правило переноса на следующий бит задачи. 7. Повторяем пункты 5 - 7 до тех пор, пока выражение не будет выполнимо. Если при выполнении переноса мы получаем все биты равные 0, выражение не имеет решений. Тут еще есть момент с улучшением. Если клоза выполнима и следующее её значение при увеличении последней переменной приводит к невыполнимости, пометим эту переменную признаком блокировки, указывающим, что она заблокирована предыдущей переменной клозы. При последующем распространении переноса, перенос происходит через заблокированные переменные, пока не изменится переменная, которая их заблокировала. ... |
|||
Хуск - трусливое анусное ссыкло. 3174775
Трахая козу, Квейд наивно полагает, что приобщается к великой культуре 3399661 :
Изменено: 25.07.2021, 00:26 - Ё
Нравится:
Не нравится:
|
|||
25.07.2021, 00:21 |
|
Start [/forum-old/topic.php?fid=13&gotomsg=3155760&tid=64992]: |
0ms |
get settings: |
1ms |
get forum list: |
3ms |
check forum access: |
0ms |
check topic access: |
0ms |
track hit: |
7ms |
get topic data: |
4ms |
get forum data: |
0ms |
get page messages: |
28ms |
update_topic_read_status (64992): 25.07.2021 00:21:18: |
0ms |
get tp. blocked users: |
0ms |
get online users: |
3ms |
others: | 50ms |
total: | 96ms |
0 / 0 |