• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Algorytm A*



    Podstrony: 1 [2] [3] [4] [5]
    Przeczytaj także...
    Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.Algorytm SMA* – algorytm przeszukiwania grafu, odnajdujący najkrótszą ścieżkę pomiędzy dwoma danymi wierzchołkami grafu (lub dokładniej, między wierzchołkiem początkowym a dowolnym z wierzchołków docelowych).

    Algorytm A* – algorytm heurystyczny znajdowania najkrótszej ścieżki w grafie ważonym z dowolnego wierzchołka do wierzchołka spełniającego określony warunek zwany testem celu. Algorytm jest zupełny i optymalny, w tym sensie, że znajduje ścieżkę, jeśli tylko taka istnieje, i przy tym jest to ścieżka najkrótsza. Stosowany głównie w dziedzinie sztucznej inteligencji do rozwiązywania problemów i w grach komputerowych do imitowania inteligentnego zachowania.

    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.Analiza składniowa (ang. parsing) – w informatyce i lingwistyce – proces analizy tekstu, w celu ustalenia jego struktury gramatycznej i zgodności z gramatyką języka. Słowo parsing pochodzi od (łac.) pars (ōrātiōnis), które oznacza część mowy.

    Algorytm został opisany pierwotnie w 1968 roku przez Petera Harta, Nilsa Nilssona oraz Bertrama Raphaela. W ich pracy naukowej został nazwany algorytmem A. Ponieważ jego użycie daje optymalne zachowanie dla danej heurystyki, nazwano go A*.

    Spis treści

  • 1 Działanie algorytmu
  • 1.1 Przykład ilustrujący działanie
  • 1.2 Algorytm A* w pseudokodzie
  • 2 Cechy algorytmu A*
  • 2.1 Przypadki graniczne
  • 3 Dlaczego A* jest dopuszczalny oraz optymalny obliczeniowo?
  • 4 Złożoność czasowa
  • 5 Zastosowanie
  • 5.1 Algorytm A* w analizie składniowej PCFG
  • 5.1.1 Przykład działania
  • 5.1.2 Heurystyka
  • 5.1.3 Efekty
  • 6 Przypisy
  • 7 Bibliografia
  • 8 Linki zewnętrzne
  • Probabilistyczna (stochastyczna) gramatyka bezkontekstowa (PCFG, ang. probabilistic context-free grammar, SCFG, ang. stochastic context-free grammar) to gramatyka bezkontekstowa, do której dołączono prawdopodobieństwa występujących w niej reguł (produkcji). Prawdopodobieństwa produkcji dołącza się w taki sposób, aby suma prawdopodobieństw reguł o tym samym poprzedniku wynosiła 1.Przeszukiwanie w głąb (ang. Depth-first search, w skrócie DFS) – jeden z algorytmów przeszukiwania grafu. Przeszukiwanie w głąb polega na badaniu wszystkich krawędzi wychodzących z podanego wierzchołka. Po zbadaniu wszystkich krawędzi wychodzących z danego wierzchołka algorytm powraca do wierzchołka, z którego dany wierzchołek został odwiedzony.


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



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

    Warto wiedzieć że... beta

    Heurystyka (gr. heuresis – odnaleźć, odkryć, heureka – znalazłem) - w informatyce metoda znajdowania rozwiązań, dla której nie ma gwarancji znalezienia rozwiązania optymalnego, a często nawet prawidłowego. Rozwiązań tych używa się np. wtedy, gdy pełny algorytm jest z przyczyn technicznych zbyt kosztowny lub gdy jest nieznany (np. przy przewidywaniu pogody lub przy wykrywaniu niektórych zagrożeń komputerowych, takich jak wirusy lub robaki). Metody używa się też często do znajdowania rozwiązań przybliżonych, na podstawie których później wylicza się ostateczny rezultat pełnym algorytmem. To ostatnie zastosowanie szczególnie dotyczy przypadków, gdy heurystyka jest wykorzystywana do nakierowywania pełnego algorytmu ku optymalnemu rozwiązaniu, aby zmniejszyć czas działania programu w typowym przypadku bez poświęcania jakości rozwiązania (np. algorytm A*).
    DOI (ang. digital object identifier – cyfrowy identyfikator dokumentu elektronicznego) – identyfikator dokumentu elektronicznego, który w odróżnieniu od identyfikatorów URL nie zależy od fizycznej lokalizacji dokumentu, lecz jest do niego na stałe przypisany.
    Problem najkrótszej ścieżki jest zagadnieniem polegającym na znalezieniu w grafie ważonym najkrótszego połączenia pomiędzy danymi wierzchołkami. Szczególnymi przypadkami tego problemu są problem najkrótszej ścieżki od jednego wierzchołka do wszystkich innych oraz problem najkrótszej ścieżki pomiędzy wszystkimi parami wierzchołków.
    Przeszukiwanie wszerz (ang. Breadth-first search, w skrócie BFS) – jeden z najprostszych algorytmów przeszukiwania grafu. Przechodzenie grafu rozpoczyna się od zadanego wierzchołka s i polega na odwiedzeniu wszystkich osiągalnych z niego wierzchołków. Wykorzystywany jest do odnajdywania najkrótszej drogi w grafie. Wynikiem działania algorytmu jest także drzewo przeszukiwania wszerz o korzeniu w s, zawierające wszystkie wierzchołki do których prowadzi droga z s. Algorytm działa prawidłowo zarówno dla grafów skierowanych jak i nieskierowanych.

    Reklama

    Czas generowania strony: 0.028 sek.