| dbo:abstract
|
- Der Simplified Memory-Bounded Algorithm (SMA*) ist ein Algorithmus zur speicheroptimierten Suche in Bäumen. Es ist ein Sonderfall des A*-Algorithmus' zur Berechnung eines kürzesten Pfades. Wenn der zu untersuchende Baum mit einem Greedy-Algorithmus durchsucht wird und nicht genügend Speicher vorhanden ist, um den kompletten Baum im Speicher zu halten, dann werden ungünstige Knoten bzw. Teilbäume zunächst ignoriert. Im Vorgängerknoten werden Informationen über die Kosten des Teilbaums gespeichert. Wenn bei den verbleibenden Teilbäumen kein besseres Ergebnis erzielt wird, kann die Berechnung an den günstigen vergessenen Knoten wieder aufgenommen werden. Der Einspareffekt beim Speicherverbrauch resultiert daraus, dass wenig erfolgversprechende Lösungsvarianten zunächst nicht im Speicher gehalten werden. (de)
- SMA* o o simplificado de memoria acotada A * es un algoritmo del camino más corto basada en el algoritmo A*. La principal ventaja de SMA * es que utiliza una memoria limitada, mientras que el algoritmo A * puede ser que necesite memoria exponencial. Todas las demás características de SMA * son heredados de A *. (es)
- SMA* or Simplified Memory Bounded A* is a shortest path algorithm based on the A* algorithm. The main advantage of SMA* is that it uses a bounded memory, while the A* algorithm might need exponential memory. All other characteristics of SMA* are inherited from A*. (en)
- SMA*, acronimo di Simplified Memory-Bounded A*, è un algoritmo euristico per la ricerca del cammino minimo basato sull'algoritmo A*, proposto dall'informatico anglo-statunitense nel 1992. Il vantaggio principale di SMA* è l'uso limitato della memoria, al contrario di A* che ha bisogno, nel caso peggiore, di uno spazio esponenziale. Tutte le altre caratteristiche di SMA* derivano direttamente da A*, incluse le prestazioni in termini di tempo, che nel caso peggiore rimangono esponenziali. Come si evince anche dal nome, questo tipo di ricerca fa parte della famiglia (o MA*). (it)
- Algorytm SMA* – algorytm przeszukiwania grafu prostego, odnajdujący najkrótszą ścieżkę pomiędzy wierzchołkiem początkowym a dowolnym z wierzchołków docelowych. Pierwszym i rozwiązaniem heurystycznym tego problemu był algorytm A*, który opisano w 1968 roku. Wadą tego algorytmu jest niepraktycznie duże zapotrzebowanie na pamięć. Jedną z prób rozwiązania tego problemu jest opisany w 1989 roku, który gwarantuje znalezienie akceptowalnych rozwiązań w określonych granicach pamięci (powyżej wymaganego minimum). SMA*, przedstawiony w 1992. przez Stuarta Russella, jest uproszczoną wersją tego algorytmu, która zarazem sprawniej wykorzystuje dostępną pamięć. Zdaniem autora największą zaletą algorytmu SMA* w porównaniu z MA* jest wykorzystanie zmiennej pathmax, która jest ustalana w ten sposób, że z jednej strony jej wartość jest co najmniej równa wartości dla optymalnego rozwiązania, a z drugiej strony pozwala na efektywną selekcję rozwiązań, których funkcja kosztu jest zbyt duża i kasowanie związanych z nimi rezultatów pośrednich. Ponadto jego zdaniem algorytm SMA* jest łatwiejszy do zrozumienia i implementacji, w algorytmie wprowadzono bardziej efektywne struktury danych do przechowywania rezultatów pośrednich oraz usprawniono obsługę odrzucania rezultatów charakteryzujących się najgorszymi wartościami w przypadku wykorzystania całej pamięci przydzielonej do realizacji zadania. (pl)
- Спро́щений алгори́тм A* з обмеже́нням па́м'яті (англ. «SMA* (Simplified Memory-Bounded A*) algorithm») — це варіант A* пошуку з обмеженою пам'яттю. (uk)
- SMA* или Упрощённый алгоритм с ограничением памяти A* — это алгоритм кратчайшего пути, основанный на алгоритме A*. Основное преимущество SMA* заключается в том, что он использует ограниченную память, в то время как алгоритму A* может потребоваться экспоненциальная память. Все остальные характеристики SMA* унаследованы от A*. (ru)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3408 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- SMA* o o simplificado de memoria acotada A * es un algoritmo del camino más corto basada en el algoritmo A*. La principal ventaja de SMA * es que utiliza una memoria limitada, mientras que el algoritmo A * puede ser que necesite memoria exponencial. Todas las demás características de SMA * son heredados de A *. (es)
- SMA* or Simplified Memory Bounded A* is a shortest path algorithm based on the A* algorithm. The main advantage of SMA* is that it uses a bounded memory, while the A* algorithm might need exponential memory. All other characteristics of SMA* are inherited from A*. (en)
- SMA*, acronimo di Simplified Memory-Bounded A*, è un algoritmo euristico per la ricerca del cammino minimo basato sull'algoritmo A*, proposto dall'informatico anglo-statunitense nel 1992. Il vantaggio principale di SMA* è l'uso limitato della memoria, al contrario di A* che ha bisogno, nel caso peggiore, di uno spazio esponenziale. Tutte le altre caratteristiche di SMA* derivano direttamente da A*, incluse le prestazioni in termini di tempo, che nel caso peggiore rimangono esponenziali. Come si evince anche dal nome, questo tipo di ricerca fa parte della famiglia (o MA*). (it)
- Спро́щений алгори́тм A* з обмеже́нням па́м'яті (англ. «SMA* (Simplified Memory-Bounded A*) algorithm») — це варіант A* пошуку з обмеженою пам'яттю. (uk)
- SMA* или Упрощённый алгоритм с ограничением памяти A* — это алгоритм кратчайшего пути, основанный на алгоритме A*. Основное преимущество SMA* заключается в том, что он использует ограниченную память, в то время как алгоритму A* может потребоваться экспоненциальная память. Все остальные характеристики SMA* унаследованы от A*. (ru)
- Der Simplified Memory-Bounded Algorithm (SMA*) ist ein Algorithmus zur speicheroptimierten Suche in Bäumen. Es ist ein Sonderfall des A*-Algorithmus' zur Berechnung eines kürzesten Pfades. Wenn der zu untersuchende Baum mit einem Greedy-Algorithmus durchsucht wird und nicht genügend Speicher vorhanden ist, um den kompletten Baum im Speicher zu halten, dann werden ungünstige Knoten bzw. Teilbäume zunächst ignoriert. Im Vorgängerknoten werden Informationen über die Kosten des Teilbaums gespeichert. Wenn bei den verbleibenden Teilbäumen kein besseres Ergebnis erzielt wird, kann die Berechnung an den günstigen vergessenen Knoten wieder aufgenommen werden. Der Einspareffekt beim Speicherverbrauch resultiert daraus, dass wenig erfolgversprechende Lösungsvarianten zunächst nicht im Speicher gehal (de)
- Algorytm SMA* – algorytm przeszukiwania grafu prostego, odnajdujący najkrótszą ścieżkę pomiędzy wierzchołkiem początkowym a dowolnym z wierzchołków docelowych. Pierwszym i rozwiązaniem heurystycznym tego problemu był algorytm A*, który opisano w 1968 roku. Wadą tego algorytmu jest niepraktycznie duże zapotrzebowanie na pamięć. Jedną z prób rozwiązania tego problemu jest opisany w 1989 roku, który gwarantuje znalezienie akceptowalnych rozwiązań w określonych granicach pamięci (powyżej wymaganego minimum). SMA*, przedstawiony w 1992. przez Stuarta Russella, jest uproszczoną wersją tego algorytmu, która zarazem sprawniej wykorzystuje dostępną pamięć. Zdaniem autora największą zaletą algorytmu SMA* w porównaniu z MA* jest wykorzystanie zmiennej pathmax, która jest ustalana w ten sposób, że (pl)
|
| rdfs:label
|
- Simplified Memory-Bounded Algorithm (de)
- SMA* (es)
- SMA* (it)
- Algorytm SMA* (pl)
- SMA* (en)
- SMA* (ru)
- Спрощений алгоритм з обмеженням пам'яті (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
