home *** CD-ROM | disk | FTP | other *** search
/ PC World 2002 December / PCWorld_2002-12_cd.bin / Software / Komercni / Baltik / katB.exe / katB / BACKTRAQ / BACKTRAQ.MOD / TSP.INC < prev   
Text File  |  2002-09-25  |  28KB  |  525 lines
  1. // soukromé konstanty
  2.  
  3. // konstanty pro hodnoty prom╪nné modTSP_ZpàsobZadáváníMíst
  4. # define modTSP_ZAD╡V╡N╓M╓ST_¼╓SELN╖ 1
  5. # define modTSP_ZAD╡V╡N╓M╓ST_GRAFICKY 2
  6.  
  7. // soukromé prom╪nné
  8.  
  9. int modTSP_PoƒetMíst; // poƒet míst, která je t²eba navτtívit
  10. int *modTSP_Sou²adniceMíst; // sou²adnice míst, která je t²eba navτtívit (kaºd∞ sud∞ [0,2,4..] prvek je X a kaºd∞ lich∞ [1,3,5..] prvek je Y)
  11. int modTSP_ZpàsobZadáváníMíst; // ƒíseln╪ nebo graficky (viz konstanty)
  12.  
  13. int *modTSP_Cesta; // pole práv╪ testované cesty - jednotlivé prvky jsou po²adová ƒísla míst, která cestu tvo²í
  14. int modTSP_DélkaCesty; // délka práv╪ testované cesty v pixelech
  15. int modTSP_Θroveσ; // úroveσ zano²ení v backtrackingu (kolik míst je v práv╪ testované cest╪ p²ítomno)
  16. int *modTSP_Nejlepτíⁿeτení_Cesta; // kopie pole Cesta, které je dosud nejlepτí nalezen∞m ²eτením
  17. int modTSP_Nejlepτíⁿeτení_DélkaCesty; // kopie prom╪nné DélkaCesty, která je dosud nejlepτím nalezen∞m ²eτením
  18. int modTSP_Nejlepτíⁿeτení_Θroveσ; // kopie prom╪nné Θroveσ, která byla aktuální v dob╪ nalezení nejlepτího nalezeného ²eτení
  19.  
  20. // soukromé funkce
  21.  
  22. void modTSP_VykresliMapu(int *modTSP_VykreslovanéPole, int modTSP_VykreslovanáΘroveσ) {
  23.   int modTSP_Vykreslovan∞Prvek, modTSP_VykreslovanéMísto;
  24.   int modTSP_VykreslovanéPísmenoX, modTSP_VykreslovanéPísmenoY;
  25.   // uschování pàvodn╪ nastaven∞ch barev
  26.   int modTSP_PàvodníBarvy = GrBarvy();
  27.   // smazání obrazovky
  28.   GrNastavBarvuPozadí(PalBéºová);
  29.   GrSmaºOkno();
  30.   // vykreslení jednotliv∞ch míst, která je nutno navτtívit
  31.   GrNastavText(GrTextSPozadím);
  32.   GrNastavBarvy(PalTmav╪Modrá<<4|Palªlutá);
  33.   ¼ekejNaVR();
  34.   for(modTSP_VykreslovanéMísto=0; modTSP_VykreslovanéMísto<((!modTSP_VykreslovanéPole && modTSP_VykreslovanáΘroveσ+1)?modTSP_VykreslovanáΘroveσ:modTSP_PoƒetMíst); modTSP_VykreslovanéMísto++) {
  35.     // vykreslení písmenného oznaƒení vykreslovaného místa
  36.     GrNastavPozici(modTSP_Sou²adniceMíst[modTSP_VykreslovanéMísto*2], modTSP_Sou²adniceMíst[modTSP_VykreslovanéMísto*2+1]);
  37.     GrNastavPozici((GrPoziceX()<4)?0:(GrPoziceX()>631?627:GrPoziceX()-4), (GrPoziceY()<5)?0:(GrPoziceY()>437?432:GrPoziceY()-5));
  38.     GrPiτZnak('A'+modTSP_VykreslovanéMísto);
  39.     }
  40.   GrNastavText(GrTextBezPozadí);
  41.   // pokud se má vykreslovat i cesta
  42.   if(modTSP_VykreslovanéPole) {
  43.     GrNastavBarvuPop²edí(PalBílá);
  44.     // vykreslení spojnic mezi místy tvo²ícími vykreslovanou cestu
  45.     for(modTSP_Vykreslovan∞Prvek=0; modTSP_Vykreslovan∞Prvek<=modTSP_VykreslovanáΘroveσ; modTSP_Vykreslovan∞Prvek++) {
  46.       ¼ekejNaVR();
  47.       // kreslí se první místo => urƒení místa, do kterého se má p²emístit kurzor
  48.       // kreslí se dalτí místa => urƒení místa, do kterého má vést vykreslovaná ƒára
  49.       modTSP_VykreslovanéMísto = modTSP_VykreslovanéPole[modTSP_Vykreslovan∞Prvek];
  50.       // kreslí se první místo => nastavení kurzoru na pozici práv╪ vykreslovaného místa
  51.       if(modTSP_Vykreslovan∞Prvek == 0) {
  52.         GrNastavPozici(modTSP_Sou²adniceMíst[modTSP_VykreslovanéMísto*2], modTSP_Sou²adniceMíst[modTSP_VykreslovanéMísto*2+1]);
  53.         }
  54.       // kreslí se dalτí místa => nakreslení ƒáry spojující p²edchozí místo s práv╪ vykreslovan∞m
  55.       else {
  56.         // kreslí se poslední místo a nekreslí se nejlepτí ²eτení => nastavení odliτné barvy ƒáry k n╪mu vedoucí
  57.         if(modTSP_VykreslovanéPole != modTSP_Nejlepτíⁿeτení_Cesta && modTSP_Vykreslovan∞Prvek == modTSP_VykreslovanáΘroveσ) GrNastavBarvuPop²edí(Palªlutá);
  58.         // nakreslení samotné ƒáry
  59.         GrKresliLinkuDo(modTSP_Sou²adniceMíst[modTSP_VykreslovanéMísto*2], modTSP_Sou²adniceMíst[modTSP_VykreslovanéMísto*2+1]);
  60.         }
  61.       }
  62.     }
  63.   // navrácení pàvodn╪ nastaven∞ch barev
  64.   GrNastavBarvy(modTSP_PàvodníBarvy);
  65.   }
  66.  
  67. int modTSP_ZjistiVzdálenostMíst(int modTSP_Místo1, int modTSP_Místo2) {
  68.   // zjiτt╪ní vzdálenosti mezi dv╪ma místy pomocí Pythagorovy v╪ty
  69.   return sqrt(sqr(abs(modTSP_Sou²adniceMíst[modTSP_Místo1*2]-modTSP_Sou²adniceMíst[modTSP_Místo2*2])) + sqr(abs(modTSP_Sou²adniceMíst[modTSP_Místo1*2+1]-modTSP_Sou²adniceMíst[modTSP_Místo2*2+1])));
  70.   }
  71.  
  72. string modTSP_PoleCestyNaⁿet╪zec(int *modTSP_P²evád╪néPole, int *modTSP_P²evád╪náΘroveσ, int *modTSP_P²evád╪náDélkaCesty) {
  73.   string modTSP_Vrátit = "";
  74.   int modTSP_P²evád╪n∞Prvek;
  75.   for(modTSP_P²evád╪n∞Prvek=0; modTSP_P²evád╪n∞Prvek<=*modTSP_P²evád╪náΘroveσ; modTSP_P²evád╪n∞Prvek++) {
  76.     modTSP_Vrátit += (string)(char)('A'+modTSP_P²evád╪néPole[modTSP_P²evád╪n∞Prvek]);
  77.     }
  78.   modTSP_Vrátit += " (délka "+StrL¼íslo(*modTSP_P²evád╪náDélkaCesty,-1)+" pixelà)";
  79.   return modTSP_Vrátit;
  80.   }
  81.  
  82. // ve²ejné funkce
  83.  
  84. void modTSP_Start(void) {
  85.   // v p²ípad╪ grafického reºimu:
  86.   if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) {
  87.     // smazání obrazovky
  88.     GrSmaºOkno();
  89.     // vykreslení mapy (pouze místa)
  90.     modTSP_VykresliMapu(0, -1);
  91.     }
  92.  
  93.   mod_VypiτHláτku("Po stisknutí klávesy nebo tlaƒítka myτi se rozb╪hne v∞poƒet...", mod_VYPIµHL╡µKU_NE¼EKEJ);
  94.   VyprázdniFrontuKláves(); MyτZapni();
  95.   ¼ekej(NaKlávesu|NaMyτ);
  96.   VyprázdniFrontuKláves(); MyτVypni();
  97.  
  98.   // smazání obrazovky v p²ípad╪ textového reºimu
  99.   if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) {
  100.     TxtSmaºObrazovku();
  101.     }
  102.  
  103.   mod_VypiτHláτku("Probíhá v∞poƒet...", mod_VYPIµHL╡µKU_NE¼EKEJ);
  104.  
  105.   // zaznamenání ƒasu startu v∞poƒtu
  106.   Systémov∞¼as(mod_¼asStart);
  107.  
  108.   // inicializace prom╪nn∞ch pouºívan∞ch v∞poƒtem
  109.   mod_HledatDál = 1;
  110.   modTSP_DélkaCesty = 0;
  111.   modTSP_Θroveσ = 0;
  112.   modTSP_Nejlepτíⁿeτení_DélkaCesty = 32767; // maximální délka cesty - v reále nemoºná, bude nahrazena menτí uº p²i nalezení první vyhovující cesty
  113.   modTSP_Nejlepτíⁿeτení_Θroveσ = 0;
  114.  
  115.   // zapsání parametrà v∞poƒtu do souboru, pokud si to uºivatel p²ál
  116.   if(mod_ZapisovatProtokol) {
  117.     mod_ProtokolZapiτStart1();
  118.     SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Reºim obrazovky: "+(mod_ReºimObrazovky==mod_TEXTOVφ_REªIM?"textov∞":"grafick∞")+"\n");
  119.     SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Poƒet míst na map╪: "+StrL¼íslo(modTSP_PoƒetMíst,-1)+"\n");
  120.     SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Zpàsob zadávání míst: "+(modTSP_ZpàsobZadáváníMíst==modTSP_ZAD╡V╡N╓M╓ST_¼╓SELN╖?"ƒíseln╪":"graficky")+"\n");
  121.     SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Sou²adnice jednotliv∞ch míst [X, Y]: ");
  122.     int modTSP_ProcházenéMísto;
  123.     for(modTSP_ProcházenéMísto=0; modTSP_ProcházenéMísto<modTSP_PoƒetMíst; modTSP_ProcházenéMísto++) SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, StrL¼íslo(modTSP_Sou²adniceMíst[modTSP_ProcházenéMísto*2],-1)+","+StrL¼íslo(modTSP_Sou²adniceMíst[modTSP_ProcházenéMísto*2+1],-1)+" ");
  124.     SouborPiτNov∞ⁿádek(mod_ZapisovatProtokol_Soubor);
  125.     SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Zobrazované pozice: "+(mod_ZobrazovanéPozice==mod_POUZE_ⁿEµEN╓?"jen nalezená ²eτení":"i pràb╪h hledání")+"\n");
  126.     SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Vyƒkat po nalezení nového nejlepτího ²eτení na stisk klávesy: "+(mod_¼ekatNaKlávesu?"ano":"ne")+"\n");
  127.     SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Zapisovat protokol o v∞poƒtu: "+(mod_ZapisovatProtokol?"ano":"ne")+"\n");
  128.     SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Soubor protokolu: "+mod_ZapisovatProtokol_Název+"\n");
  129.     mod_ProtokolZapiτStart2();
  130.     }
  131.   }
  132.  
  133. void modTSP_Hotovo(void) {
  134.   // uloºení ƒasu dokonƒení v∞poƒtu
  135.   Systémov∞¼as(mod_¼asHotovo);
  136.   // p²ekreslení mapy - vykreslení prázdné mapy
  137.   if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) {
  138.     modTSP_VykresliMapu(0, -1);
  139.     }
  140.   // v p²ípad╪ grafického reºimu pípnutí - oznámení dokonƒení v∞poƒtu
  141.   if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { Tón(1000); ¼ekej(1500); VypniTón(); }
  142.   // pokud bylo vàbec nalezeno n╪jaké nejlepτí ²eτení
  143.   if(modTSP_Nejlepτíⁿeτení_DélkaCesty < 32767) {
  144.     // p²ekreslení mapy - vykreslení nejlepτího nalezeného ²eτení
  145.     if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) {
  146.       modTSP_VykresliMapu(modTSP_Nejlepτíⁿeτení_Cesta, modTSP_Nejlepτíⁿeτení_Θroveσ);
  147.       }
  148.     }
  149.   // v∞poƒet doby trvání v∞poƒtu
  150.   mod_V∞poƒetDobyTrváníV∞poƒtu();
  151.   // zobrazení doby trvání v∞poƒtu
  152.   mod_VypiτHláτku("Hotovo. Délka: "+StrL¼ísloZeroPad(mod_¼asRozdíl.Hodiny,2)+":"+StrL¼ísloZeroPad(mod_¼asRozdíl.Minuty,2)+":"+StrL¼ísloZeroPad(mod_¼asRozdíl.Sekundy,2)+"."+StrL¼ísloZeroPad(mod_¼asRozdíl.Setiny,2)+"...", mod_VYPIµHL╡µKU_¼EKEJNAKL╡VESUGRAFIKA);
  153.   // zapsání informací t∞kajících se dokonƒení v∞poƒtu do souboru, pokud si to uºivatel p²ál
  154.   if(mod_ZapisovatProtokol) {
  155.     // pokud bylo vàbec nalezeno n╪jaké nejlepτí ²eτení
  156.     if(modTSP_Nejlepτíⁿeτení_DélkaCesty < 32767) {
  157.       SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "NEJLEPµ╓ ⁿEµEN╓: ");
  158.       SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, modTSP_PoleCestyNaⁿet╪zec(modTSP_Nejlepτíⁿeτení_Cesta, &modTSP_Nejlepτíⁿeτení_Θroveσ, &modTSP_Nejlepτíⁿeτení_DélkaCesty));
  159.       SouborPiτNov∞ⁿádek(mod_ZapisovatProtokol_Soubor);
  160.       }
  161.     // jinak pokud nebylo nalezeno ºádné nejlepτí ²eτení
  162.     else {
  163.       SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Nebylo nalezeno ºádné ²eτení.\n");
  164.       }
  165.     SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Hotovo: "+StrL¼ísloZeroPad(mod_¼asHotovo.Hodiny,2)+":"+StrL¼ísloZeroPad(mod_¼asHotovo.Minuty,2)+":"+StrL¼ísloZeroPad(mod_¼asHotovo.Sekundy,2)+"."+StrL¼ísloZeroPad(mod_¼asHotovo.Setiny,2)+"\n");
  166.     SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Délka v∞poƒtu: "+StrL¼ísloZeroPad(mod_¼asRozdíl.Hodiny,2)+":"+StrL¼ísloZeroPad(mod_¼asRozdíl.Minuty,2)+":"+StrL¼ísloZeroPad(mod_¼asRozdíl.Sekundy,2)+"."+StrL¼ísloZeroPad(mod_¼asRozdíl.Setiny,2)+"\n");
  167.     mod_ProtokolZapiτHotovo();
  168.     }
  169.   // pokud bylo vàbec nalezeno n╪jaké nejlepτí ²eτení
  170.   if(modTSP_Nejlepτíⁿeτení_DélkaCesty < 32767) {
  171.     mod_VypiτHláτku("NEJLEPµ╓ ⁿEµEN╓: " + modTSP_PoleCestyNaⁿet╪zec(modTSP_Nejlepτíⁿeτení_Cesta, &modTSP_Nejlepτíⁿeτení_Θroveσ, &modTSP_Nejlepτíⁿeτení_DélkaCesty), mod_VYPIµHL╡µKU_¼EKEJNAKL╡VESU);
  172.     }
  173.   // jinak pokud nebylo nalezeno ºádné nejlepτí ²eτení
  174.   else {
  175.     mod_VypiτHláτku("Nebylo nalezeno ºádné ²eτení.", mod_VYPIµHL╡µKU_¼EKEJNAKL╡VESU);
  176.     }
  177.   }
  178.  
  179. void modTSP_Θklid(void) {
  180.   // uvoln╪ní pam╪ti pouºité pro pole sou²adnic míst
  181.   HromadaUvolniPam╪£(modTSP_Sou²adniceMíst);
  182.   modTSP_Sou²adniceMíst = 0;
  183.   // uvoln╪ní pam╪ti pouºité pro pole cesty
  184.   HromadaUvolniPam╪£(modTSP_Cesta);
  185.   modTSP_Cesta = 0;
  186.   // uvoln╪ní pam╪ti pouºité pro pole nejlepτího ²eτení
  187.   HromadaUvolniPam╪£(modTSP_Nejlepτíⁿeτení_Cesta);
  188.   modTSP_Nejlepτíⁿeτení_Cesta = 0;
  189.   }
  190.  
  191. void modTSP_ZadáníVstupu(void) {
  192.   // INICIALIZACE REªIMU OBRAZOVKY
  193.   if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) {
  194.     // p²epnutí do textového reºimu
  195.     P²epniNaText();
  196.     }
  197.   else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) {
  198.     GrSmaºOkno();
  199.     }
  200.  
  201.   // INFORMACE O REªIMU OBRAZOVKY
  202.   if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) {
  203.     mod_VypiτHláτku("Pouºívám textov∞ reºim...", mod_VYPIµHL╡µKU_VY¼KEJ);
  204.     }
  205.   else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) {
  206.     mod_VypiτHláτku("Pouºívám grafick∞ reºim...", mod_VYPIµHL╡µKU_VY¼KEJ);
  207.     }
  208.  
  209.   // ZJIµT╖N╓ PO¼TU M╓ST NA MAP╖, KTER╡ M╡ OBCHODN╓ CESTUJ╓C╓ PROJ╓T
  210.   mod_VypiτHláτku("Zadejte, kolik míst má obchodní cestující projít [2-26]: ", mod_VYPIµHL╡µKU_NE¼EKEJ);
  211.   if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) {
  212.     while((VyprázdniFrontuKláves(),Txt¼tiI¼íslo(modTSP_PoƒetMíst)) || modTSP_PoƒetMíst < 2 || modTSP_PoƒetMíst > 26);
  213.     }
  214.   else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) {
  215.     GrNastavV∞stup(mod_GRAFIKA_VφSTUP_POKYN);
  216.     while((VyprázdniFrontuKláves(),Gr¼tiI¼íslo("",modTSP_PoƒetMíst,2,0,PalTmav╪Modrá<<4|Palªlutá)) || modTSP_PoƒetMíst < 2 || modTSP_PoƒetMíst > 26);
  217.     GrNastavV∞stup(mod_GRAFIKA_VφSTUP_MOJEPLOCHA);
  218.     }
  219.  
  220.   // INFORMACE O PO¼TU M╓ST NA MAP╖, KTER╡ M╡ OBCHODN╓ CESTUJ╓C╓ PROJ╓T
  221.   if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) {
  222.     mod_VypiτHláτku("Obchodní cestující má projít "+StrL¼íslo(modTSP_PoƒetMíst,-1)+" místy...", mod_VYPIµHL╡µKU_VY¼KEJ);
  223.     }
  224.  
  225.   // Pⁿ╓PRAVA POLE SOUⁿADNIC M╓ST
  226.   // alokace pam╪ti pro pole
  227.   modTSP_Sou²adniceMíst = (int*)HromadaAlokujPam╪£(modTSP_PoƒetMíst*2*sizeof(modTSP_Sou²adniceMíst[0]));
  228.   // vynulování vτech prvkà pole
  229.   memset(modTSP_Sou²adniceMíst, 0, modTSP_PoƒetMíst*2*sizeof(modTSP_Sou²adniceMíst[0]));
  230.  
  231.   // Pⁿ╓PRAVA POLE CESTY
  232.   // alokace pam╪ti pro pole
  233.   modTSP_Cesta = (int*)HromadaAlokujPam╪£(modTSP_PoƒetMíst*sizeof(modTSP_Cesta[0]));
  234.   // vynulování vτech prvkà pole
  235.   memset(modTSP_Cesta, 0, modTSP_PoƒetMíst*sizeof(modTSP_Cesta[0]));
  236.  
  237.   // Pⁿ╓PRAVA POLE NEJLEPµ╓HO ⁿEµEN╓
  238.   // alokace pam╪ti pro pole
  239.   modTSP_Nejlepτíⁿeτení_Cesta = (int*)HromadaAlokujPam╪£(modTSP_PoƒetMíst*sizeof(modTSP_Nejlepτíⁿeτení_Cesta[0]));
  240.   // vynulování vτech prvkà pole
  241.   memset(modTSP_Nejlepτíⁿeτení_Cesta, 0, modTSP_PoƒetMíst*sizeof(modTSP_Nejlepτíⁿeτení_Cesta[0]));
  242.  
  243.   // ZJIµT╖N╓ ZP▐SOBU ZAD╡V╡N╓ SOUⁿADNIC JEDNOTLIVφCH M╓ST NA MAP╖, KTER╡ M╡ OBCHODN╓ CESTUJ╓C╓ PROJ╓T
  244.   if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) {
  245.     // pokud je vybrán grafick∞ reºim, umoºníme zpàsob zadávání vybrat
  246.     mod_NechZvolit_Volby[0] = "ƒíseln╪"; mod_NechZvolit_AccessKeys[0] = 'ƒ';
  247.     mod_NechZvolit_Volby[1] = "graficky"; mod_NechZvolit_AccessKeys[1] = 'g';
  248.     switch(mod_NechZvolit("Zvolte zpàsob zadávání sou²adnic míst, která má obchodní cestující projít:")) {
  249.       case 0: modTSP_ZpàsobZadáváníMíst = modTSP_ZAD╡V╡N╓M╓ST_¼╓SELN╖; break;
  250.       case 1: modTSP_ZpàsobZadáváníMíst = modTSP_ZAD╡V╡N╓M╓ST_GRAFICKY; break;
  251.       }
  252.     }
  253.   else if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) {
  254.     // jinak pokud je vybrán textov∞ reºim, lze zadávat pouze ƒíseln╪
  255.     modTSP_ZpàsobZadáváníMíst = modTSP_ZAD╡V╡N╓M╓ST_¼╓SELN╖;
  256.     }
  257.  
  258.   // ZJIµT╖N╓ SOUⁿADNIC JEDNOTLIVφCH M╓ST NA MAP╖, KTER╡ M╡ OBCHODN╓ CESTUJ╓C╓ PROJ╓T
  259.   int modTSP_ZadávanéMísto;
  260.   if(modTSP_ZpàsobZadáváníMíst == modTSP_ZAD╡V╡N╓M╓ST_¼╓SELN╖) {
  261.     for(modTSP_ZadávanéMísto=0; modTSP_ZadávanéMísto<modTSP_PoƒetMíst; modTSP_ZadávanéMísto++) {
  262.       // ZJIµT╖N╓ X SOUⁿADNICE PR╡V╖ ZAD╡VANÉHO M╓STA
  263.       mod_VypiτHláτku("Zadejte X sou²adnici místa "+(string)(char)('A'+modTSP_ZadávanéMísto)+" v pixelech [0-635]: ", mod_VYPIµHL╡µKU_NE¼EKEJ);
  264.       if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) {
  265.         while((VyprázdniFrontuKláves(),Txt¼tiI¼íslo(modTSP_Sou²adniceMíst[modTSP_ZadávanéMísto*2])) || modTSP_Sou²adniceMíst[modTSP_ZadávanéMísto*2] < 0 || modTSP_Sou²adniceMíst[modTSP_ZadávanéMísto*2] > 635);
  266.         }
  267.       else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) {
  268.         GrNastavV∞stup(mod_GRAFIKA_VφSTUP_POKYN);
  269.         while((VyprázdniFrontuKláves(),Gr¼tiI¼íslo("",modTSP_Sou²adniceMíst[modTSP_ZadávanéMísto*2],3,0,PalTmav╪Modrá<<4|Palªlutá)) || modTSP_Sou²adniceMíst[modTSP_ZadávanéMísto*2] < 0 || modTSP_Sou²adniceMíst[modTSP_ZadávanéMísto*2] > 635);
  270.         GrNastavV∞stup(mod_GRAFIKA_VφSTUP_MOJEPLOCHA);
  271.         }
  272.  
  273.       // ZJIµT╖N╓ Y SOUⁿADNICE PR╡V╖ ZAD╡VANÉHO M╓STA
  274.       mod_VypiτHláτku("Zadejte Y sou²adnici místa "+(string)(char)('A'+modTSP_ZadávanéMísto)+" v pixelech [0-442]: ", mod_VYPIµHL╡µKU_NE¼EKEJ);
  275.       if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) {
  276.         while((VyprázdniFrontuKláves(),Txt¼tiI¼íslo(modTSP_Sou²adniceMíst[modTSP_ZadávanéMísto*2+1])) || modTSP_Sou²adniceMíst[modTSP_ZadávanéMísto*2+1] < 0 || modTSP_Sou²adniceMíst[modTSP_ZadávanéMísto*2+1] > 442);
  277.         }
  278.       else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) {
  279.         GrNastavV∞stup(mod_GRAFIKA_VφSTUP_POKYN);
  280.         while((VyprázdniFrontuKláves(),Gr¼tiI¼íslo("",modTSP_Sou²adniceMíst[modTSP_ZadávanéMísto*2+1],3,0,PalTmav╪Modrá<<4|Palªlutá)) || modTSP_Sou²adniceMíst[modTSP_ZadávanéMísto*2+1] < 0 || modTSP_Sou²adniceMíst[modTSP_ZadávanéMísto*2+1] > 442);
  281.         GrNastavV∞stup(mod_GRAFIKA_VφSTUP_MOJEPLOCHA);
  282.         }
  283.  
  284.       // ZOBRAZEN╓ PR╡V╖ ZAD╡VANÉHO M╓STA SPOLU S OSTATN╓MI JIª ZADANφMI
  285.       if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) {
  286.         modTSP_VykresliMapu(0, modTSP_ZadávanéMísto+1);
  287.         }
  288.  
  289.       // INFORMACE O SOUⁿADNICI PR╡V╖ ZAD╡VANÉHO M╓STA
  290.       if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) {
  291.         mod_VypiτHláτku("Sou²adnice místa "+(string)(char)('A'+modTSP_ZadávanéMísto)+" je "+StrL¼íslo(modTSP_Sou²adniceMíst[modTSP_ZadávanéMísto*2],-1)+","+StrL¼íslo(modTSP_Sou²adniceMíst[modTSP_ZadávanéMísto*2+1],-1)+"...", mod_VYPIµHL╡µKU_VY¼KEJ);
  292.         }
  293.       }
  294.     }
  295.   else if(modTSP_ZpàsobZadáváníMíst == modTSP_ZAD╡V╡N╓M╓ST_GRAFICKY) {
  296.     NastavJménoBankyP²edm╪tà("*\\backtraq");
  297.     MyτZapni();
  298.     MyτNastavGrKurzor(25);
  299.     MyτNastavPozici(mod_GRAFIKA_VφSTUP_MOJEPLOCHA_X1+(mod_GRAFIKA_VφSTUP_MOJEPLOCHA_X2-mod_GRAFIKA_VφSTUP_MOJEPLOCHA_X1)/2, mod_GRAFIKA_VφSTUP_MOJEPLOCHA_Y1+(mod_GRAFIKA_VφSTUP_MOJEPLOCHA_Y2-mod_GRAFIKA_VφSTUP_MOJEPLOCHA_Y1)/2);
  300.     for(modTSP_ZadávanéMísto=0; modTSP_ZadávanéMísto<modTSP_PoƒetMíst; modTSP_ZadávanéMísto++) {
  301.       // ZJIµT╖N╓ X SOUⁿADNICE PR╡V╖ ZAD╡VANÉHO M╓STA
  302.       mod_VypiτHláτku("Pomocí myτi zadejte sou²adnici místa "+(string)(char)('A'+modTSP_ZadávanéMísto)+".", mod_VYPIµHL╡µKU_NE¼EKEJ);
  303.       // vykreslení mapy - pouze dosud zadaná místa
  304.       modTSP_VykresliMapu(0, modTSP_ZadávanéMísto);
  305.       // nastavení a zobrazení myτi
  306.       MyτVyprázdniFrontuUdálostí();
  307.       MyτZobrazKurzor();
  308.       // vyƒkání na volbu pozice práv╪ zadávaného místa
  309.       do{
  310.         Myτ¼tiUdálost(gMyτUdálost);
  311.         }while(gMyτUdálost.Typ != MyτUdálostLevéTlNahoru);
  312.       gMyτUdálost.X -= mod_GRAFIKA_VφSTUP_MOJEPLOCHA_X1;
  313.       gMyτUdálost.Y -= mod_GRAFIKA_VφSTUP_MOJEPLOCHA_Y1;
  314.       // schování kurzoru myτi
  315.       MyτSchovejKurzor();
  316.       // uloºení zadan∞ch hodnot do pole
  317.       modTSP_Sou²adniceMíst[modTSP_ZadávanéMísto*2] = gMyτUdálost.X;
  318.       modTSP_Sou²adniceMíst[modTSP_ZadávanéMísto*2+1] = gMyτUdálost.Y;
  319.       }
  320.     MyτVypni();
  321.     NastavJménoBankyP²edm╪tà("*\\backtraq.mod\\"+AktivníModul->KrátkéJméno);
  322.     }
  323.  
  324.   // ZJIµT╖N╓, KTERÉ POZICE ZOBRAZOVAT
  325.   mod_NechZvolit_Volby[0] = "jen ²eτení"; mod_NechZvolit_AccessKeys[0] = '²';
  326.   mod_NechZvolit_Volby[1] = "i pràb╪h hledání"; mod_NechZvolit_AccessKeys[1] = 'p';
  327.   switch(mod_NechZvolit("Zobrazovat jen nalezená ²eτení nebo i pràb╪h hledání (upozorn╪ní: pomalé)?")) {
  328.     case 0: mod_ZobrazovanéPozice = mod_POUZE_ⁿEµEN╓; break;
  329.     case 1: mod_ZobrazovanéPozice = mod_VµECHNY_POZICE; break;
  330.     }
  331.  
  332.   // INFORMACE O TOM, KTERÉ POZICE ZOBRAZOVAT
  333.   if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) {
  334.     mod_VypiτHláτku("Budu zobrazovat "+(mod_ZobrazovanéPozice==mod_POUZE_ⁿEµEN╓?"jen nalezená ²eτení":"i pràb╪h hledání")+"...", mod_VYPIµHL╡µKU_VY¼KEJ);
  335.     }
  336.  
  337.   // ZJIµT╖N╓, ZDA ¼EKAT PO NALEZEN╓ NOVÉHO NEJLEPµ╓HO ⁿEµEN╓ NA STISK KL╡VESY
  338.   if(mod_ZobrazovanéPozice == mod_POUZE_ⁿEµEN╓) {
  339.     // pokud se zobrazuje pouze v∞sledné nalezené ²eτení, po nalezení jednotliv∞ch nov∞ch nejlepτích ²eτení se nikdy neƒeká
  340.     mod_¼ekatNaKlávesu = 0;
  341.     }
  342.   else {
  343.     mod_NechZvolit_Volby[0] = "ano, vyƒkat"; mod_NechZvolit_AccessKeys[0] = 'a';
  344.     mod_NechZvolit_Volby[1] = "ne, neƒekat"; mod_NechZvolit_AccessKeys[1] = 'n';
  345.     switch(mod_NechZvolit("Vyƒkat po nalezení nového nejlepτího ²eτení na stisknutí klávesy?")) {
  346.       case 0: mod_¼ekatNaKlávesu = 1; break;
  347.       case 1: mod_¼ekatNaKlávesu = 0; break;
  348.       }
  349.  
  350.     // INFORMACE O TOM, ZDA PO NALEZEN╓ NOVÉHO NEJLEPµ╓HO ⁿEµEN╓ ¼EKAT NA STISK KL╡VESY
  351.     if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) {
  352.       mod_VypiτHláτku("Po nalezení nového nejlepτího ²eτení "+(mod_¼ekatNaKlávesu?"budu":"nebudu")+" ƒekat na stisk klávesy...", mod_VYPIµHL╡µKU_VY¼KEJ);
  353.       }
  354.     }
  355.  
  356.   // ZJIµT╖N╓, ZDA ZAPISOVAT PROTOKOL O VφPO¼TU DO SOUBORU
  357.   mod_NechZvolit_Volby[0] = "ano, zapisovat"; mod_NechZvolit_AccessKeys[0] = 'a';
  358.   mod_NechZvolit_Volby[1] = "ne, nezapisovat"; mod_NechZvolit_AccessKeys[1] = 'n';
  359.   switch(mod_NechZvolit("Zapisovat protokol o v∞poƒtu do souboru?")) {
  360.     case 0: mod_ZapisovatProtokol = 1; break;
  361.     case 1: mod_ZapisovatProtokol = 0; break;
  362.     }
  363.  
  364.   // INFORMACE O TOM, ZDA ZAPISOVAT PROTOKOL O VφPO¼TU DO SOUBORU
  365.   if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) {
  366.     mod_VypiτHláτku("Protokol o v∞poƒtu "+(mod_ZapisovatProtokol?"budu":"nebudu")+" zapisovat do souboru...", mod_VYPIµHL╡µKU_VY¼KEJ);
  367.     }
  368.  
  369.   if(mod_ZapisovatProtokol) {
  370.     // ZJIµT╖N╓ N╡ZVU SOUBORU, KAM ZAPISOVAT PROTOKOL O VφPO¼TU
  371.     mod_VypiτHláτku("Zadejte název souboru: ", mod_VYPIµHL╡µKU_NE¼EKEJ);
  372.     mod_ZapisovatProtokol_Název = "";
  373.     if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) {
  374.       Txtⁿádkov∞Editor(mod_ZapisovatProtokol_Název,50,50,-1,0);
  375.       TxtPiτNov∞ⁿádek();
  376.       }
  377.     else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) {
  378.       GrNastavV∞stup(mod_GRAFIKA_VφSTUP_POKYN);
  379.       VyprázdniFrontuKláves();
  380.       Grⁿádkov∞Editor(mod_ZapisovatProtokol_Název,50,-1,0,-1,PalTmav╪Modrá<<4|Palªlutá);
  381.       GrNastavV∞stup(mod_GRAFIKA_VφSTUP_MOJEPLOCHA);
  382.       }
  383.     if(StrKopie(mod_ZapisovatProtokol_Název, 1, 1) != ":") mod_ZapisovatProtokol_Název = "*\\" + mod_ZapisovatProtokol_Název;
  384.  
  385.     // INFORMACE O N╡ZVU SOUBORU, KAM ZAPISOVAT PROTOKOL O VφPO¼TU
  386.     if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) {
  387.       mod_VypiτHláτku("Zvolen soubor "+mod_ZapisovatProtokol_Název+"...", mod_VYPIµHL╡µKU_VY¼KEJ);
  388.       }
  389.     }
  390.   }
  391.  
  392. void modTSP_OptimalizaceVstupu(void) {
  393.   }
  394.  
  395. void modTSP_OpakováníInicializace(void) {
  396.   modTSP_Cesta[modTSP_Θroveσ] = 0;
  397.   }
  398.  
  399. int modTSP_OpakováníTest(void) {
  400.   // kdyº se nejedná o první místo na cest╪ a kdyº je jeτt╪ jaká místa procházet (procházení jeτt╪ nebylo dokonƒeno)
  401.   if(modTSP_Θroveσ > 0 && modTSP_Cesta[modTSP_Θroveσ] < modTSP_PoƒetMíst) {
  402.     // p²ipoƒtení délky cesty k práv╪ procházenému místu k délce testované cesty
  403.     modTSP_DélkaCesty += modTSP_ZjistiVzdálenostMíst(modTSP_Cesta[modTSP_Θroveσ], modTSP_Cesta[modTSP_Θroveσ-1]);
  404.     }
  405.   // vrácení informace o tom, zda se má pokraƒovat v procházení nebo jiº bylo dokonƒeno
  406.   return modTSP_Cesta[modTSP_Θroveσ] < modTSP_PoƒetMíst;
  407.   }
  408.  
  409. void modTSP_OpakováníIterace(void) {
  410.   // kdyº se nejedná o první místo na cest╪
  411.   if(modTSP_Θroveσ > 0) {
  412.     // odeƒtení délky cesty k práv╪ doprocházenému místu od délky testované cesty
  413.     modTSP_DélkaCesty -= modTSP_ZjistiVzdálenostMíst(modTSP_Cesta[modTSP_Θroveσ], modTSP_Cesta[modTSP_Θroveσ-1]);
  414.     }
  415.   // p²echod k následujícímu místu
  416.   modTSP_Cesta[modTSP_Θroveσ]++;
  417.   }
  418.  
  419. void modTSP_Dalτí¼lánek_P²ed(void) {
  420.   // zv∞τení úrovn╪ backtrackingu (poƒet míst v práv╪ testované cest╪)
  421.   modTSP_Θroveσ++;
  422.   }
  423.  
  424. void modTSP_Dalτí¼lánek_Po(void) {
  425.   // zmenτení úrovn╪ backtrackingu (poƒet míst v práv╪ testované cest╪)
  426.   modTSP_Θroveσ--;
  427.   }
  428.  
  429. int modTSP_TestVyhovuje(void) {
  430.   int modTSP_Procházen∞Prvek;
  431.  
  432.   // zjiτt╪ní, zda nalezená pozice vyhovuje podmínkám úlohy
  433.  
  434.   // kontrola, zda n╪které z míst jiº v cest╪ obsaºen∞ch není shodné s místem práv╪ do cesty p²idan∞m
  435.   for(modTSP_Procházen∞Prvek=0; modTSP_Procházen∞Prvek<modTSP_Θroveσ; modTSP_Procházen∞Prvek++) {
  436.     if(modTSP_Cesta[modTSP_Procházen∞Prvek] == modTSP_Cesta[modTSP_Θroveσ]) {
  437.       // vrácení informace, ºe nalezená pozice nevyhovuje podmínkám úlohy
  438.       return 0;
  439.       }
  440.     }
  441.  
  442.   // je testovaná pozice stále lepτí neº doposud nejlepτí nalezené ²eτení?
  443.   if(!(modTSP_DélkaCesty < modTSP_Nejlepτíⁿeτení_DélkaCesty)) {
  444.     // ne, není => pozice tedy není vyhovující (hledá se jen to nejlepτí ²eτení)
  445.     return 0;
  446.     }
  447.  
  448.   // zobrazení práv╪ testované pozice, pokud si uºivatel toto nastavil
  449.   if(mod_ZobrazovanéPozice == mod_VµECHNY_POZICE) {
  450.     if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) {
  451.       TxtPiτⁿet╪zec(modTSP_PoleCestyNaⁿet╪zec(modTSP_Cesta, &modTSP_Θroveσ, &modTSP_DélkaCesty));
  452.       TxtPiτNov∞ⁿádek();
  453.       }
  454.     else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) {
  455.       modTSP_VykresliMapu(modTSP_Cesta, modTSP_Θroveσ);
  456.       if(modTSP_PoƒetMíst <= 4) ¼ekej(1.0/modTSP_PoƒetMíst*2800-200);
  457.       }
  458.     if(mod_ZapisovatProtokol) {
  459.       SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Testuji ");
  460.       SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, modTSP_PoleCestyNaⁿet╪zec(modTSP_Cesta, &modTSP_Θroveσ, &modTSP_DélkaCesty));
  461.       SouborPiτNov∞ⁿádek(mod_ZapisovatProtokol_Soubor);
  462.       }
  463.     }
  464.  
  465.   // vrácení informace, ºe nalezená pozice vyhovuje podmínkám úlohy
  466.   return 1;
  467.   }
  468.  
  469. int modTSP_TestNalezeno(void) {
  470.   // nov∞ kandidát na ²eτení byl nalezen, pokud je práv╪ nalezené ²eτení kompletní
  471.   return (modTSP_Θroveσ == modTSP_PoƒetMíst-1);
  472.   }
  473.  
  474. void modTSP_Nalezeno(void) {
  475.   // uloºení nalezeného ²eτení jako dosud nejlepτího
  476.   memmove(modTSP_Nejlepτíⁿeτení_Cesta, modTSP_Cesta, modTSP_PoƒetMíst*sizeof(modTSP_Cesta[0]));
  477.   modTSP_Nejlepτíⁿeτení_DélkaCesty = modTSP_DélkaCesty;
  478.   modTSP_Nejlepτíⁿeτení_Θroveσ = modTSP_Θroveσ;
  479.   // zobrazení práv╪ nalezeného ²eτení
  480.   if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) {
  481.     TxtPiτⁿet╪zec("Nalezeno dosud nejlepτí ²eτení: ");
  482.     TxtPiτⁿet╪zec(modTSP_PoleCestyNaⁿet╪zec(modTSP_Cesta, &modTSP_Θroveσ, &modTSP_DélkaCesty));
  483.     TxtPiτNov∞ⁿádek();
  484.     }
  485.   else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) {
  486.     mod_VypiτHláτku("Nalezeno dosud nejlepτí ²eτení: " + modTSP_PoleCestyNaⁿet╪zec(modTSP_Cesta, &modTSP_Θroveσ, &modTSP_DélkaCesty), mod_VYPIµHL╡µKU_NE¼EKEJ);
  487.     if(mod_ZobrazovanéPozice == mod_POUZE_ⁿEµEN╓) modTSP_VykresliMapu(modTSP_Nejlepτíⁿeτení_Cesta, modTSP_Nejlepτíⁿeτení_Θroveσ);
  488.     }
  489.   // zápis práv╪ nalezeného ²eτení do souboru, pokud si to uºivatel p²ál
  490.   if(mod_ZapisovatProtokol) {
  491.     SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "NALEZENO DOSUD NEJLEPµ╓ ⁿEµEN╓: ");
  492.     SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, modTSP_PoleCestyNaⁿet╪zec(modTSP_Cesta, &modTSP_Θroveσ, &modTSP_DélkaCesty));
  493.     SouborPiτNov∞ⁿádek(mod_ZapisovatProtokol_Soubor);
  494.     }
  495.   // v p²ípad╪ grafického reºimu, pokud se ale nezobrazují pouze nalezená ²eτení, pípnutí - oznámení nalezení nového nejlepτího ²eτení
  496.   if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM && !(mod_ZobrazovanéPozice == mod_POUZE_ⁿEµEN╓)) { Tón(1000); ¼ekej(100); VypniTón(); }
  497.   // vyƒkání na stisk klávesy, pokud si to uºivatel p²ál
  498.   if(mod_¼ekatNaKlávesu) ¼ekejNaKlávesu();
  499.   }
  500.  
  501. void modTSP_InfoOModulu(struct _ModulInfo* ModulInfo) {
  502.   ModulInfo->KrátkéJméno = "TSP";
  503.   ModulInfo->DlouhéJméno = "Problém obchodního cestujícího";
  504.   ModulInfo->Popis = "Star∞, ale dosud stále nevy²eτen∞ problém. Obchodní cestující má za úkol navτtívit urƒité mnoºství míst, ve kter∞ch se nacházejí jeho zákazníci. Jak to má provést, aby kaºdé místo navτtívil práv╪ jednou a v∞sledná cesta p²itom byla co nejkratτí? Tento modul ²eτí problém obchodního cestujícího dosud jedinou spolehlivou metodou - vyzkouτením vτech moºností spolu s vyuºitím backtrackingu ke zredukování poƒtu t╪chto moºností. S problémem obchodního cestujícího se denn╪ nesetkávají pouze obchodní cestující, ale obecn╪ ràzní doruƒovatelé, jejichº úkolem je doruƒit zboºí na náhodn╪ umíst╪ná místa. Algoritmy ²eτící tento problém nacházejí vyuºití také p²i ²ízení pohybu plotterà a strojà pro v∞robu ploτn∞ch spojà.";
  505.   ModulInfo->Verze = 1.0;
  506.   ModulInfo->Datum.Den = 12;
  507.   ModulInfo->Datum.M╪síc = 9;
  508.   ModulInfo->Datum.Rok = 2002;
  509.   ModulInfo->Autor = "Marek Blahuτ";
  510.   ModulInfo->Kontakt = "blahus@seznam.cz";
  511.   ModulInfo->Start = &modTSP_Start;
  512.   ModulInfo->Hotovo = &modTSP_Hotovo;
  513.   ModulInfo->Θklid = &modTSP_Θklid;
  514.   ModulInfo->ZadáníVstupu = &modTSP_ZadáníVstupu;
  515.   ModulInfo->OptimalizaceVstupu = &modTSP_OptimalizaceVstupu;
  516.   ModulInfo->OpakováníInicializace = &modTSP_OpakováníInicializace;
  517.   ModulInfo->OpakováníTest = &modTSP_OpakováníTest;
  518.   ModulInfo->OpakováníIterace = &modTSP_OpakováníIterace;
  519.   ModulInfo->Dalτí¼lánek_P²ed = &modTSP_Dalτí¼lánek_P²ed;
  520.   ModulInfo->Dalτí¼lánek_Po = &modTSP_Dalτí¼lánek_Po;
  521.   ModulInfo->TestVyhovuje = &modTSP_TestVyhovuje;
  522.   ModulInfo->TestNalezeno = &modTSP_TestNalezeno;
  523.   ModulInfo->Nalezeno = &modTSP_Nalezeno;
  524.   }
  525.