У меня есть теоретическая/практическая проблема, и я пока не знаю, как это сделать. Вот она:
Я создаю SAT solver, способный найти модель, когда она существует, и доказать противоречие, если это не так на CNF проблемы на C с использованием генетических алгоритмов.
SAT-проблема выглядит в основном такой проблемой: Моя цель - использовать этот решатель для поиска решений во множестве различных NP-завершает проблемы. В основном, я переводил различные проблемы в SAT, решает SAT с моим решателем, а затем преобразовываю решение в решение, приемлемое для исходной проблемы.
Мне уже удалось выполнить N * N Sudoku, а также проблемы N-queens, но вот моя новая цель: уменьшить проблему планирования классов до SAT, но я понятия не имею, как формализовать задачу планирования класса для упорядочения чтобы легко преобразовать его в SAT после.
Цель состоит в том, чтобы через несколько месяцев создать график расписания, подобный этому:
Я нашел этот исходный код, который может решить расписание классов, но без каких-либо сокращений к SAT, к сожалению:/
Я также нашел некоторые статьи о планировании вообще (http://www.cs.rochester.edu/users/faculty/kautz/papers/kautz-satplan06.pdf, например).
Но планирование языка определения домена, используемый в этой статье, кажется слишком общим для меня, чтобы представлять проблему планирования класса.:/
Есть ли у кого-то идея о том, как эффективно формализовать планирование классов, чтобы уменьшить его до SAT и после, преобразовать решение SAT (если оно существует ^^) в расписание классов?
Я в принципе открыт для любых предложений, я пока не знаю, как представить, как уменьшить проблему, как преобразовать SAT-решение в расписание...
Следующий вопрос: Расписание классов для булевой выполнимости [Часть 2].