Форум Flasher.ru

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)
-   Флейм (http://www.flasher.ru/forum/forumdisplay.php?f=53)
-   -   По графам (http://www.flasher.ru/forum/showthread.php?t=128237)

Герыч 03.08.2009 01:37
По графам
 
Пишу сюда, потому что по общим вопросам программирования ветки нет:mad:
Итак, есть n вершин, у каждой может быть максимум k рёбер. Как посчитать, сколько у всего графа будет максимально рёбер?
Это мне нужно, чтобы оптимально просчитать размер пула для динамического создания связей в желе.

Добавлено через 5 минут
Пока получается наверно такая формула: round(n*k/2)

r_r_f_r 03.08.2009 11:20
Используй списки, с ними флеш отлично дружит, только перед помещением в пул обязательно линки на частицы желе затереть нужно.

Герыч 03.08.2009 13:30
=) я сразу так сделал. Вопрос не в этом, вопрос в оптимальном размере для пула. Для каждой частицы я разрешаю максимум k связей, поэтому узнав эту формулу я узнаю оптимальный размер для пула. Вот как)
P.S. пул - это у меня связный список

r_r_f_r 03.08.2009 13:42
что-то не понимаю зачем нужен размер пула?// извиняюсь если что:)

Element:
Код AS3:
 

public static var pool:Element;

public var next:Element;

public var prev:Element;
Container:
Код AS3:
public function addElement(value:Element):Element

{

        Element.pool.prev = value;

        value.next = Element.pool;

        value.prev = null;

        Element.pool = value;

        return element;

}

 

public function removeElement(value:Element):void

{

        if (value == Element.pool)

        {

                Element.pool = Element.pool.next;

        }

        else

        {

                value.prev.next = value.next;

                value.next.prev = value.prev;

        }

        value.next = null;

        value.prev = null;

}

 

public function doSmt():void

{

        var element:Element = Element.pool;

        while (element)

        {

//                element.doSmt();

                element = element.next;

        }

}
Всё же нужно вчитываться лучше, ступил, сорри.
Но всё таки я не понимаю, зачем в списке нужен размер?
Ты же не выделяешь пямять под него.

Герыч 03.08.2009 13:51
Ты путаешь пул со связным списком.
Сам пул я организовал как связный список(это не так важно, это чисто реализация), но его сначала надо инициализировать некоторым числом элементов. Поскольку у меня почти гарантированно происходит ситуация, когда у каждой частицы желе будет достигнуто максимальное число связей, то пул мне лучше сразу инициализировать нужным числом объектов - связей.

r_r_f_r 03.08.2009 14:03
Ну хозяин как говорится - барин.
Но формула у вас неверна, при к=5 и n=3, а на другую мозгов не хватает.

Я бы сделал инициализацию по требованию.
Код AS3:
curentEelement = Element.pool ? Element.pool : Element.pool = new Element();

Герыч 03.08.2009 14:08
Сейчас именно такая инициализация)
Просто
Цитата:
Сообщение от Герыч (Сообщение 840150)
...у меня почти гарантированно происходит ситуация, когда у каждой частицы желе будет достигнуто максимальное число связей, то пул мне лучше сразу инициализировать нужным числом объектов - связей.
а, я забыл про k и n сказать) k<<n, т.е. к примеру n=200, k=20

r_r_f_r 03.08.2009 14:18
Тут тем более, я не знаю математического способа как можно описать "много меньше":)

Герыч 03.08.2009 14:19
Так, зря я всех тут тревожил. Я просто немного ошибся. Формула отлично работает)
P.S. На будущее: перепроверять код, написанный в час ночи=)

udaaff 03.08.2009 15:00
Количество ребер, по идее, будет зависеть от того, как мы соединим вершины. Поэтому точную формулу, скорее всего, вывести нельзя. Есть формула для полного графа, где все вершины соединены: n * (n - 1) / 2. Т.е. как твоя формула, только без округления, так как оно тут не нужно. В правильной формуле округление бы не понадобилось.
К примеру: У графа с четырьмя вершинами и максимальным количеством ребер 2, может быть 4 ребра, а может быть и три.

$mival 03.08.2009 15:45
Цитата:
Сообщение от udaaff (Сообщение 840174)
Количество ребер, по идее, будет зависеть от того, как мы соединим вершины. Поэтому точную формулу, скорее всего, вывести нельзя. Есть формула для полного графа, где все вершины соединены: n * (n - 1) / 2. Т.е. как твоя формула, только без округления, так как оно тут не нужно. В правильной формуле округление бы не понадобилось.
К примеру: У графа с четырьмя вершинами и максимальным количеством ребер 2, может быть 4 ребра, а может быть и три.
вообще то там считаются максимумы, об это мнаписано: максимум k рёбер ... сколько у всего графа будет максимально рёбер?

Герыч 03.08.2009 22:23
Да, максимумы. Я просто объясняю форумулу:
каждой вершине присвоим число k, а потом будет брать любые 2 вершины и уменьшать число, приписанное вершине на 1, а число рёбер увеличивать на 1. Как не думай, больше чем k*n/2 раз не получится.


Часовой пояс GMT +4, время: 03:06.

Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2026, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.