Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C#] Генератор случайных графов

Автор: Tolo 17.5.2007, 15:30

Нужно реализовать генератор случайных графов, используя модель случайного графа.

Моделью случайного графа называется классическая математическая модель, которая должна рассмотреть все возможные рёбра и включить в граф каждое ребро с фиксированной вероятностью p. Если мы хотим, чтобы число рёбер графа было равно E, мы должны выбрать вероятность p=2E/V(V-1)
V - количество вершин

Я написал прогу которая генерирует вершины с вероятностью p=100/V, тоесть у каждой вершины есть равные шансы "выпасть". Реализовано при помощи СиШарповской функции random, насколько я знаю, управлять вероятностью в этой функции нельзя...
Помогите, пожалуйста, реализовать генератор с управляемой вероятностью "выпадения" вершин.

Автор: ivashkanet 17.5.2007, 17:05

Цитата(Tolo @ 17.5.2007, 14:30

)

управлять вероятностью

Ты будешь, как минимум, самым богатым человеком на свете, если сделаешь это smile

Если нужно выбирать узел с учетом его веса, то посмотри тему http://forum.vingrad.ru/index.php?show_type=forum&showtopic=150854

Автор: Tolo 17.5.2007, 17:13

Цитата

Ты будешь, как минимум, самым богатым человеком на свете, если сделаешь это

хех, ну я имел ввиду, задать(выбрать) эту вероятность. Формула есть smile

Автор: ivashkanet 17.5.2007, 17:22

А что мешает прогнать рандом на отрезке [0;1], получить число и сравнить с 2E/V(V-1), если меньше, то попало (берем ребро), если больше, то не попало

Т.е. если вероятность события: 0,235. Рандом дал 0,1236 то событие наступило, 0,59 -- событие не наступило

P.S. В первом посте я просто указал на неточность определения

Автор: Tolo 17.5.2007, 19:23

Вот в том то и дело, что до меня, хоть убей, не доперает как это всё реализовать...:(
Этозадание на курсовой проект, что ещё хуже...
Если ты сможешь мне помочь именно с реализацией, то буду на тебя молиться недели две smile

Там я прикрепил прогу(код)...если есть время и желание, посмотри, что можно сделать пожаласта...

Автор: ivashkanet 18.5.2007, 11:53

Tolo, сначала конкретизируй вопрос, а то непонятно что именно ты хочешь: либо просто помощи в конкретном вопросе (тогда нужно этот вопрос конкретизировать), либо чтобы тебе просто решили задачу (тогда непонятен смысл двух последних абзацев) smile

"Управляемая" вероятность
Долго мучался как же назвать метод. Все равно не удовлетворен.

Код


        private  Random _random = new Random();

        /// <summary>
        /// Определяет произошло ли событие с заданной вероятностью
        /// </summary>
        /// <param name="probability">Вероятность наступления события</param>
        /// <returns>Произошло ли событие с заданной вероятностью</returns>
        public bool IsIncidentOccur(double probability)
        {
            if (0 < probability && probability > 1)
                throw new ArgumentOutOfRangeException("Вероятность события должна быть от 0 до 1");


            double currentRandomValue = _random.NextDouble();

            if (currentRandomValue <= probability) return true;
            else return false;
        }

Но в данном случае это не важно, так как вероятность "p=2E/V(V-1)" просто утверждает, что все ребра графа равновероятны!
E --- реальное количество ребер, V(V-1)/2 --- количество возможных вариантов ребер

Поэтому забей на свою "управляемую вероятность" и случайным образом формируй ребра графа.

Цитата(Tolo @ 17.5.2007, 18:23

)

Там я прикрепил прогу(код)...

Мало кто будет анализировать большой кусок чужего кода, поэтому локализируй проблемный код и выложи его здесь

P.S. Откуда взялось число p=100/V? С потолка?

Автор: ivashkanet 18.5.2007, 13:13

Судя по всему, проблема в следующем коде:

Код


        private void buRandom_Click(object sender, EventArgs e)
        {
                       
            Random rnd = new Random();
            smezh = new double[N, N];
            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    dgv1.Rows[i].Cells[j].Value = 0;

            // Начало проблемного кода
            for (int i = M; i > 0; i--)
            {
                V = rnd.Next(0, N);
                S = rnd.Next(0, N);
                dgv1.Rows[V].Cells[S].Value =
                    dgv1.Rows[S].Cells[V].Value = 1;
            } // Конец проблемного кода
            
            buEdit_Click(this, null);
            toolStripStatusLabel1.Text = "Заполнено случайно";
        }

Нужно так изменить его, чтобы мы в итоге получили M ребер, случайно распределенных в графе.

Формализуем задачу: требуется равномерно заполнить часть матрицы N*N расположенную ниже главной диагонали.

Или еще формальней: как выбрать m элементов (реальных ребер) среди n элементов (возможных ребер) (m < n).

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