Многие дистрибутивы Solver включают пример N Queens, в котором необходимо разместить n ферзей на шахматной доске n*n без возможности атаки. Поэтому, когда вы ищете самый быстрый Solver, заманчиво использовать пример N Queens в качестве эталона для сравнения этих решателей. Это трагическая ошибка, потому что проблема N Queens разрешима за полиномиальное время, что означает, что есть способ обмануть.
При этом OptaPlanner решает проблему 1 000 000 ферзей менее чем за 3 секунды. Вот журнал, чтобы доказать это (со временем, потраченным в миллисекундах):
|
1
2
3
4
5
6
7
8
|
INFO Opened: data/nqueens/unsolved/10000queens.xmlINFO Solving ended: time spent (23), best score (0), ...INFO Opened: data/nqueens/unsolved/100000queens.xmlINFO Solving ended: time spent (159), best score (0), ...INFO Opened: data/nqueens/unsolved/1000000queens.xmlINFO Solving ended: time spent (2981), best score (0), ... |
Как обмануть проблему N Queens
Проблема N Queens не является NP-полной или NP-сложной. То есть математика говорит о том, что существует идеальный алгоритм для решения этой проблемы : алгоритм Explicits Solutions . Реализованный с CustomSolverPhaseCommand в OptaPlanner это выглядит так:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
public class CheatingNQueensPhaseCommand implements CustomSolverPhaseCommand { public void changeWorkingSolution(ScoreDirector scoreDirector) { NQueens nQueens = (NQueens) scoreDirector.getWorkingSolution(); int n = nQueens.getN(); List<Queen> queenList = nQueens.getQueenList(); List<Row> rowList = nQueens.getRowList(); if (n % 2 == 1) { Queen a = queenList.get(n - 1); scoreDirector.beforeVariableChanged(a, "row"); a.setRow(rowList.get(n - 1)); scoreDirector.afterVariableChanged(a, "row"); n--; } int halfN = n / 2; if (n % 6 != 2) { for (int i = 0; i < halfN; i++) { Queen a = queenList.get(i); scoreDirector.beforeVariableChanged(a, "row"); a.setRow(rowList.get((2 * i) + 1)); scoreDirector.afterVariableChanged(a, "row"); Queen b = queenList.get(halfN + i); scoreDirector.beforeVariableChanged(b, "row"); b.setRow(rowList.get(2 * i)); scoreDirector.afterVariableChanged(b, "row"); } } else { for (int i = 0; i < halfN; i++) { Queen a = queenList.get(i); scoreDirector.beforeVariableChanged(a, "row"); a.setRow(rowList.get((halfN + (2 * i) - 1) % n)); scoreDirector.afterVariableChanged(a, "row"); Queen b = queenList.get(n - i - 1); scoreDirector.beforeVariableChanged(b, "row"); b.setRow(rowList.get(n - 1 - ((halfN + (2 * i) - 1) % n))); scoreDirector.afterVariableChanged(b, "row"); } } }} |
Теперь можно утверждать, что в этой реализации не используются какие-либо алгоритмы OptaPlanner (такие как строительная эвристика или локальный поиск). Но легко подражать этому подходу в строительной эвристике (или даже в локальном поиске). Таким образом, в тесте любой Солвер, который симулирует этот подход больше всего, гарантированно выиграет при масштабировании.
Почему это не работает для других проблем планирования?
Этот алгоритм идеально подходит для N королев, так почему бы не использовать идеальный алгоритм для других задач планирования? Ну просто потому что их нет !
Большинство проблем планирования, таких как маршрутизация транспортных средств, составление списков сотрудников, оптимизация облачных вычислений, упаковка бункеров,… доказано, что они являются NP-полными (или NP-сложными). Это означает, что эти проблемы по сути одинаковы: идеальный алгоритм для одного будет работать для всех из них. Но ни один человек не нашел такого алгоритма (и большинство экспертов считают, что такого алгоритма не существует).
Примечание. Существует несколько заметных исключений из задач планирования, которые не являются NP-полными или NP-сложными. Например, поиск кратчайшего расстояния между двумя точками может быть решен за полиномиальное время с помощью A * -Search. Но их область действия узкая: нахождение кратчайшего расстояния для посещения n точек (TSP), с другой стороны, невозможно решить за полиномиальное время.
Поскольку N Queens по своей природе отличается от реальных проблем планирования, это ужасный пример использования для сравнения.
Вывод
Ориентиры по проблеме N Queens не имеют смысла. Вместо этого, тесты реализации реалистичного соревнования. Реалистичный конкурс — это официальный, независимый конкурс :
- который четко определяет реальный вариант использования
- с реальными ограничениями
- с несколькими реальными наборами данных
- что ожидает воспроизводимых результатов в течение определенного времени на конкретном оборудовании
- при серьезном участии академического и / или корпоративного сообщества по исследованию операций
Примеры OptaPlanner реализуют несколько случаев реалистичных соревнований .
| Ссылка: | Обман в тесте N Queens от нашего партнера JCG Джеффри Де Смета в блоге OptaPlanner . |