SHARE
TWEET

Untitled

a guest Mar 26th, 2020 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // SADlg.cpp : implementation file
  2. //
  3.  
  4. #include "stdafx.h"
  5. #include "SA.h"
  6. #include "SADlg.h"
  7. #include <math.h>
  8. #include <stdlib.h>
  9. #include <random>
  10.  
  11. #ifdef _DEBUG
  12. #define new DEBUG_NEW
  13. #undef THIS_FILE
  14. static char THIS_FILE[] = __FILE__;
  15. #endif
  16. double fRand(double fMin, double fMax)
  17. {
  18.     double f = (double)rand() / RAND_MAX;
  19.     return fMin + f * (fMax - fMin);
  20. }
  21. /////////////////////////////////////////////////////////////////////////////
  22. // CAboutDlg dialog used for App About
  23.  
  24. class CAboutDlg : public CDialog
  25. {
  26. public:
  27.     CAboutDlg();
  28.  
  29. // Dialog Data
  30.     //{{AFX_DATA(CAboutDlg)
  31.     enum { IDD = IDD_ABOUTBOX };
  32.     //}}AFX_DATA
  33.  
  34.     // ClassWizard generated virtual function overrides
  35.     //{{AFX_VIRTUAL(CAboutDlg)
  36.     protected:
  37.     virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
  38.     //}}AFX_VIRTUAL
  39.  
  40. // Implementation
  41. protected:
  42.     //{{AFX_MSG(CAboutDlg)
  43.     //}}AFX_MSG
  44.     DECLARE_MESSAGE_MAP()
  45. };
  46.  
  47. CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
  48. {
  49.     //{{AFX_DATA_INIT(CAboutDlg)
  50.     //}}AFX_DATA_INIT
  51. }
  52.  
  53. void CAboutDlg::DoDataExchange(CDataExchange* pDX)
  54. {
  55.     CDialog::DoDataExchange(pDX);
  56.     //{{AFX_DATA_MAP(CAboutDlg)
  57.     //}}AFX_DATA_MAP
  58. }
  59.  
  60. BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
  61.     //{{AFX_MSG_MAP(CAboutDlg)
  62.         // No message handlers
  63.     //}}AFX_MSG_MAP
  64. END_MESSAGE_MAP()
  65.  
  66. /////////////////////////////////////////////////////////////////////////////
  67. // CSADlg dialog
  68.  
  69. CSADlg::CSADlg(CWnd* pParent /*=NULL*/)
  70.     : CDialog(CSADlg::IDD, pParent)
  71. {
  72.     //{{AFX_DATA_INIT(CSADlg)
  73.         // NOTE: the ClassWizard will add member initialization here
  74.     //}}AFX_DATA_INIT
  75.     // Note that LoadIcon does not require a subsequent DestroyIcon in Win32
  76.     m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
  77. }
  78.  
  79. void CSADlg::DoDataExchange(CDataExchange* pDX)
  80. {
  81.     CDialog::DoDataExchange(pDX);
  82.     //{{AFX_DATA_MAP(CSADlg)
  83.     DDX_Control(pDX, IDC_CITY_FRAME, m_CityFrame);
  84.     //}}AFX_DATA_MAP
  85. }
  86.  
  87. BEGIN_MESSAGE_MAP(CSADlg, CDialog)
  88.     //{{AFX_MSG_MAP(CSADlg)
  89.     ON_WM_SYSCOMMAND()
  90.     ON_WM_PAINT()
  91.     ON_WM_QUERYDRAGICON()
  92.     ON_BN_CLICKED(IDC_START, OnStart)
  93.     //}}AFX_MSG_MAP
  94. END_MESSAGE_MAP()
  95.  
  96. /////////////////////////////////////////////////////////////////////////////
  97. // CSADlg message handlers
  98.  
  99. BOOL CSADlg::OnInitDialog()
  100. {
  101.     CDialog::OnInitDialog();
  102.  
  103.     // Add "About..." menu item to system menu.
  104.  
  105.     // IDM_ABOUTBOX must be in the system command range.
  106.     ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
  107.     ASSERT(IDM_ABOUTBOX < 0xF000);
  108.  
  109.     CMenu* pSysMenu = GetSystemMenu(FALSE);
  110.     if (pSysMenu != NULL)
  111.     {
  112.         CString strAboutMenu;
  113.         strAboutMenu.LoadString(IDS_ABOUTBOX);
  114.         if (!strAboutMenu.IsEmpty())
  115.         {
  116.             pSysMenu->AppendMenu(MF_SEPARATOR);
  117.             pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
  118.         }
  119.     }
  120.  
  121.     // Set the icon for this dialog.  The framework does this automatically
  122.     //  when the application's main window is not a dialog
  123.     SetIcon(m_hIcon, TRUE);         // Set big icon
  124.     SetIcon(m_hIcon, FALSE);        // Set small icon
  125.    
  126.    
  127.     srand((unsigned)time(NULL));
  128.  
  129.     CRect r;
  130.     m_CityFrame.GetClientRect(&r);
  131.  
  132.     m_memDC.CreateCompatibleDC(GetDC());
  133.     m_bmp.CreateCompatibleBitmap(GetDC(), r.Width(), r.Height());
  134.     m_font.CreatePointFont(110, "Arial");
  135.     m_pen.CreatePen(PS_SOLID, 1, RGB(255, 0, 0));
  136.     m_brush.CreateSolidBrush(RGB(255, 255, 255));
  137.    
  138.     m_memDC.SelectObject(&m_bmp);
  139.     m_memDC.SelectObject(&m_font);
  140.     m_memDC.SelectObject(&m_pen);
  141.     m_memDC.SelectObject(&m_brush);
  142.  
  143.     m_CityFrame.GetClientRect(&r);
  144.     m_memDC.Rectangle(&r);
  145.  
  146.     m_memDC.SetBkMode(TRANSPARENT);
  147.    
  148.     COLORREF oldTxtCol = (m_memDC.SetTextColor(RGB (0, 100, 10)));
  149.    
  150.     return TRUE;  // return TRUE  unless you set the focus to a control
  151. }
  152.  
  153. void CSADlg::OnSysCommand(UINT nID, LPARAM lParam)
  154. {
  155.     if ((nID & 0xFFF0) == IDM_ABOUTBOX)
  156.     {
  157.         CAboutDlg dlgAbout;
  158.         dlgAbout.DoModal();
  159.     }
  160.     else
  161.     {
  162.         CDialog::OnSysCommand(nID, lParam);
  163.     }
  164. }
  165.  
  166. // If you add a minimize button to your dialog, you will need the code below
  167. //  to draw the icon.  For MFC applications using the document/view model,
  168. //  this is automatically done for you by the framework.
  169.  
  170. void CSADlg::OnPaint()
  171. {
  172.     if (IsIconic())
  173.     {
  174.         CPaintDC dc(this); // device context for painting
  175.  
  176.         SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);
  177.  
  178.         // Center icon in client rectangle
  179.         int cxIcon = GetSystemMetrics(SM_CXICON);
  180.         int cyIcon = GetSystemMetrics(SM_CYICON);
  181.         CRect rect;
  182.         GetClientRect(&rect);
  183.         int x = (rect.Width() - cxIcon + 1) / 2;
  184.         int y = (rect.Height() - cyIcon + 1) / 2;
  185.  
  186.         // Draw the icon
  187.         dc.DrawIcon(x, y, m_hIcon);
  188.     }
  189.     else
  190.     {
  191.         CPaintDC dc(this); // device context for painting
  192.  
  193.         CRect r;
  194.         m_CityFrame.GetWindowRect(&r);
  195.         ScreenToClient(r);     
  196.  
  197.         dc.BitBlt(r.left, r.top, r.right - r.left, r.bottom - r.top, &m_memDC, 0, 0, SRCCOPY);
  198.    
  199.         CDialog::OnPaint();
  200.     }
  201. }
  202.  
  203. // The system calls this to obtain the cursor to display while the user drags
  204. //  the minimized window.
  205. HCURSOR CSADlg::OnQueryDragIcon()
  206. {
  207.     return (HCURSOR) m_hIcon;
  208. }
  209.  
  210. /**************************************************************************}
  211. {ODCZYT MAPY Z PLIKU, WYZNACZENIE TEMPERATURY POCZATKOWEJ                  }
  212. {**************************************************************************/
  213. BOOL CSADlg::InitializeMap()
  214. {
  215.  
  216.     int i, j, k;
  217.    
  218.     int stop;
  219.  
  220.     CFile f;
  221.     if (!f.Open("tsp-c.dat", CFile::modeRead | CFile::shareDenyWrite))
  222.     {
  223.         MessageBox("Proszę umieścić plik tsp-c.dat w katalogu, w którym znajduje się program.");
  224.         return FALSE;
  225.     }
  226.    
  227.     float fBuf;
  228.  
  229.     for (i = 0; i < NCITIES; i++)
  230.     {
  231.         f.Read(&fBuf, sizeof(float));
  232.         loc[i][0] = (double)fBuf;
  233.         f.Read(&fBuf, sizeof(float));
  234.         loc[i][1] = (double)fBuf;
  235.     };
  236.  
  237.     f.Close();
  238.     for (j = 0; j < NCITIES; j++)
  239.     {
  240.         do
  241.         {
  242.             stop = 1;
  243.             route[j] = rand() % NCITIES;
  244.             k=0;
  245.          
  246.             while (k<j)
  247.             {
  248.                 if (route[k] == route[j]) stop = 0;
  249.                 k++;
  250.             };
  251.         }
  252.         while (!stop);
  253.      };
  254.  
  255.      T = 15.0;
  256.      energy = 0;
  257.  
  258.      return TRUE;
  259. }
  260.  
  261. /**************************************************************************}
  262. {RYSOWANIE AKTUALNEJ TRASY, WYSWIETLANIE ENERGII                           }
  263. {**************************************************************************/
  264. void CSADlg::Draw()
  265. {
  266.  
  267.     int i, x, y, x1, y1;
  268.     char s[10];
  269.     CString sEn = "Energia: ";
  270.  
  271.     CRect r;
  272.     m_CityFrame.GetClientRect(&r);
  273.     m_memDC.Rectangle(&r);
  274.  
  275.     if (energy == 0.0)
  276.     {
  277.         sEn = "Oblicz wartość energii!";
  278.     }
  279.     else
  280.     {
  281.         _gcvt_s(s, sizeof(s), energy,5);
  282.         sEn += CString(s);
  283.     }
  284.  
  285.     m_memDC.TextOut(10, r.Height()-20, sEn);
  286.  
  287.     for (i = 0; i < NCITIES; i++)
  288.     {
  289.         x = 10 + (int)((r.Width()-20)*loc[i][0]);
  290.         y = 10 + (int)((r.Height()-20)*loc[i][1]);
  291.         m_memDC.Ellipse(x-5, y-5, x+5, y+5);
  292.     }
  293.  
  294.     for (i = 0; i < NCITIES-1; i++)
  295.     {
  296.         x = 10 + (int)((r.Width()-20)*loc[route[i]][0]);
  297.         y = 10 + (int)((r.Height()-20)*loc[route[i]][1]);
  298.         x1 = 10 + (int)((r.Width()-20)*loc[route[i+1]][0]);
  299.         y1 = 10 + (int)((r.Height()-20)*loc[route[i+1]][1]);
  300.         m_memDC.MoveTo(x, y);
  301.         m_memDC.LineTo(x1, y1);
  302.     };
  303.  
  304.     x = 10 + (int)((r.Width()-20)*loc[route[NCITIES-1]][0]);
  305.     y = 10 + (int)((r.Height()-20)*loc[route[NCITIES-1]][1]);
  306.     x1 = 10 + (int)((r.Width()-20)*loc[route[0]][0]);
  307.     y1 = 10 + (int)((r.Height()-20)*loc[route[0]][1]);
  308.     m_memDC.MoveTo(x, y);
  309.     m_memDC.LineTo(x1, y1);
  310.  
  311.     CDC* pDC = GetDC();
  312.     m_CityFrame.GetWindowRect(&r);
  313.     ScreenToClient(r);
  314.  
  315.     pDC->BitBlt(r.left, r.top, r.right - r.left, r.bottom - r.top, &m_memDC, 0, 0, SRCCOPY);
  316.  
  317.     ReleaseDC(pDC);
  318. }
  319.  
  320. void CSADlg::OnStart()
  321. {
  322.  
  323.     if (!InitializeMap())
  324.         return;
  325.  
  326.     Draw();
  327.     maxTrialN=NCITIES*100;
  328.     maxAcceptN=NCITIES*10;
  329.     stopTolerance=0.005;
  330.    
  331.     minE=1e20;
  332.     maxE=-1;
  333.  
  334.   /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!}
  335.   {TU WSTAWIC PETLE WYZARZANIA                                               }
  336.   {!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!}
  337.   Z pliku została wczytana mapa miast. Jest ich NCITIES. Ich współrzędne     
  338.   zawiera tablica loc[NCITIES][2]. Każdy wiersz tej tablicy to współrzędne
  339.   (x,y) jednego miasta.
  340.  
  341.   Losowo wybrana trasa jest umieszczona w tablicy route[NCITIES].
  342.   Trasa to ciąg liczb oznaczających miasta i jednocześnie wskazujących wiersze
  343.   tablicy 'loc' (aby można było odczytywać współrzędne miast).
  344.  
  345.   Procedura 'Draw' wyświetla trasę zawartą w 'route' i wartość zmiennej         
  346.   'energy' (o ile jest wyznaczona).
  347.   Temperatura początkowa jest ustawiona w zmiennej 'T'.
  348.  
  349.   Zmienne minE i maxE służą do przechowywania energii najlepszego
  350.   i najgorszego rozwiązania, zaakceptowanego w danym kroku (czyli przy
  351.   tej samej temperaturze). Sprawdzając wartość różnicy maxE-minE
  352.   można podejmować decyzję o zakończeniu bądź kontynuowaniu wyżarzania.
  353.  
  354.   Zmienne są zdefiniowane w pliku SADlg.h.
  355.  
  356.   ---Algorytm symulowanego wyżarzania---
  357.  
  358.   Poniższe kroki należy powtarzać, dopóki (maxE-minE)/maxE nie spadnie
  359.   poniżej progu określonego przez stopTolerance.
  360.  
  361. 1. Ustaw licznik prób i licznik zaakceptowanych prób na 0.
  362. 2. Oblicz energię E aktualnego rozwiązania.
  363. 3. Wyznacz nowe rozwiązanie (np. zamieniając miejscami dwa miasta w trasie).
  364. 4. Oblicz energię En nowego rozwiązania.
  365. 5. Zaakceptuj nowe rozwiązanie z prawdopodobieństwem 1/(1+exp(dE/T)), gdzie
  366.    (dE = En-E). W przypadku zaakceptowania zwiększ licznik zaakceptowanych prób.
  367. 6. Uaktualnij maxE i minE, jeśli jest to konieczne.
  368. 7. Zwiększ licznik prob. Jeżeli licznik prób lub licznik zaakceptowanych prób
  369.    osiągnęły maksymalną wartość (maxTrialN, maxAcceptN), idź do kroku 8. W przeciwnym razie wróć do kroku 3.
  370. 8. Uaktualnij zawartość zmiennych 'route' i 'energy', tak by opisywały ostatnią zaakceptowaną trasę.
  371. 9. Wywołaj funkcję 'Draw', aby uzyskać podgląd aktualnego rozwiązania.
  372. 10.Obniż temperaturę.
  373.  
  374.   {!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*/
  375.     srand(time(NULL));
  376.     double E = 0;
  377.     double En = 0;
  378.     int TrialN = 0;
  379.     int AcceptN = 0;
  380.     int tmproute[NCITIES];
  381.    
  382.    
  383.  
  384.     while ((maxE - minE) / maxE>stopTolerance) {
  385.         E = 0;
  386.         for (int i = 0; i < NCITIES - 1; i++)
  387.         {
  388.             E += sqrt(pow((loc[route[i]][0] - loc[route[i + 1]][0]), 2) + pow((loc[route[i]][1] - loc[route[i + 1]][1]), 2));
  389.         }
  390.         E += sqrt(pow((loc[route[NCITIES - 1]][0] - loc[route[0]][0]), 2) + pow((loc[route[NCITIES - 1]][1] - loc[route[0]][1]), 2));
  391.             int index = rand() % NCITIES;
  392.             int index2 = rand() % NCITIES;
  393.             double temp = route[index];
  394.             route[index] = route[index2];
  395.             route[index2] = temp;
  396.  
  397.         En = 0;
  398.         for (int i = 0; i < NCITIES - 1; i++)
  399.         {
  400.             En += sqrt(pow((loc[route[i]][0] - loc[route[i + 1]][0]), 2) + pow((loc[route[i]][1] - loc[route[i + 1]][1]), 2));
  401.         }
  402.         En += sqrt(pow((loc[route[NCITIES - 1]][0] - loc[route[0]][0]), 2) + pow((loc[route[NCITIES - 1]][1] - loc[route[0]][1]), 2));
  403.         double prawdopodobienstwo = 1 / (1 + exp((En - E) / T))/5;
  404.         double tmp = fRand(0,1);
  405.         if (En < E) {
  406.             AcceptN++;
  407.         for (int i = 0; i < NCITIES; i++)
  408.             tmproute[i] = route[i];
  409.         }
  410.         if (minE > En)
  411.             minE = En;
  412.         else if (maxE < En)
  413.             maxE = En;
  414.         TrialN++;
  415.         if (TrialN == maxTrialN || AcceptN == maxAcceptN)
  416.             break;
  417.     }
  418.     for (int i = 0; i < NCITIES; i++)
  419.         route[i] = tmproute[i];
  420.     energy = En;
  421.     Draw();
  422.     T = T * 0.7;
  423. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top