home *** CD-ROM | disk | FTP | other *** search
/ PC World 2002 December / PCWorld_2002-12_cd.bin / Software / Komercni / Baltik / katB.exe / katB / BACKTRAQ / BACKTRAQ.LAT < prev    next >
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. 3. Pokud nové ƒásteƒné ²eτení vyhovuje podmínkám úlohy, jde se znovu na bod 2.
  56. 4. Pokud nové ƒásteƒné ²eτení nevyhovuje podmínkám úlohy, je vyzkouτeno jiné.
  57. 5. 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.