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