Monthly Archives: June 2012

Алгоритъмът на Дейкстра, реализиран с приоритетна опашка и написан на C#

Кой е Дейкстра?

Едсхер Дейкстра е холандски учен със значителни постижения в компютърните науки:
dijkstra

  • Независимо, заедно с колегата си Фридрих Бауер, са преоткрили алгоритъма обратен полски запис. Целяли са да намалят ползваната компютърна памет като използват стека за правене на изчисления.
  • Създател на алгоритма Shunting yard, който се използва за преобразуване на нормален израз в обратен полски запис.
  • Създател на алгоритъмът на Дейкстра, който открива най-кратък път в граф с положителни ребра.
  • Създал концепцията за семафора, която цели координация на множество програми и процесори.
  • Създател на алгоритъма на Банкер.
  • Един от създателите на първия компилатор на ALGOL 60. Двамата с неговия колега Яп Зонфилд си обещали да не се бръснат, докато не приключат компилатора. Създаденият компилатор бил един от първите, поддържащи рекурсия.
  • Голям противник на GOTO, той пишел статии срещу тази конструкция и спомогнал много за всеобщото й неодобрение. Заедно с това той прокарал идеята си за структурно програмиране, което вместо GOTO използва WHILE и FOR в кратки програмни блокове и избягва спагети кода.
  • Създал концепцията самостоятелна стабилизация, чиято цел била да накара една система да завърши правилно работата си при каквито и да е входни данни. Благодарение на откриването на тази концепция, Дейкстра е награден след близо 30 години с една от най-престижните награди в компютърното общество 2002 ACM PODC Influential-Paper Award, която по-късно е преименувана на “награда на Дейкстра”.
  • Награден с А.М. Тюринг

Алгоритми за най-кратък път в граф

Има различни алгоритми за намиране на най-кратък път граф – това е сумата на теглата на ребрата, през които минаваме от стартовия връх до целта. Три от най-известните алгоритми за намираме на най-кратките разстояния от конкретен връх до всички останали са алгоритмите на Форд-Белман, Флойд и Дейкстра.

И трита алгоритъма се основават на неравенството на триъгълника. Т.е. сумата на дължините на кои да е две страни е по-голяма от дължината на третата му страна. Всеки от тези алгоритми се основава на последователна проверка на (някои от) неравенствата на триъгълника и, в случай на нарушение, установяване в равенство.

Алгоритъмът на Форд-Белман има сложност Θ(n3). При него получаваме пътищата от стартовия връх до всички останали. Алгоритъмът работи с произволни тегла на ребрата – отрицателни и положителни. Полезно свойство на алгоритъма на Форд-Белман е, че позволява да се открие отрицателен цикъл, ако съществува такъв.

Алгоритъмът на Флойд е подобен на този на Форд-Белман. Той отново има сложност Θ(n3). След приключване на работата му обаче, при него получаваме разстоянията между всяка двойка върхове в графа. Отново, както при алгоритъма на Флойд, отрицателните ребра не са проблем, стига да няма отрицателни цикли.

Алгоритъмът на Дейкстра за най-кратък път в граф

Най-ефективният метод за намиране на най-кратките пътища от един връх до всички останали е алгоритъмът на Дейкстра. За да работи алгоритъмът, теглата трябва да са положителни. Повече информация за това как точно работи алгоритъма, както и анимации – тук. Сложността на алгоритъма е Θ(n2), но при използване на приоритетна опашка, тя може да спадне до Θ(n.log2n).

Алгоритъм на Дейкстра с приоритетна опашка, написан на C#

Понеже в библиотеката на C# няма реализация на приоритетна опашка, ще използваме класа OrderedBag<T> от колекцията Power Collections на Wintellect, която представлява сортирано мултимножество.

Първото нещо, което трябва да направим е един клас, който ще представя връх в граф. В него ще имаме – име на върха, цена, дали е бил посетен, кой е предишния връх, през който сме стигнали, за да стигнем до него и списък с децата му и цената(теглото на реброто) до всяко дете. Сорс-код:

class Vertex : IComparable<Vertex>
{
    public string Name { get; set; }
    public Vertex Previous { get; set; }
    public uint Cost { get; set; }
    public bool Visited { get; set; }
    public Dictionary<Vertex, uint> Children { get; set; }

    public Vertex(string name)
    {
        this.Name = name;
        this.Previous = null;
        this.Cost = int.MaxValue;
        this.Visited = false;
        this.Children = new Dictionary<Vertex, uint>();
    }
 
    public override bool Equals(Object obj)
    {
        if (this == obj)
        {
            return true;
        }

        Vertex other = obj as Vertex;
 
        if (other == null)
        {
            return false;
        }
 
        if (!this.Name.Equals(other.Name))
        {
            return false;
        }
        return true;
    }
 
    public override int GetHashCode()
    {
        return this.Name.GetHashCode();
    }

    public int CompareTo(Vertex other)
    {
        return this.Cost.CompareTo(other.Cost);
    }
}

Конструктора задава по подразбиране за предишен връх – null. Това ще ние полезно по-нататък при изпечатването на пътя. Задава се цена на пътя максималното int число. Ако реалната цена на пътя надвиши това число, алгоритъма няма да работи коректно. При необходимост, може да се промени на друго число или да се реализира по друг начин с цел избягване на препълване. Отбелязваме, че не е бил посетен. Децата пазим в речник, който хешира по име и пази в една променлива теглото на реброто към съответното дете. Теглата могат да са само положителни, тъй като алгоритъмът на Дейкстра работи само с такива.

Следва сорс-код на алгоритъма на Дейкстра:

static void ExecuteDijkstra(Vertex start)
{
    OrderedBag<Vertex> pQueue = new OrderedBag<Vertex>();
    start.Cost = 0;
    pQueue.Add(start);

    while (pQueue.Count > 0)
    {
        Vertex current = pQueue.RemoveFirst();
        current.Visited = true;
        foreach (Vertex child in current.Children.Keys)
        {
            if (child.Visited == false)
            {
                if (child.Cost > current.Cost + current.Children[child])
                {
                    child.Previous = current;
                    child.Cost = current.Cost + current.Children[child];
                    pQueue.Add(child);
                }
            }
        }
    }
}

За да намерим разстоянието от стартовия до текущия връх, се опитваме да оптимизираме с децата на текущия. За всяко дете, което е по-близко, го добавяме в приоритетната опашка. Докато не свършат върховете повтаряме процедурата като всеки път се обработва елементът, който е най-близо до стартовия връх.

Нека тестваме алгоритъма. Ще въведем неориентиран граф, но алгоритъмът работи също толкова успешно и с ориентиран:
dijkstra-algorithm-example-graph
Ще пуснем алгоритъма на Дейкстра от върха “A”. След това ще изпечатаме резултатите. Имаме разнообразни сценарии – има по няколко пътя до някои върхове, а до други – нямаме въобще. Можем да хард-коуд-нем графа по следния начин:

static void Main(string[] args)
{
    List<Vertex> graph = new List<Vertex>();
    graph.Add(new Vertex("A")); //0            
    graph.Add(new Vertex("B")); //1
    graph.Add(new Vertex("C")); //2
    graph.Add(new Vertex("D")); //3
    graph.Add(new Vertex("E")); //4
    graph.Add(new Vertex("F")); //5
    graph.Add(new Vertex("G")); //6
    graph.Add(new Vertex("H")); //7
    graph.Add(new Vertex("I")); //8
    graph.Add(new Vertex("J")); //9

    graph[0].Children.Add(graph[1], 23);
    graph[0].Children.Add(graph[7], 8);

    graph[1].Children.Add(graph[0], 23);
    graph[1].Children.Add(graph[3], 3);
    graph[1].Children.Add(graph[6], 34);

    graph[2].Children.Add(graph[7], 25);
    graph[2].Children.Add(graph[3], 6);
    graph[2].Children.Add(graph[9], 7);

    graph[3].Children.Add(graph[1], 3);
    graph[3].Children.Add(graph[2], 6);

    graph[4].Children.Add(graph[5], 10);

    graph[5].Children.Add(graph[4], 10);

    graph[6].Children.Add(graph[1], 34);

    graph[7].Children.Add(graph[0], 8);
    graph[7].Children.Add(graph[9], 30);
    graph[7].Children.Add(graph[2], 25);

    graph[9].Children.Add(graph[7], 30);
    graph[9].Children.Add(graph[2], 7);

    Vertex start = graph[0]; //"A"

    ExecuteDijkstra(start);
    PrintPaths(graph, start);
}

Функциите за отпечатване:

static void PrintPaths(List<Vertex> graph, Vertex start)
{
    foreach (Vertex vertex in graph)
    {
        if (vertex.Name != start.Name)
        {
            if (vertex.Cost == int.MaxValue)
            {
                Console.WriteLine("No path between " 
                    + start.Name + " and " + vertex.Name + ".");
            }
            else
            {
                Console.Write("The path between "
                    + start.Name + " and " + vertex.Name + " is: ");
                PrintPath(vertex);
                Console.WriteLine("and has a length of " + 
                    vertex.Cost + ".");
            }
        }
    }
}

static void PrintPath(Vertex v)
{
    if (v.Previous != null)
    {
        PrintPath(v.Previous);
    }
    Console.Write(v.Name + " ");
}

Как разпечатваме? Преминаваме през всеки връх на графа, с изключение на стартовия, и ако цената му е максималният int, значи не сме стигнали до него и той е в друга компонента на свързаност. Ако цената не е максималният int, значи сме стигнали до него по някакъв начин . Как да открием пътя? Помните ли, че записвахме в една променлива от кой връх сме дошли, за да стигнем до текущия. Остава да пуснем една изключителна проста рекурсия и да отпечатаме върха. Цялостната цена пазим в променливата Cost. Печатаме и нея. Резултата от изпълнението на всичкия код:
priority queue dijkstra algorithm graph example result

Какво е SEO и защо е важно да се прави?

Search engine optimization

Какво означава SEO? SEO значи Search Engine Optimization. На български това се превежда като оптимизация за търсещи машини. Най-вероятно сте чували този термин и искате да научите повече за тази техника. Поне 99% от потребителите на Интернет са използвали Google.com и повечето от тях са наясно, че това е търсеща машина. Всеки път, в който напишете някакви думи в търсачката на Google, тя бълва резултати с доста бърза скорост. И всеки път получавате най-релевантните на търсените думи резултати в мрежата.

Ако решите да стартирате уеб сайт днес, който да напълните с релевантно на вашата ниша съдържание, ще бъдете ли на първите страници в Google? Възможно е, но е трудно. Защо? Защото е нужно да познавате как Google или всяка друга търсачка оперира.

Търсещите машини обхождат уеб сайтовете често и индексират страниците им. Индексирането е процес, при който търсещите машини съпоставят уеб страниците на съответните им ключови думи и ги класират според тяхната популярност и релевантност. Накрая, когато търсите в Google по дадена дума, вие ще видите най-добрите резултати на първата страница и с всяка следваща страница качеството на резултатите, които ще получавате, ще се влошава.

SEO или оптимизирането за търсещи машини спомага по-доброто класиране на уеб страница в Интернет. Как? Прочетете по-долу…

Какво е SEO?

Search engine optimization

SEO е процес, който помага на търсещите на машини да открият съдържанието на сайта ви и да го класират на базата на ключови думи и линкове. Главната цел на SEO е да увеличи трафика към вашия уеб сайт.

  • Кой печели от SEO? Собственика на сайта.
  • По какъв начин печели собственикът на сайта? Чрез повече трафик.
  • Как SEO набира трафик? Когато се класирате високо за определена ключова дума, вашият сайт става видим и когато някой пусне заявка в търсеща машина за същата ключова дума има все по-голям шанс вашият сайт да излезе по-напред и да бъде посетен.
  • Какви типове SEO има? Има само два типа SEO – White Hat SEO и Black Hat SEO. White Hat SEO е термин, описващ етичните SEО практики. Black Hat SEO е точно обратното – това са лошите практики, които са забранени и се наказват от тъсещите машини.

Защо SEO е важно да се прави?

Search engine optimization

Ако искате вашият уеб сайт да бъде на първа страница в Google и да печели трафик, той трябва да е ооптимизиран за това. Успехът на един уеб сайт зависи от това колко добре е оптимизиран за търсещите машини. Никой не би искал да влиза в уеб сайтове, които не се посещават. Статистиките показват, че повече от 85% от трафика в Интернет идва от търсещите машини. Това е доста голям трафик и той може да се насочва.

Няколко причини защо е важно да се прави SEO

  • SEO ви дава трафик
  • Добре оптимизирираните уеб страници са обожавани от търсещите машини
  • По-голямата част от уеб трафика в Интернет идва от търсещите машини
  • SEO може да увеличи вашите продажби феноменално
  • SEO е икономически ефекетивна
  • SEO дава авторитет на вашия уеб сайт. Увеличава PageRank-а му.

Какво включва SEO?

Search Engine Optimization
Ключовите думи са най-важният елемент в целия SEO процес. Това е първата крачка в SEO. Подборът на правилна или грешна ключова дума може да даде голяма разлика. Когато публикувате съдържание на вашия сайт, важно е да спрете и да помислите кои ключови думи му отговарят. Важните фактори при ключовите думи, които се вземат под внимание от търсещите машини са подобора на ключови думи, честотата на ключовите думи, същите в линкове и имена на файлове, ключови думи в заглавия на страници, заглавия и съдържание.

Линковете са също много важен фактор в процеса на оптимизация за търсещите машини. Линковете представят полулярността на уеб сайта ви. Има два типа линкове – входящи и изходящи. Входящите линкове са тези, които идват от чужди уеб сайтове и сочат към вашия, а изходящите линкове са такива, които са във вашия сайт и сочат към чужди. Колкото по-висок е броят на качествените линкове, сочещи към вашия сайт, толкова по-високо ще бъде класиран той. Такива типове линкове (входящи) могат да се създадат чрез регистриране на вашия сайт в различни директории, чпрез споделяне във форуми, статии и други сайтове.

Мета таговете са обобщение на уеб страницата. Те могат да бъдат използвани, за да спцифицират описание, ключови думи и други мета данни, които не са написани другаде. Мета тагове се състоят от мета описание, мета ключови думи и мета роботи. Важно е да се отбележи, че важността на мета таговете спада много и те вече не се считат за голям фактор при класирането на уеб сайта ви в търсещите машини.

Съдържанието е кралят на онлайн бизнеса, същото може да бъде казано и в смисъла на SEO. Уеб сайт със съдржание, което не се харесва на хората, не се харесва и на търсещите машини. Важно е да се създаде съдържание, което се харесва от хората и от търсачките. Няма смисъл от подхвърляне на безсмислено съдържание, което не е итнересно никому. Качественото съдържание носи входящи линкове от други сайтове, а те носят популярност на вашия уеб сайт. Никога не дублирайте съдържание от друг уеб сайт. Това се хваща изключително лесно от търсещите машини и се наказва сериозно. Съдържанието на вашия уеб сайт трябва да бъде уникално, атрактивно и полезно на вашите читатели, както и да бъде добре оптимизирано за тъсещите машини.

Визуалните екстри са картинките, видеата, флаш-анимациите, звуците, javascript и други, които търсещите машини не могат да индексират. Но дори да не могат да се индексират, тези компомпненти на вашия уеб сайт трябва да бъдат поднесени с подхгодящи описания, за да може да се индексират поне самите файлове. Има няколко важни неща, които трябва да се спазват, когато става въпрос за визуални екстри и SEO:

  • Избягвайте картинки, които показват текст. Те не могат да се прочетат от търсещите машини. Осигурете подходящо описание на каритнките в “alt” атрибута на <img> тага.
  • Винаги осигурявайте информация за анимация и филмчета в “alt” тага.
  • Можете да използвате <noscript> тага, за да осигурите алтернативно съдържание за потребителите, които са изключили скриптовете в техния браузър.

Search Engine Optimization
Важността на SEO няма да намали в близко бъдеще. Ако искате да правите пари онлайн, първото нещо, от което трябва да разбира е SEO. Разбира се, SEO не е единственият начин да докарате трафик до вашия уеб сайт, но със сигурност е най-ефиктивният.