Распознавать плохие экземпляры IP наиболее эффективным способом ⇐ Python

[Anonymous]

Я работаю над проектом на Python, для которого мне нужно протестировать все возможные входные данные, то есть 2^35 входных данных. Входные данные имеют длину 35 с 0 или 1. Например, входные данные будут выглядеть так: «00001110001011011010100010001110010»
Небольшое описание проблемы: это называется локально оптимальным разрезом, и я запускаю задачу на этом рисунке:

. Каждый узел должен быть окрашен в цвет 0, 1 так, чтобы у каждого узла было как минимум 3 соседа противоположного цвета.
Узлы 1–12 не получают никаких входных данных.
Узлы 13-47 заданы входные значения (0 или 1), следовательно, 2 ^ 35. Узел 48 всегда имеет 0 на входе.
Цель состоит в том, чтобы проверить все допустимые входные данные и проверить, можно ли раскрасить узлы 1–12 так, чтобы это соответствовало задаче.
I используйте IP-решатель (z3), чтобы проверить, работает ли проблема, разрешима она или нет. Есть две программы: первая работает, игнорируя центр, поэтому она принимает входные данные и проверяет, что это действительный экземпляр проблемы. Например, это неправильный ввод:

Вы можете видеть, что у узла 13 есть 3 соседа одного цвета. Следовательно, нет необходимости запускать решатель на всем графе, поскольку входные данные сами по себе содержат недопустимое решение. Если бы входные данные были действительными, я бы затем восстановил все ребра, отсутствующие на первой фигуре, и решил IP.
С точки зрения псевдокода, вот как будет выглядеть код:< /p>

Код: Выделить всё

valid_instance = solve_on_B(input) #check if the input itself is valid
if valid_instance == True:
print(solve_on_A(input),input) #the input is valid, so can we complete the coloring?

Однако, к моему удивлению (думаю, этого и следовало ожидать), когда я беру случайные входные данные, большинство из них на самом деле являются плохими экземплярами. Для контекста: я тестировал 7 тысяч случайных входных данных, и до сих пор все они были отклонены. Поэтому передача всех входных данных через решатель является излишним, если очень большая их часть даже недействительна. Поэтому вместо того, чтобы делать это, я ищу функцию, которая просто должна просмотреть входные данные и решить, стоит ли вообще запускать какой-либо решатель.
Например: если мы находимся в треугольнике 21, 39, 37, и все они имеют один и тот же цвет, то 19, 23, 41 должны иметь другой цвет.
Я думал о том, чтобы жестко запрограммировать такого рода правила для всех треугольников в функцию вместо прямого вызоваsolve_on_B. Я также мог бы запрограммировать его для всех узлов 13–48, что кажется гораздо более хлопотным, если делать это вручную, но при этом мне никогда не придется вызыватьsolve_on_B. Но мне интересно, как мне написать эту проверочную функцию. Как уже упоминалось, мне нужно протестировать 2^35 входов, поэтому эффективность использования времени — самое важное.

Подробнее здесь: https://stackoverflow.com/questions/790 ... y-possible