Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [C#] Генератор случайных графов, Используя модель случайного графа 
:(
    Опции темы
Tolo
Дата 17.5.2007, 15:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 4
Регистрация: 10.5.2007

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

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

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

Присоединённый файл ( Кол-во скачиваний: 61 )
Присоединённый файл  generator.rar 88,36 Kb
PM MAIL   Вверх
ivashkanet
Дата 17.5.2007, 17:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Кодю потиху
****


Профиль
Группа: Участник Клуба
Сообщений: 3684
Регистрация: 23.2.2006
Где: Гомель, Беларусь

Репутация: 9
Всего: 149
Цитата(Tolo @  17.5.2007,  14:30 Найти цитируемый пост)
управлять вероятностью

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

Если нужно выбирать узел с учетом его веса, то посмотри тему Фунционал randome как в AdRotator


--------------------
design, simplicity, and experience with a technology focus
PM MAIL WWW ICQ   Вверх
Tolo
Дата 17.5.2007, 17:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 4
Регистрация: 10.5.2007

Репутация: нет
Всего: нет
Цитата
Ты будешь, как минимум, самым богатым человеком на свете, если сделаешь это

хех, ну я имел ввиду, задать(выбрать) эту вероятность. Формула есть smile
PM MAIL   Вверх
ivashkanet
Дата 17.5.2007, 17:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Кодю потиху
****


Профиль
Группа: Участник Клуба
Сообщений: 3684
Регистрация: 23.2.2006
Где: Гомель, Беларусь

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

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

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


--------------------
design, simplicity, and experience with a technology focus
PM MAIL WWW ICQ   Вверх
Tolo
Дата 17.5.2007, 19:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 4
Регистрация: 10.5.2007

Репутация: нет
Всего: нет
Вот в том то и дело, что до меня, хоть убей, не доперает как это всё реализовать...:(
Этозадание на курсовой проект, что ещё хуже...
Если ты сможешь мне помочь именно с реализацией, то буду на тебя молиться недели две smile
Там я прикрепил прогу(код)...если есть время и желание, посмотри, что можно сделать пожаласта...
PM MAIL   Вверх
ivashkanet
Дата 18.5.2007, 11:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Кодю потиху
****


Профиль
Группа: Участник Клуба
Сообщений: 3684
Регистрация: 23.2.2006
Где: Гомель, Беларусь

Репутация: 9
Всего: 149
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? С потолка?

Это сообщение отредактировал(а) Guedda - 18.5.2007, 12:26


--------------------
design, simplicity, and experience with a technology focus
PM MAIL WWW ICQ   Вверх
ivashkanet
Дата 18.5.2007, 13:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Кодю потиху
****


Профиль
Группа: Участник Клуба
Сообщений: 3684
Регистрация: 23.2.2006
Где: Гомель, Беларусь

Репутация: 9
Всего: 149
Судя по всему, проблема  в следующем коде:
Код

        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).

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

Это сообщение отредактировал(а) ivashkanet - 18.5.2007, 13:16


--------------------
design, simplicity, and experience with a technology focus
PM MAIL WWW ICQ   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0564 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.