• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Algorytm zachłanny



    Podstrony: 1 [2] [3] [4]
    Przeczytaj także...
    Teoria grafów to dział matematyki i informatyki zajmujący się badaniem własności grafów. Informatyka rozwija także algorytmy wyznaczające pewne właściwości grafów. Algorytmy te stosuje się do rozwiązywania wielu zadań praktycznych, często w dziedzinach na pozór nie związanych z grafami.Kryterium klasyfikacyjne - wyodrębnienie i przyporządkowanie obiektów, przedmiotów, istot, osób, zjawisk do określonego zbioru lub grupy, na podstawie ich istotnej i wspólnej cechy, według logicznych zasad.

    Algorytm zachłanny (ang. greedy algorithm) – algorytm, który w celu wyznaczenia rozwiązania w każdym kroku dokonuje zachłannego, tj. najlepiej rokującego w danym momencie wyboru rozwiązania częściowego. Innymi słowy algorytm zachłanny nie dokonuje oceny czy w kolejnych krokach jest sens wykonywać dane działanie, dokonuje decyzji lokalnie optymalnej, dokonuje on wyboru wydającego się w danej chwili najlepszym, kontynuując rozwiązanie podproblemu wynikającego z podjętej decyzji.

    Graf to – w uproszczeniu – zbiór wierzchołków, które mogą być połączone krawędziami, w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków (ilustracja po prawej stronie). Grafy to podstawowy obiekt rozważań teorii grafów. Za pierwszego teoretyka i badacza grafów uważa się Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich.Podzbiór – pewna „część” danego zbioru, czyli dla danego zbioru, nazywanego nadzbiorem, zbiór składający się z pewnej liczby jego elementów, np. żadnego, jednego, wszystkich. Pierwszy przypadek nazywa się podzbiorem pustym, drugi – podzbiorem jednoelementowym lub singletonem, trzeci – podzbiorem niewłaściwym.

    Typowe zadanie rozwiązywane metodą zachłanną ma charakter optymalizacyjny, jednak algorytm zachłanny nie zawsze odnajduje rozwiązanie optymalne.

    W dziedzinie sztucznej inteligencji zachłanna odmiana przeszukiwania lokalnego jest nazywana "podchodzeniem pod wzgórze".

    Madryt (hiszp. Madrid) – stolica i największe miasto Hiszpanii, położony w środkowej części kraju u podnóża Sierra de Guadarrama (Wyżyna Kastylijska) nad rzeką Manzanares.Własność optymalnej podstruktury – jest własnością problemów, które można rozwiązywać za pomocą algorytmów. Mówi się, że dany problem ma własność optymalnej podstruktury, jeżeli jego optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów.

    Spis treści

  • 1 Zbiór rozwiązań
  • 1.1 Przykład
  • 2 Rozwiązanie zachłanne
  • 2.1 Problem wydawania reszty
  • 3 Poprawność rozwiązania zachłannego
  • 3.1 Własność zachłannego wyboru
  • 3.2 Własność optymalnej podstruktury
  • 4 Przykłady algorytmów zachłannych
  • 5 Zobacz też
  • 6 Przypisy
  • 7 Bibliografia
  • Zbiór rozwiązań[]

    Niech C będzie zbiorem skończonym, takim, że wszystkie możliwe rozwiązania problemu P są podzbiorami C.

    Problem wydawania reszty – zagadnienie z dziedziny algorytmiki, problem polegający na wybraniu z danego zbioru monet o określonych nominałach takiej konfiguracji, by wydać żądaną kwotę przy użyciu minimalnej liczby monet. Jego rozwiązania są wykorzystywane w automatach z napojami, bankomatach itd.Algorytm szeregowania (ang. scheduler - planista) to algorytm rozwiązujący jedno z najważniejszych zagadnień informatyki - jak rozdzielić czas procesora i dostęp do innych zasobów pomiędzy zadania, które w praktyce zwykle o te zasoby konkurują.

    Musi być znane kryterium pozwalające oceniać jakość rozwiązania

    Przykład[]

    Dany jest problem znalezienia trasy podróży z Madrytu do Moskwy. Można na niego spojrzeć jako problem z dziedziny teorii grafów – jeżeli z wierzchołkami grafu utożsami się punkty podróży (miasta, lotniska, stacje kolejowe, skrzyżowania dróg itp.) a z krawędziami możliwe trasy przebiegu (autostrady, trasy przelotu samolotów, przejazdu pociągów itp.), z wagami odpowiadającymi kosztom podróży (odległości, ceny biletów itp.) to zadanie sprowadza się do odnalezienia minimalnej ścieżki łączącej wierzchołki opowiadające Madrytowi i Moskwie, a zbiór wszystkich rozwiązań C składa się z rozwiązań zarówno optymalnych jak i propozycji tras typu Madryt–Rzym–Moskwa czy nawet tak nieoptymalnych jak Madryt–RzymTel Awiw-JafaHongkong–Moskwa

    Algorytm Dijkstry, opracowany przez holenderskiego informatyka Edsgera Dijkstrę, służy do znajdowania najkrótszej ścieżki z pojedynczego źródła w grafie o nieujemnych wagach krawędzi.Tel Awiw-Jafa (hebr. תֵּל־אָבִיב-יָפוֹ, trl. Tel Aviv-Yafo, trb. Tel Awiw-Jafo; arab. تل ابيب-يافا trl. Til Abīb-Yāfū, trb. Til Abib-Jafu), zwyczajowo nazywane Tel Awiw, jest drugim pod względem wielkości miastem Izraela. Miasto jest położone w Dystrykcie Tel Awiwu na nadmorskiej równinie Szaron leżącej nad Morzem Śródziemnym. Tel Awiw zajmuje powierzchnię 51,8 km², będąc największym i najludniejszym miastem obszaru metropolitalnego Gusz Dan. Miasto jest zarządzane przez władze miejskie Tel Awiwu-Jafy, na czele których stoi burmistrz Ron Huldai.


    Podstrony: 1 [2] [3] [4]



    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Warto wiedzieć że... beta

    Minimalne drzewo rozpinające (ang. MST, Minimum Spanning Tree) – drzewo rozpinające danego grafu o najmniejszej z możliwych wag, tj. takie, że nie istnieje dla tego grafu inne drzewo rozpinające o mniejszej sumie wag krawędzi.
    Algorytm Kruskala wyznacza minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, o ile jest on spójny. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa. Jest to przykład algorytmu zachłannego.
    Programowanie dynamiczne jest techniką lub strategią projektowania algorytmów, stosowaną przeważnie do rozwiązywania zagadnień optymalizacyjnych. Jest alternatywą dla niektórych zagadnień rozwiązywanych za pomocą algorytmów zachłannych. Wynalazcą techniki jest amerykański matematyk Richard Bellman, uhonorowany za to odkrycie medalem IEEE (ang. medal of honour) w 1979 roku.
    Zbiór – pojęcie pierwotne teorii zbiorów (znanej szerzej jako teoria mnogości; za jej twórcę uważa się Georga Cantora) leżące u podstaw całej matematyki; intuicyjnie jest to nieuporządkowany zestaw różnych obiektów, czy też kolekcja niepowtarzających się komponentów bez wyróżnionej kolejności.
    Hongkong (oficj. Specjalny Region Administracyjny Hongkong; ang. Hong Kong, Hong Kong Special Administrative Region of the People’s Republic of China, chiń. 香港, kantoński jyutping: hoeng1 gong2, mandaryński pinyin: Xiānggǎng) – specjalny region administracyjny Chińskiej Republiki Ludowej (drugim regionem jest Makau), znajdujący się na wschodnim wybrzeżu Chin, nad Morzem Południowochińskim.
    Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.
    Optymalizacja - metoda wyznaczania najlepszego (optymalnego) rozwiązania (poszukiwanie ekstremum funkcji) z punktu widzenia określonego kryterium (wskaźnika) jakości (np. kosztu, drogi, wydajności).

    Reklama

    Czas generowania strony: 0.016 sek.