Haggle
(Tento súbor je v Markdown formáte. Pre renderovanie do HTML použite napríklad program marked.)
Haggle je vnorený doménovo špecifický jazyk pre všeobecné problémy prehľadávania stavových priestorov. Jeho cieľom je zjednodušiť kombinovanie rozličných prehľadávacích algoritmov a skúšanie rozličných heuristík pre daný problém.
Kompilácia a spúšťanie
Zdrojový kód jazyka Haggle pozostáva z troch modulov, ktoré tvoria jeho jadro - Haggle, Path a Expandable - a z modulov, ktoré implementujú konkrétne prehľadávacie algoritmy. Podporované prehľadávacie algoritmy sú:
-
prehľadávanie s výberom najlepšieho (s heuristikou)
-
prehľadávanie do šírky (s ľubovoľnou hĺbkou vrátane nekonečnej)
Haggle potrebuje GHC 7. Novšie verzie pravdepodobne nebudú fungovať.
Najjednoduchší spôsob, ako používať Haggle, je stiahnuť si jeho zdrojové súbory a dať adresár so zdrojovými súbormi ako -i parameter prekladaču, keď kompilujete alebo spúšťate Haggle súbory.
Pridávanie nových prehľadávacích algoritmov
Implementujte váš prehľadávací algoritmus v Haskelli ako nový modul. Exportovaná funkcia, ktorá vykonáva samotné prehľadávanie, musí mať návratový typ State (Backlog a) [[a]]
, ak je a inštanciou typovej triedy Expandable.
Potom stačí len importovať modul z Haggle súborov a zavolať prehľadávaciu funkciu.
Testovanie algoritmov na nových problémoch
Navrhnite dátový typ reprezentujúci problém a urobte tento typ inštanciou typovej triedy Expandable.
Táto typová trieda obsahuje nasledovné funkcie:
-- predikát "detekuj úspešný koncový vrchol"
stopSuccess :: a -> Bool
-- predikát "detekuj neúspešný koncový vrchol"
stopFail :: [a] -> Bool
-- vráť ohodnotenie cesty
rank :: (a -> Int) -> [a] -> Int
-- vráť nasledujúce stavy k zadanému stavu
generateNbs :: a -> [a]
-- odstráň zo zoznamu potenciálnych kandidátov tých,
-- ktorých sme už preskúmali
prune :: Result a -> [a] -> Result a
Dátový typ Result je typ pre výsledok expanzie jedného vrcholu a vyzerá nasledovne:
data Result a = Fail | Success a | Sons [a]
Teraz môžete používať podporované prehľadávanie algoritmy a ich kombinácie na hľadanie riešenia tohto problému.
Formát súboru pre Haggle
Súbory pre Haggle sú obyčajné zdrojáky v Haskelli. Môžete v nich používať funkcie tohto jazyka, prípadne si pridať vlastné, kdekoľvek to prekladač dovoľuje.
Súbor pre jazyk Haggle vyzerá nasledovne:
import Haggle
<import used search algorithms>
<import other modules>`
main = < result selector > $ do
<search algorithm 1> <params>
...
<search algorithms n> <params>
Algoritmus pre prehľadávanie s výberom najlepšieho sa zavolá použitím:
befs < heuristická funkcia >
Algoritmus pre prehľadávanie do šírky sa zavolá použitím:
bfs < limit; Inf znamená neobmedzene >
Haggle súbor spustíte (napríklad) pomocou:
runghc -i<path to Haggle> hagglefile.hs
Príklady
V adresári examples je niekoľko príkladov využitia jazyka Haggle pre hľadanie riešení Lloydovej 15 rozličnými technikami.
Skript runExamples.sh skompiluje a spustí všetky príklady.
Testy
V adresári tests sa nachádzajú unit testy. Všetky používajú framework HUnit.
Modul TestBeFS2x2 hľadá riešenia 2x2 verzie Lloyd 15 s použitím prehľadávania s výberom najlepšieho.
Modul TestBeFS4x4 hľadá riešenia 4x4 verzie Lloyd 15 s použitím prehľadávania s výberom najlepšieho.
Modul TestBFS2x2 hľadá riešenia 2x2 verzie Lloyd 15 s použitím prehľadávania do šírky.
Modul TestBFS4x4 hľadá riešenia 4x4 verzie Lloyd 15 s použitím prehľadávania do širky.
Modul TestFixtures obsahuje pomocné funkcie pre heuristiky a testovacie dáta.
Modul TestLloyd15 testuje reprezentáciu Lloyd 15.
Skript runTests.sh skompiluje a spustí všetky testy.