Когда вам следует прекратить расширять горизонт планировщика CSP? В частности, существует ли условие планировщика проблем с ограничением ограничений, которое, когда согласование с ошибкой поиска на некотором горизонте приводит к тому, что согласованность дуги также будет терпеть неудачу для всех более длинных горизонтов.Когда вам следует прекратить расширять горизонт CSP?
Если ваш планировщик очень общий, ответ должен быть отрицательным.
Предположим, что ваша система ограничений достаточно общая, чтобы она могла проверять: «Каждая строка этой матрицы соответствует ленте машины Тьюринга, а строка i является снимком состояния машины Тьюринга после шага i и последней строки показывает, что машина Тьюринга остановлена ».
Тогда «Я нашел матрицу, удовлетворяющую ограничениям», соответствует «Эта машина Тьюринга остановлена» и https://en.wikipedia.org/wiki/Halting_problem - это единственный способ узнать, остановилась ли машина Тьюринга или другое общее вычисление, чтобы играть в нее и подождите, чтобы остановить его.
Спасибо за разные взгляды на проблему, даже не рассмотрев проблему остановки. –
Стриптиз-планирование разрешимо, оно даже в PSPACE. Таким образом, аналогия с проблемой остановки не выполняется. – ziggystar
Я вижу, что если вы решаете ограничения для фиксированной области, вы можете сделать это в PSPACE, пробовав все возможные комбинации. То, что я думаю, показывает аналогию с машиной Тьюринга, состоит в том, что для того, чтобы существовало решение, область, возможно, должна быть непредсказуемо большой. – mcdowella