2-SATisfiabilty проблемных тестовых случаев

Я написал SAT решатель для задачи 2-удовлетворяемости, кто-то, пожалуйста, предоставьте мне контрольный пример, скажем, 10000 литералов, который имеет только одно выполнимое назначение, т.е. только одно решение

The format can be:(for 3 literals)
2            // No of clauses and then each clause
2 3
1 -2
corresponding to
(b+c).(a+!b)
Источник

2 ответа

Решение

Тестирование покрытия обычно затруднено, в большинстве случаев вы просто забываете о том или ином факторе.

Я обычно поступаю в несколько шагов:

  1. Убедитесь, что это решает тривиальную проблему (или некоторые)
  2. Тестовые граничные случаи / граничные условия: предложение 0, например
  3. Случаи тестовых ошибок: плохо отформатированный ввод, проблемы без решения
  4. Тест производительности / массового впрыска (посмотрите, не падает ли программа под нагрузкой, не протекает,...)

2) и 3) в значительной степени взаимозаменяемы, 4) должны поступать только в том случае, если у вас есть способы исследования такого рода информации (бенчмаркинг, обнаружение утечек памяти...).

Важным моментом является то, что вы не должны перепроектировать свой код для написания тестов, потому что в итоге вы будете тестировать свой код, а не тестировать, что он соответствует спецификациям.

Если это домашний проект, спецификации, как правило, неформальные, но они все еще существуют (в вашей голове), и именно после них вы должны подготовить контрольные примеры.

Источник

Работает ли этот подход?

 (a + b ).(a + !b)

Это может быть удовлетворено, только если верно.

 (a + !b).(!a + !b)

Может быть выполнено, только если b ложно. следовательно

  (a + b ).(a + !b).(a + !b).(!a + !b)

Полностью указывает значения для a и b. Теперь мы можем расширить это для любого числа литералов.

Чтобы протестировать ваше приложение, вы также можете указать противоречивые требования, а значит, что-то без решения.

Источник
Другие вопросы по тегам