|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Comoderator Of Ru Algorithms 2:5002/46.4 10 Apr 2003 08:01:52
To : All
Subject : 2 faq
--------------------------------------------------------------------------------
Все эти подсчеты производились для не префиксных кодов Хаффмана т.е.
кодов, которые нельзя идентифицировать однозначно. Hапример код A - 01011 и
код B - 0101 . Если мы будем получать эти коды побитно, то получив биты 0101
мы не сможем сказать какой код мы получили A или B , так как следующий бит
может быть как началом следующего кода, так и продолжением предыдущего.
Hеобходимо добавить, что ключем к построению префиксных кодов служит
обычное бинарное дерево и если внимательно рассмотреть предыдущий пример
с построением дерева , можно убедится , что все получаемые коды там
префиксные.
Одно последнее примечание - алгоритм Хаффмана требует читать входной
файл дважды , один раз считая частоты вхождения символов , другой раз
производя непосредственно кодирование.
P.S. О "ключике" дающем дорогу алгоритму Running.
---- Прочитав обзорную информацию о Huffman кодировании подумайте
над тем, что на нашем бинарном дереве может быть и 257
листиков.
Литература :
------------
1) Описание архиватора Narc фирмы Infinity Design Concepts, Inc.;
2) Чарльз Сейтер,'Сжатие данных', "Мир ПК",N2 1991;
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
Q33. Перевод 256цв-2цв
A: Alexander (2:5015/103.19)
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
Делаешь так:
Каждый цвет по палитре переводишь в твойку (R,G,B), потом считаешь общую
интенсивность по формуле I = 0.229*R+0.587*G+0.114*B, если общая интенсивность
больше некого порогового значения (попробуй его менять - интересная штука
получится), то результирующий цвет - 1, иначе - 0.
A: Sergey Belikov (2:5054/67.4)
Если тебе нужно сделать из цветной картинки ч/б или ч/к и т.д., вобщем
алгоритм такой ((r+g+b)/3) - нахождение яркости r=g=b=((r+g+b)/3)- для ч/б
r=((r+g+b)/3) g=0 b=0 для з/ч. Можно сделать для любого цвета, находишь
процентное содержание красного, зеленого, синего, потом соответсвенно
умножаешь каждый коэффицент на яркость.
ОТ РЕДАКЦИИ: существует очень много различных моделей, какую использовать -
решать только вам. Я могу предложить еще так:
y=0.299r+0.587g+ 0.114b
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
Q34. Алгоритм нахождения оптимальной траэктории (динамическое
программирование).
A: Sergey Novak (2:469/138.1)
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
AM> Конкретно интересует алгоритм нахождения оптимальной траектории,
AM> основанные на принципе Беллмана. В инете искал - честно не нашел :^(
Раз уж за долгий промежуток времени никто не ответил, попробую я.
Для тех кто не знает скажу, что этот алгоритм нужен для максимизации или
минимизации в неклассических задачах. Hапример, для нахождения оптимального
пути для максимизации скорости в случае если на каджом участке максимальная
развиваемая скорость может быть различной (например, где то асфальт, где то
сельская дорога, а где то надо лес рубить чтоб пройти пешком) Иногда ведь
быстрей прорубить один метр леса вместо того, чтоб объезжать по асфальту 100
км. В общем зачем это нужно смысл ясен. Теперь "КАК".
В решении задач методом программирования Белмана заложен принцип оптимальности.
Он заключается в том, что любая оптимальная траектория оптимальна только от
своего начала и не имеет значения как система попала в данное состояние. Т.е.
каждый кусок заданной территории оптимален относительно своего начала.
Механизм нахождения оптимальной траектории лучше объяснять на примере. Hа
практике я его никогда не использовал.
Hапример, дана площадь M, которую надо пройти из А в Б по оптимальному пути,
затратив наименьшее количество денег, с учетом того, что в разных местах цена
преодоления площади различна.
Площадь разбивается на квадраты. Каждая сторона квадрата от этой площади
обозначается ценой за ее преодоление. Примерно вот так:
1 2 3 4
| | | | Б
1 ------- --70--- ---10-- ---5--- -------
| | | |
| 10 25 |
5 | | 15
| | | |
2 ------- ---15-- ---3--- -45---- -------
| | | |
8 5 30 50
| | | |
| | | |
4 ------- ---25-- ---15-- ---20-- -------
| | | |
15 5 35 5
| | | |
| | | |
5 ------- ---20-- --12--- --20--- -------
А | | | |
Задача решается от конечной точки Б с координатами 4:1, проставляя стрелки,
указывающие оптимальный путь из текущей точки к Б и цену за это.
Hачинаем заполнять цену, за определение пути.
В точку (3:2) можно добраться двумя путями: через (3:1) и через (4:2)
По первому пути цена равна 5+25=30
По второму : 15+45
Естественно, что в точку (3:2) выгодней добираться по первому пути.
1 2 3 4
| | | | Б
1 ------- --70--- ---10-- 5 ---5--- 0 -------
| | | ----> |
| 10 25 | |
5 | | | 15
| | | |
2 ------- ---15-- ---3--- 30 -45---- 15 -------
| | | |
8 5 30 5
| | | |
| | | |
3 ------- ---25-- ---15-- ---20-- -------
| | | |
15 5 35 5
| | | |
| | | |
4 ------- ---20-- --12--- --20--- -------
А | | | |
Далее считаем как лучше добраться в (2:2)
Варианты: либо через (2:1) , либо через (3:2)
через (2:1) цена равна 25
через (3:2) цена равна 33
Значит выбирается путь через (2:1)
Там где стоит "x" тот путь не выгоден
1 2 3 4
| | | | Б
1 ------- --70--- 15 ---10-- 5 ---5--- 0 -------
| | -----> | -----> |
| 10| 25 | |
5 | | | | 15
| | | | |
2 ------- ---15-- 25 ---3-x- 30 -45--x- 15 -------
| | | |
8 5 30 5
| | | |
| | | |
3 ------- ---25-- ---15-- ---20-- -------
| | | |
15 5 35 5
| | | |
| | | |
4 ------- ---20-- --12--- --20--- -------
А | | | |
А вот с точкой (1:1) получается интересно. В нее выгодней добираться через
(1:2). Так цена получится 45 у.е., в отличие от того, чтоб мы добирались по
прямой через (2:1). Тогда бы цена была 70.
1 2 3 4
| | | | Б
1 ------- 45--70--- 15 ---10-- 5 ---5--- -------
| | -----> | -----> |
| 10 | 25 | |
5 | | | | 15
| ------> | | | | |
2 ------- 40---15-- 25 ---3-x- 30 -45-x-- 15 -------
| | | |
8 5 30 5
| | | |
| | | |
3 ------- ---25-- ---15-- ---20-- 20 -------
| | | |
15 5 35 5
| | | |
| | | |
4 ------- ---20-- --12--- --20--- -------
А | | | |
В точку (3:3) выгодней добираться через (4:3) Цена будет 40 :
1 2 3 4
| | | | Б
1 ------- 45--70--- 15 ---10-- 5 ---5--- -------
| | -----> | -----> |
| 10 | 25 | |
5 | | | | 15
| ------> | | | | |
2 ------- 40---15-- 25 ---3-x- 30 -45-x-- 15 -------
| | | | .
8 5 30 5 |
| | | | |
| | | -------> | |
3 ------- ---25-- ---15-- 40 ---20-- 20 -------
| | | |
15 5 35 5
| | | |
| | | |
4 ------- ---20-- --12--- --20--- -------
А | | | |
Дальше все одинаково:
в (2:3) добираемся через (2:2) = 30 у.е.
в (1:3) через (1:2) за 48 у.е.
1 2 3 4
| | | | Б
1 ------- 45--70--- 15 ---10-- 5 ---5--- -------
| | -----> | -----> |
| 10 | 25 | |
5 | | | | 15
| ------> | | | | |
2 ------- 40---15-- 25 ---3-x- 30 -45-x-- 15 -------
| . | . | | .
8 | 5 | 30 5 |
| | | | | | |
| | | | | -------> | |
3 ------- 48---25-- 30 ---15-- 40 ---20-- 20 -------
| | | |
15 5 35 5
| | | |
| | | |
4 ------- ---20-- --12--- --20--- -------
А | | | |
В точку (3:4) попадаем за 45 через (4:4)
А в (2:4) через (2:3) за 35 у.е.
1 2 3 4
| | | | Б
1 ------- 45--70--- 15 ---10-- 5 ---5--- -------
| | -----> | -----> |
| 10 | 25 | |
5 | | | | 15
| ------> | | | | |
2 ------- 40---15-- 25 ---3-x- 30 -45-x-- 15 -------
| . | . | | .
8 | 5 | 30 5 |
| | | | | | |
| | | | | -------> | |
3 ------- 48---25-- 30 ---15-- 40 ---20-- 20 -------
| | . | | .
15 5 | 35 5 |
| | | | | |
| | | | ------> | |
4 ------- ---20-- 35 --12--- 45 --20--- 25 -------
А | | | |
И вот наконец настал решающий момент, когда считается последняя сумма и
становится очевидным результат:
1 2 3 4
| | | | Б
1 ------- 45--70--- 15 ---10-- 5 ---5--- -------
| | -----> | -----> |
| 10 | 25 | |
5 | | | | 15
| ------> | | | | |
2 ------- 40---15-- 25 ---3-x- 30 -45-x-- 15 -------
| . | . | | .
8 | 5 | 30 5 |
| | | | | | |
| | | | | -------> | |
3 ------- 48---25-- 30 ---15-- 40 ---20-- 20 -------
| | . | | .
15 5 | 35 5 |
| | | | | |
| ------> | | | ------> | |
4 ------- 55---20-- 35 --12--- 45 --20--- 25 -------
А | | | |
В итоге самая минимальная сумма, которую нужно вложить на преодоление пути 55
у.е.
1 2 3 4
| | | | Б
1 ------- 45--70--- 15 ---10-- 5 ---5--- -------
| | -----> | ------> |
| 10 | 25 |
5 | | | 15
| | | | |
2 ------- 40---15-- 25 ---3-x- 30 -45-x-- 15 -------
| | . | |
8 5 | 30 5
| | | | |
| | | | |
3 ------- 48---25-- 30 ---15-- 40 ---20-- 20 -------
| | . | |
15 5 | 35 5
| | | | |
| ------> | | | |
4 ------- 55---20-- 35 --12--- 45 --20--- 25 -------
А | | | |
Стрелки от точки А нам показывают как нужно двигаться и в каждой точке стоит
цена за преодоление пути от нее к точке Б.
Итак, оптимальный путь из (1:4) в (4:1) :
(1:4) > (2:4) > (2:3) > (2:2) > (2:1) > (3:1) > (4:1)
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
Q35. Построение 3D-ландшафтов
A: Mark Shevchenko (2:5093/27.77)
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
DK>>> Как можно постpоить yбедительный ландшафт? Сам я этой темой
DK>>> занимаюсь давно, но pезyльтаты меня не yдовлетвоpяют...
MS>> http://freespace.virgin.net/hugo.elias/models/m_perlin.htm
DK> Спасибо, конечно, но мне в инет залезать неохота, я за него плачy.
DK> Я пpосил эхотаг.
Понятно. Попpобyю на пальцах объяснить - но там, кyда я тебя отслал всё то же
самое с каpтинками и более пpодyманно выpажено (я же бyдy писать, как бог на
дyшy положит, сам понимаешь, вpемени на подготовкy нет).
Итак, там описана шyмовая фyнкция Пеpлина. Я здесь напишy, как она стpоится в
двyмеpном слyчае, на тpёхмеpный пеpеносится без пpоблем. Если на гpафик этой
фyнкции смотpеть (двyмеpный слyчай), то напоминает он сpез гоpной цепи, в
тpёхмеpном слyчае - обычный ландшафт.
Понятно, что мы должны по кооpдинате Х полyчать кооpдинатy У, пpичём такyю,
чтобы гpафик был "ландшафтным". Делается это в несколько пpоходов.
Сначала выбиpаешь интеpвал, где y тебя бyдет стpоится гpафик. Разбиваешь его на
N частей pавной шиpины, в каждой из pазбивающих точек беpёшь слyчайное число от
0 до 1 (нyжна фyнкция y = random(x), пpимеpы нескольких таких фyнкций можешь
найти в статье, :) в пpостейшем слyчае можешь воспользоваться паpой { srand(x);
--- GoldED+/386 1.1.4.7
* Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
faq |
Mike Galushkin |
06 Apr 2003 13:18:22 |
 faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 08:08:30 |
|
faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 07:57:54 |
|
faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 07:59:52 |
|
2 faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 07:59:52 |
|
faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 08:00:48 |
|
2 faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 08:00:48 |
|
faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 08:01:18 |
|
2 faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 08:01:18 |
|
faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 08:01:52 |
|
2 faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 08:01:52 |
 3 faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 08:01:52 |
 3 faq |
Stanislav Shwartsman |
10 Apr 2003 08:11:45 |
|
3 faq |
Andrey Dashkovsky |
11 Apr 2003 23:00:43 |
|
3 faq |
Stanislav Shwartsman |
12 Apr 2003 10:39:21 |
 3 faq |
Andrey Dashkovsky |
13 Apr 2003 11:31:29 |
 3 faq |
Stanislav Shwartsman |
14 Apr 2003 08:20:45 |
 3 faq |
Andrey Dashkovsky |
14 Apr 2003 22:21:35 |
|
3 faq |
Ruslan Tebuev |
14 Apr 2003 11:51:21 |
|
3 faq |
Andrey Dashkovsky |
14 Apr 2003 22:38:11 |
|
3 faq |
Ruslan Tebuev |
15 Apr 2003 16:46:02 |
|
3 faq |
Moderator |
14 Apr 2003 23:26:48 |
|
3 faq |
Zahar Kiselev |
13 Apr 2003 19:07:12 |
|
3 faq |
Moderator |
14 Apr 2003 23:30:46 |
|
3 faq |
Stanislav Shwartsman |
15 Apr 2003 08:10:17 |
|
3 faq |
Andrey Dashkovsky |
14 Apr 2003 22:19:31 |
|
Re: 3 faq - аппроксимация |
Yuri Burger |
15 Apr 2003 14:49:50 |
|
|
