Алгоритм теста хи-квадрат - PullRequest
Новая
       3

Алгоритм теста хи-квадрат

2 голосов
/ 31 октября 2010

Я случайным образом выбираю узлы из двоичного дерева, и мне нужно создать тест черного ящика, который доказывает, что все узлы имеют почти одинаковую вероятность выбора.

Я адаптирую Chi-Алгоритм квадратного теста, основанный на этой статье http://en.wikibooks.org/wiki/Algorithm_Implementation/Pseudorandom_Numbers/Chi-Square_Test, но я немного озадачен тем, каким должно быть 'r'.

Как дополнительный вопрос, считаете ли вы, что это подходящий алгоритм для доказательства?случайность в наборе результатов?

Спасибо, Диого

1 Ответ

2 голосов
/ 31 октября 2010

Ответ прямо здесь, в цитате.Прокрутите вниз до javadocs: 

* @param  r           upper bound for the random range

Мне кажется, что r должно быть числом узлов в дереве.Вы согласны?

Я случайно выбираю узлы из двоичного дерева, и мне нужно создать тест черного ящика, который доказывает, что все узлы имеют почти одинаковую вероятность выбора.

Я не понимаю этого.Вы?Кажется, это не проверка древовидной структуры данных, а скорее случайный алгоритм, который вы используете для выбора узла, который нужно выбрать.Что этот результат доказывает?

Проведите меня через то, что вы делаете, пожалуйста.Вот что я себе представляю:

  1. У вас есть список узлов в вашем дереве.
  2. Вы каким-то образом используете случайный алгоритм, чтобы выбрать узел для выбора из своего дерева.
  3. Вы просматриваете свое дерево, чтобы найти этот узел.

Если в вашем дереве есть r узлы, каждый из них должен иметь вероятность 1 / r выбора.Это многомерная, односторонняя монета или кубик.Правильно?

Дерево может внести в микс еще один элемент: вероятности изменяются, если шансы на выбор зависят от того, где вы находитесь в дереве, и от того, разрешено ли вам возвращаться назад.Если это так, шансы быть выбранными различны на каждом узле.Начиная с корня означает, что вы можете добраться до всех дочерних узлов.Нахождение на первом уровне и невозможность возврата назад исключает возможность рассмотрения корневого и всех других узлов первого уровня и т. Д.

Какую проблему вы пытаетесь решить?

...