Program Backtraq vyu₧φvß algoritmu zvanΘho "backtracking" (Φesky "zp∞tnΘ sledovßnφ") k °eÜenφ problΘm∙ z ka₧dodennφho ₧ivota i z teorie, jejich₧ °eÜenφ jin²mi prost°edky ne₧ pomocφ poΦφtaΦe by bylo velmi komplikovanΘ a Φasov∞ nßroΦnΘ.
Po spuÜt∞nφ programu je zobrazeno hlavnφ menu. Pro start programu stiskn∞te p°i zobrazenΘm hlavnφm menu klßvesu F2. Tak p°ejdete na v²b∞r modulu. Ka₧d² modul p°edstavuje °eÜenφ urΦitΘ ·lohy (problΘmu). Modul vybφrßte stisknutφm kurzorov²ch Üipek nahoru a dol∙, pop°. lze pou₧φt rychlΘ volby stisknutφm klßvesy s po°adov²m Φφslem modulu (modul, kter² je zobrazen² po vstupu do v²b∞ru modulu mß Φφslo 1, dßle Φφsla rostou sm∞rem dol∙). V²b∞r modulu potvrdφte klßvesou Enter. PotΘ je na obrazovce zobrazen bli₧Üφ popis Φinnosti modulu. Nynφ jeÜt∞ m∙₧ete svou volbu zruÜit a vrßtit se do hlavnφho menu prost°ednictvφm klßvesy Escape. Stisknutφm klßvesy T spustφte modul v textovΘm re₧imu, stisknutφm libovolnΘ jinΘ klßvesy v re₧imu grafickΘm. Po spuÜt∞nφ modulu se dßle °i∩te pokyny, kterΘ se zobrazujφ u hornφho okraje obrazovky (grafick² re₧im) resp. v °ad∞ pod sebou na obrazovce (textov² re₧im). Pro prvnφ seznßmenφ se s programem doporuΦujeme pou₧φvat grafick² re₧im, pro uskuteΦ≥ovßnφ slo₧it∞jÜφch v²poΦt∙ pak textov² re₧im, kter² je oproti grafickΘmu rychlejÜφ.
S programem jsou standardn∞ dodßvßny Φty°i moduly, tzn. program umo₧≥uje °eÜit Φty°i r∙znΘ ·lohy (problΘmy): ProblΘm osmi dam, Vyt∞₧ovacφ stanice, ProblΘm obchodnφho cestujφcφho, Hledßnφ nejlepÜφ cesty. Bli₧Üφ popis t∞chto modul∙ naleznete na obrazovce s informacemi po jejich v²b∞ru v menu pro v²b∞r modulu. Program je otev°en² dalÜφm v²vojß°∙m, kte°φ mohou naprogramovat novΘ moduly a ty pak do programu snadn²m zp∙sobem zaΦlenit, proto₧e zdrojovΘ k≤dy programu jsou voln∞ Üi°itelnΘ. Ka₧d² modul je tvo°en dv∞ma soubory (modul.inc a modul.b00), kterΘ jsou umφst∞ny v podadresß°i backtraq.mod. Vlo₧enφm takov²chto soubor∙ do tohoto podadresß°e a jejich p°idßnφm do seznamu modul∙ v souboru moduly.inc v tΘm₧e podadresß°i staΦφ k p°idßnφ nov∞ vytvo°enΘho modulu do programu. Nov² modul p°itom m∙₧e vyu₧φvat veÜkerΘ v²hody, kterΘ mu program Backtraq p°inßÜφ, co₧ je mj. ji₧ vy°eÜenß zßkladnφ kostra backtrackingu, na kterou staΦφ pouze navßzat jednotlivΘ funkce, dßle pak p°edp°ipravenΘ funkce pro grafickΘ i textovΘ u₧ivatelskΘ rozhranφ a uklßdßnφ informacφ o °eÜenΘm problΘmu do textovΘho souboru.
VÜechny ·lohy (problΘmy) °eÜenΘ programem jsou zalo₧enΘ na spoleΦnΘm algoritmu, kter² se naz²vß backtracking (Φesky "zp∞tnΘ sledovßnφ"). Ka₧dß ·loha tento algoritmus po svΘm konkretizuje, zßklad vÜak z∙stßvß spoleΦn² pro vÜechny. Zßkladnφ princip backtrackingu spoΦφvß v systematickΘm zkoumßnφ vÜech potencißlnφch °eÜenφ, a to takto:
DalÜφ nerozÜi°ovßnφ ΦßsteΦnΘho °eÜenφ z d∙vodu, ₧e z n∞j nelze dosp∞t ke kompletnφmu °eÜenφ, se naz²vß pruning (Φesky "o°ezßvßnφ", "omezovßnφ"). A prßv∞ vyu₧itφ pruningu Φinφ backtracking rychlejÜφm a v²hodn∞jÜφm ne₧ pou₧itφ prostΘho vyzkouÜenφ vÜech mo₧nostφ. Oproti jin²m jeÜt∞ vφce zjednoduÜen²m p°φstup∙m k °eÜenφ ·loh mß pak backtracking tu v²hodu, ₧e zaruΦuje p°esnost v²sledku, proto₧e zkoumß vÜechny mo₧nΘ situace, kterΘ mohou p°i °eÜenφ ·lohy nastat.
Backtraq - Copyright © 2001-2002 Marek BlahuÜ
Program je freeware a open-source. Lze jej voln∞ Üφ°it i se zdrojov²m k≤dem.
Autor programu uvφtß, pokud se s nφm pod∞lφte o svΘ zkuÜenosti s programem.
Marek BlahuÜ
E-mail: blahus@seznam.cz
Adresa: Marek BlahuÜ, Rudy KubφΦka 1002, 686 05 UherskΘ HradiÜt∞ 5
Telefon: (+420) 777252487
Datum a Φas poslednφ zm∞ny: pßtek 20.9.2002 23:28