home *** CD-ROM | disk | FTP | other *** search
/ PC World 2002 December / PCWorld_2002-12_cd.bin / Software / Komercni / Baltik / katB.exe / katB / BACKTRAQ / BACKTRAQ.TXT < prev   
Text File  |  2002-09-25  |  5KB  |  83 lines
  1. Nßpov∞da k programu Backtraq
  2. ----------------------------
  3. Program Backtraq vyu₧φvß algoritmu zvanΘho "backtracking" (Φesky "zp∞tnΘ
  4. sledovßnφ") k °eÜenφ problΘm∙ z ka₧dodennφho ₧ivota i z teorie, jejich₧ °eÜenφ
  5. jin²mi prost°edky ne₧ pomocφ poΦφtaΦe by bylo velmi komplikovanΘ a Φasov∞
  6. nßroΦnΘ.
  7.  
  8. Jak program ovlßdat
  9. -------------------
  10. Po spuÜt∞nφ programu je zobrazeno hlavnφ menu. Pro start programu stiskn∞te p°i
  11. zobrazenΘm hlavnφm menu klßvesu F2. Tak p°ejdete na v²b∞r modulu. Ka₧d² modul
  12. p°edstavuje °eÜenφ urΦitΘ ·lohy (problΘmu). Modul vybφrßte stisknutφm
  13. kurzorov²ch Üipek nahoru a dol∙, pop°. lze pou₧φt rychlΘ volby stisknutφm
  14. klßvesy s po°adov²m Φφslem modulu (modul, kter² je zobrazen² po vstupu do
  15. v²b∞ru modulu mß Φφslo 1, dßle Φφsla rostou sm∞rem dol∙). V²b∞r modulu
  16. potvrdφte klßvesou Enter. PotΘ je na obrazovce zobrazen bli₧Üφ popis Φinnosti
  17. modulu. Nynφ jeÜt∞ m∙₧ete svou volbu zruÜit a vrßtit se do hlavnφho menu
  18. prost°ednictvφm klßvesy Escape. Stisknutφm klßvesy T spustφte modul v textovΘm
  19. re₧imu, stisknutφm libovolnΘ jinΘ klßvesy v re₧imu grafickΘm. Po spuÜt∞nφ
  20. modulu se dßle °i∩te pokyny, kterΘ se zobrazujφ u hornφho okraje obrazovky
  21. (grafick² re₧im) resp. v °ad∞ pod sebou na obrazovce (textov² re₧im). Pro prvnφ
  22. seznßmenφ se s programem doporuΦujeme pou₧φvat grafick² re₧im, pro
  23. uskuteΦ≥ovßnφ slo₧it∞jÜφch v²poΦt∙ pak textov² re₧im, kter² je oproti
  24. grafickΘmu rychlejÜφ.
  25.  
  26. ╪eÜenΘ problΘmy aneb O modulech
  27. -------------------------------
  28. S programem jsou standardn∞ dodßvßny Φty°i moduly, tzn. program umo₧≥uje °eÜit
  29. Φty°i r∙znΘ ·lohy (problΘmy): ProblΘm osmi dam, Vyt∞₧ovacφ stanice, ProblΘm
  30. obchodnφho cestujφcφho, Hledßnφ nejlepÜφ cesty. Bli₧Üφ popis t∞chto modul∙
  31. naleznete na obrazovce s informacemi po jejich v²b∞ru v menu pro v²b∞r modulu.
  32. Program je otev°en² dalÜφm v²vojß°∙m, kte°φ mohou naprogramovat novΘ moduly a
  33. ty pak do programu snadn²m zp∙sobem zaΦlenit, proto₧e zdrojovΘ k≤dy programu
  34. jsou voln∞ Üi°itelnΘ. Ka₧d² modul je tvo°en dv∞ma soubory (modul.inc a
  35. modul.b00), kterΘ jsou umφst∞ny v podadresß°i backtraq.mod. Vlo₧enφm takov²chto
  36. soubor∙ do tohoto podadresß°e a jejich p°idßnφm do seznamu modul∙ v souboru
  37. moduly.inc v tΘm₧e podadresß°i staΦφ k p°idßnφ nov∞ vytvo°enΘho modulu do
  38. programu. Nov² modul p°itom m∙₧e vyu₧φvat veÜkerΘ v²hody, kterΘ mu program
  39. Backtraq p°inßÜφ, co₧ je mj. ji₧ vy°eÜenß zßkladnφ kostra backtrackingu, na
  40. kterou staΦφ pouze navßzat jednotlivΘ funkce, dßle pak p°edp°ipravenΘ funkce
  41. pro grafickΘ i textovΘ u₧ivatelskΘ rozhranφ a uklßdßnφ informacφ o °eÜenΘm
  42. problΘmu do textovΘho souboru.
  43.  
  44. Podrobn∞ji o backtrackingu a jeho aplikaci v programu
  45. -----------------------------------------------------
  46. VÜechny ·lohy (problΘmy) °eÜenΘ programem jsou zalo₧enΘ na spoleΦnΘm algoritmu,
  47. kter² se naz²vß backtracking (Φesky "zp∞tnΘ sledovßnφ"). Ka₧dß ·loha tento
  48. algoritmus po svΘm konkretizuje, zßklad vÜak z∙stßvß spoleΦn² pro vÜechny.
  49. Zßkladnφ princip backtrackingu spoΦφvß v systematickΘm zkoumßnφ vÜech
  50. potencißlnφch °eÜenφ, a to takto:
  51.  
  52. 1. Na zaΦßtku je ΦßsteΦnΘ °eÜenφ prßzdnΘ.
  53. 2. Dosavadnφ ΦßsteΦnΘ °eÜenφ je rozÜφ°eno.
  54. 3. Pokud je novΘ ΦßsteΦnΘ °eÜenφ kompletnφm °eÜenφm ·lohy, skonΦφ se.
  55. 4. Pokud novΘ ΦßsteΦnΘ °eÜenφ vyhovuje podmφnkßm ·lohy, jde se znovu na bod 2.
  56. 5. Pokud novΘ ΦßsteΦnΘ °eÜenφ nevyhovuje podmφnkßm ·lohy, je vyzkouÜeno jinΘ.
  57. 6. Pokud ₧ßdnΘ ΦßsteΦnΘ °eÜenφ nevyhovuje podmφnkßm ·lohy, vrßtφme se o ·rove≥
  58.    v²Ü (na poslednφ vyhovujφcφ ΦßsteΦnΘ °eÜenφ) a pokraΦujeme v prozkoumßvßnφ
  59.    jeho dalÜφch potencißlnφ rozÜφ°enφ (bod 2.).
  60.  
  61. DalÜφ nerozÜi°ovßnφ ΦßsteΦnΘho °eÜenφ z d∙vodu, ₧e z n∞j nelze dosp∞t ke
  62. kompletnφmu °eÜenφ, se naz²vß pruning (Φesky "o°ezßvßnφ", "omezovßnφ"). A prßv∞
  63. vyu₧itφ pruningu Φinφ backtracking rychlejÜφm a v²hodn∞jÜφm ne₧ pou₧itφ
  64. prostΘho vyzkouÜenφ vÜech mo₧nostφ. Oproti jin²m jeÜt∞ vφce zjednoduÜen²m
  65. p°φstup∙m k °eÜenφ ·loh mß pak backtracking tu v²hodu, ₧e zaruΦuje p°esnost
  66. v²sledku, proto₧e zkoumß vÜechny mo₧nΘ situace, kterΘ mohou p°i °eÜenφ ·lohy
  67. nastat.
  68.  
  69. O programu Backtraq
  70. -------------------
  71. Backtraq - Copyright (C) 2001-2002 Marek BlahuÜ
  72. Program je freeware a open-source. Lze jej voln∞ Üφ°it i se zdrojov²m k≤dem.
  73. Autor programu uvφtß, pokud se s nφm pod∞lφte o svΘ zkuÜenosti s programem.
  74.  
  75. Kontakt na autora
  76. -----------------
  77. Marek BlahuÜ
  78. E-mail: blahus@seznam.cz
  79. Adresa: Marek BlahuÜ, Rudy KubφΦka 1002, 686 05 UherskΘ HradiÜt∞ 5
  80. Telefon: (+420) 777252487
  81.  
  82. Datum a Φas poslednφ zm∞ny: pßtek 20.9.2002 23:28
  83.