Ocena poprawności działania algorytmu proof-number search na strukturze digrafu acyklicznego - Publikacja - MOST Wiedzy

Wyszukiwarka

Ocena poprawności działania algorytmu proof-number search na strukturze digrafu acyklicznego

Abstrakt

Algorytm proof-number search jest znanym algorytmem służącym do rozwiązywania gier logicznych. Rozwiązanie gry jest jednoznaczne ze znalezieniem optymalnej strategii i pozwala przeprowadzić rozgrywkę w sposób pozwalający na osiągnięcie najlepszego możliwego wyniku. Jedną z największych wad tego algorytmu, naturalnie pracującego na strukturze drzewa, jest wielokrotne rozwijanie identycznych poddrzew gry co prowadzi do nadmiarowego zużycia pamięci. Jednym z możliwych sposobów służących rozwiązaniu tego problemu jest zastosowanie struktury digrafu acyklicznego zamiast drzewa. Może to jednak prowadzić do przeoczenia przez tak zmodyfikowany algorytm pewnych strategii, a to z kolei prowadzi do nieoptymalnej gry. W niniejszym artykule przeprowadzono badania wydajności i poprawności działania tak zmodyfikowanego algorytmu przy wykorzystaniu różnych wariantów gry logicznej "Skoczki".

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
Opublikowano w:
Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne nr T. 1, strony 305 - 310,
ISSN: 1732-1166
Język:
polski
Rok wydania:
2011
Opis bibliograficzny:
Goluch T.: Ocena poprawności działania algorytmu proof-number search na strukturze digrafu acyklicznego// Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne. -Vol. T. 1., nr. nr 9 (2011), s.305-310
Weryfikacja:
Politechnika Gdańska

wyświetlono 14 razy

Publikacje, które mogą cię zainteresować

Meta Tagi