Быстрое поколение случайного набора, Моделирования Монте-Карло
NP обозначает Недетерминированный Многочлен время.
Это означает, что проблема может быть решена в Полиномиальное время с помощью Недетерминированной Машины Тьюринга (как обычная Машина Тьюринга, но также и включая недетерминированную функцию "выбора"). В основном решение должно быть тестируемое в poly время. Если это так, и известная проблема NP может быть решена с помощью данной проблемы с измененным входом (проблема NP может быть , уменьшил до данной проблемы), тогда, проблемой является завершенный NP.
главное отнять у полной NP проблемы состоит в том, что она не может быть решена в полиномиальное время никаким известным способом. NP-Hard/NP-Complete является способом показать, что определенные классы проблем не разрешимы в реалистическое время.
Редактирование: Как другие отметили, часто существуют решения для приближения для Полных NP проблем. В этом случае решение для приближения обычно дает приближение, связанное с помощью специальной нотации, которая говорит нам, как близко приближение.
2 ответа
Если вы используете только первые 20 значений в рандомизированном массиве, вам нужно выполнить только 20 шагов алгоритма Фишера-Йейтса (версия Кнута). Затем 20 значений были рандомизированы (фактически в конце массива, а не в начале, в обычной формулировке) в том смысле, что оставшиеся 80 шагов алгоритма гарантированно не переместят их. Остальные 80 позиций перемешаны не полностью, но кого это волнует?
Код C ++ (итераторы должны иметь произвольный доступ):
using std::swap;
template <typename Iterator, typename Rand> // you didn't specify the type
void partial_shuffle(Iterator first, Iterator middle, Iterator last, Rand rnd) {
size_t n = last - first;
while (first != middle) {
size_t k = rnd(n); // random integer from 0 to n-1
swap(*(first+k),*first);
--n;
++first;
}
}
При возврате значения от сначала до посередине -1 перемешиваются. Используйте это так:
int arr[100];
for (int i = 0; i < 100; ++i) arr[i] = i;
while (need_more_samples()) {
partial_shuffle(arr, arr+20, arr+100, my_prng);
process_sample(arr, arr+20);
}
Книга по моделированию Росс предлагает примерно следующее:
double return[10];
for(int i=0, n=100; i < 10; i++) {
int x = rand(n); //pseudocode - generate an integer on [0,n]
return[i] = arr[x];
arr[x] = arr[n];
n--;
}