class: center, middle, inverse, title-slide .title[ # Optymalizacja dyskretna <br>(w tym algorytmy heurystyczne) ] .subtitle[ ## Projekty ] .author[ ### Jakub Nowosad <br><a href="https://jakubnowosad.com/" class="uri">https://jakubnowosad.com/</a> ] --- class: inverse, left, bottom # 1 --- # 1 - problem ## Ułożenie optymalnej trasy wycieczki --- # 1 - dane ```r odleglosci = readr::read_csv("data/odleglosci.csv") DT::datatable(odleglosci[, 1:4], fillContainer = FALSE, options = list(pageLength = 5)) ``` <div class="datatables html-widget html-fill-item-overflow-hidden html-fill-item" id="htmlwidget-f4fad56dbb763466c627" style="width:100%;height:auto;"></div> <script type="application/json" data-for="htmlwidget-f4fad56dbb763466c627">{"x":{"filter":"none","vertical":false,"fillContainer":false,"data":[["1","2","3","4","5","6","7","8","9","10","11","12","13","14","15","16","17","18","19","20","21","22","23","24","25","26","27","28","29","30","31","32","33","34","35","36","37","38","39","40","41","42","43","44","45","46","47","48","49","50","51","52","53","54","55","56","57","58","59","60","61","62","63","64","65","66"],["Biała Podlaska","Białystok","Bielsko-Biała","Bydgoszcz","Chełm","Częstochowa","Elbląg","Gdańsk","Gdynia","Gorzów Wielkopolski","Jelenia Góra","Kalisz","Katowice","Kielce","Konin","Koszalin","Kraków","Krosno","Legnica","Leszno","Lublin","Łomża","Łódź","Nowy Sącz","Olsztyn","Opole","Ostrołęka","Piotrków Trybunalski","Płock","Poznań","Przemyśl","Radom","Ruda Śląska","Rybnik","Rzeszów","Siedlce","Siemianowice Śląskie","Skierniewice","Słupsk","Suwałki","Szczecin","Świnoujście","Tarnobrzeg","Tarnów","Toruń","Wałbrzych","Warszawa","Włocławek","Wrocław","Zamość","Zielona Góra","Grudziądz","Sopot","Chorzów","Bytom","Dąbrowa Górnicza","Gliwice","Jastrzębie-Zdrój","Jaworzno","Mysłowice","Piekary Śląskie","Sosnowiec","Świętochłowice","Tychy","Zabrze","Żory"],[null,154,491,415,127,383,428,487,505,600,631,416,460,268,364,600,374,356,576,505,121,210,297,406,238,477,203,297,274,466,336,94,443,480,296,61,414,237,587,270,675,675,244,347,369,572,162,322,504,186,588,477,480,429,440,408,451,499,408,421,439,416,431,437,431,482],[154,null,542,400,281,410,335,395,461,608,630,445,490,365,390,585,445,545,610,510,295,75,215,510,235,505,113,330,275,485,470,295,512,530,430,170,485,274,525,116,660,710,370,480,350,605,190,315,535,340,615,370,408,483,479,478,505,548,497,491,477,481,496,507,488,531],[491,542,null,460,408,130,595,595,601,495,340,300,55,225,340,640,85,308,300,325,340,540,260,150,535,145,514,215,355,400,340,295,66,70,255,480,75,293,660,674,600,728,265,170,420,280,400,360,230,385,385,473,694,69.2,77.9,78.4,93.2,56,53.4,61.2,116,65.7,71.7,43.7,98.1,56.7]],"container":"<table class=\"display\">\n <thead>\n <tr>\n <th> <\/th>\n <th>city<\/th>\n <th>Biała Podlaska<\/th>\n <th>Białystok<\/th>\n <th>Bielsko-Biała<\/th>\n <\/tr>\n <\/thead>\n<\/table>","options":{"pageLength":5,"columnDefs":[{"className":"dt-right","targets":[2,3,4]},{"orderable":false,"targets":0}],"order":[],"autoWidth":false,"orderClasses":false,"lengthMenu":[5,10,25,50,100]}},"evals":[],"jsHooks":[]}</script> --- # 1 - dane ```r wagi_miast = readr::read_csv("data/wagi_miast.csv") DT::datatable(wagi_miast[, c(1:3, 23)], fillContainer = FALSE, options = list(pageLength = 5)) ``` <div class="datatables html-widget html-fill-item-overflow-hidden html-fill-item" id="htmlwidget-425ac54f944fb1a7ab86" style="width:100%;height:auto;"></div> <script type="application/json" data-for="htmlwidget-425ac54f944fb1a7ab86">{"x":{"filter":"none","vertical":false,"fillContainer":false,"data":[["1","2","3","4","5","6","7","8","9","10","11","12","13","14","15","16","17","18","19","20","21","22","23","24","25","26","27","28","29","30","31","32","33","34","35","36","37","38","39","40","41","42","43","44","45","46","47","48","49","50","51","52","53","54","55","56","57","58","59","60","61","62","63","64","65","66"],["Biała Podlaska","Białystok","Bielsko-Biała","Bydgoszcz","Chełm","Częstochowa","Elbląg","Gdańsk","Gdynia","Gorzów Wielkopolski","Jelenia Góra","Kalisz","Katowice","Kielce","Konin","Koszalin","Kraków","Krosno","Legnica","Leszno","Lublin","Łomża","Łódź","Nowy Sącz","Olsztyn","Opole","Ostrołęka","Piotrków Trybunalski","Płock","Poznań","Przemyśl","Radom","Ruda Śląska","Rybnik","Rzeszów","Siedlce","Siemianowice Śląskie","Skierniewice","Słupsk","Suwałki","Szczecin","Świnoujście","Tarnobrzeg","Tarnów","Toruń","Wałbrzych","Warszawa","Włocławek","Wrocław","Zamość","Zielona Góra","Grudziądz","Sopot","Chorzów","Bytom","Dąbrowa Górnicza","Gliwice","Jastrzębie-Zdrój","Jaworzno","Mysłowice","Piekary Śląskie","Sosnowiec","Świętochłowice","Tychy","Zabrze","Żory"],[7.42857142857143,14.8571428571429,14.8571428571429,14.8571428571429,7.42857142857143,11.1428571428571,11.1428571428571,18.5714285714286,11.1428571428571,11.1428571428571,14.8571428571429,7.42857142857143,14.8571428571429,14.8571428571429,3.71428571428571,7.42857142857143,18.5714285714286,11.1428571428571,11.1428571428571,7.42857142857143,18.5714285714286,3.71428571428571,14.8571428571429,7.42857142857143,14.8571428571429,14.8571428571429,3.71428571428571,7.42857142857143,11.1428571428571,18.5714285714286,11.1428571428571,11.1428571428571,3.71428571428571,7.42857142857143,18.5714285714286,7.42857142857143,3.71428571428571,3.71428571428571,7.42857142857143,7.42857142857143,14.8571428571429,14.8571428571429,11.1428571428571,11.1428571428571,14.8571428571429,11.1428571428571,18.5714285714286,11.1428571428571,18.5714285714286,14.8571428571429,14.8571428571429,11.1428571428571,14.8571428571429,7.42857142857143,3.71428571428571,7.42857142857143,11.1428571428571,7.42857142857143,7.42857142857143,3.71428571428571,7.42857142857143,7.42857142857143,3.71428571428571,11.1428571428571,11.1428571428571,7.42857142857143],[7.14285714285714,7.14285714285714,14.2857142857143,10.7142857142857,10.7142857142857,10.7142857142857,14.2857142857143,10.7142857142857,3.57142857142857,14.2857142857143,14.2857142857143,14.2857142857143,7.14285714285714,14.2857142857143,10.7142857142857,14.2857142857143,17.8571428571429,10.7142857142857,14.2857142857143,7.14285714285714,10.7142857142857,10.7142857142857,10.7142857142857,10.7142857142857,10.7142857142857,17.8571428571429,10.7142857142857,17.8571428571429,14.2857142857143,14.2857142857143,10.7142857142857,17.8571428571429,3.57142857142857,10.7142857142857,10.7142857142857,7.14285714285714,3.57142857142857,10.7142857142857,10.7142857142857,7.14285714285714,14.2857142857143,7.14285714285714,7.14285714285714,10.7142857142857,17.8571428571429,10.7142857142857,17.8571428571429,14.2857142857143,17.8571428571429,7.14285714285714,10.7142857142857,10.7142857142857,7.14285714285714,7.14285714285714,14.2857142857143,7.14285714285714,14.2857142857143,3.57142857142857,7.14285714285714,10.7142857142857,3.57142857142857,7.14285714285714,3.57142857142857,3.57142857142857,7.14285714285714,14.2857142857143],[9.24263038548753,12.3424036281179,10.1360544217687,12.4988662131519,8.8140589569161,11.968253968254,9.7891156462585,14.6371882086168,12.0090702947846,10.0748299319728,10.984126984127,11.4399092970522,12.7800453514739,12.7369614512472,8.91383219954649,11.8367346938776,14.827664399093,8.80498866213152,10.3877551020408,8.68253968253968,12.6009070294785,10.5963718820862,14.4580498866213,8.42630385487528,12.437641723356,13.1111111111111,8.32879818594104,9.13378684807256,11.8231292517007,15.3446712018141,7.69387755102041,10.4081632653061,8.37414965986395,9.43990929705215,11.4580498866213,7.88208616780045,7.71655328798186,7.40362811791383,10.7959183673469,9.63038548752834,13.827664399093,10.7301587301587,9.00907029478458,10.2222222222222,12.2743764172336,10.0793650793651,15.4671201814059,9.90249433106576,14.6235827664399,9.58503401360544,12.4852607709751,10.3514739229025,10.9455782312925,8.89115646258503,9.31292517006803,8.85487528344671,11.1904761904762,8.56916099773243,8.52380952380952,7.44444444444444,7.90702947845805,9.82993197278912,7.26757369614513,10.1768707482993,10.5646258503401,8.58730158730159]],"container":"<table class=\"display\">\n <thead>\n <tr>\n <th> <\/th>\n <th>Nazwa<\/th>\n <th>likes_restaurants<\/th>\n <th>interested_in_history<\/th>\n <th>srednia_waga<\/th>\n <\/tr>\n <\/thead>\n<\/table>","options":{"pageLength":5,"columnDefs":[{"className":"dt-right","targets":[2,3,4]},{"orderable":false,"targets":0}],"order":[],"autoWidth":false,"orderClasses":false,"lengthMenu":[5,10,25,50,100]}},"evals":[],"jsHooks":[]}</script> --- # 1 - wymagania 1. **Podstawowe** - określenie optymalnej trasy do 1500 kilometrów składającej się z pięciu przystanków (miast) biorąc pod uwagę zmienną `srednia_waga` 2. **Dodatkowe** - pokazanie kilku innych scenariuszy (inna długość trasy, inna liczba przystanków, inna waga) 3. **Dodatkowe** - rozszerzenie rozwiązania poprzez stworzenie funkcji/aplikacji pozwalającej na wybór parametrów 4. **Dodatkowe** - stworzenie mapy reprezentującej wynikowe trasy 5. **Dodatkowe** - wszelkie inne pomysły --- class: inverse, left, bottom # 2 --- # 2 - problem ## Generowanie danych przestrzennych o zadanych parametrach <img src="XX-projekty_files/figure-html/unnamed-chunk-5-1.png" style="display: block; margin: auto;" /> --- # 2 - przykład - https://en.wikipedia.org/wiki/Entropy_(information_theory)#Definition $$ H(X) = -\sum_{i=1}^n {\mathrm{P}(x_i) \log_b \mathrm{P}(x_i)} $$ .pull-left[ <img src="XX-projekty_files/figure-html/unnamed-chunk-6-1.png" style="display: block; margin: auto;" /> ] .pull-right[ ```r prop1 = table(ras1) / sum(table(ras1)) prop1 ``` ``` ## ras1 ## 1 ## 1 ``` ```r shdi1 = sum(-prop1 * log2(prop1)) shdi1 ``` ``` ## [1] 0 ``` ] --- # 2 - przykład - https://en.wikipedia.org/wiki/Entropy_(information_theory) $$ H(X) = -\sum_{i=1}^n {\mathrm{P}(x_i) \log_b \mathrm{P}(x_i)} $$ .pull-left[ <img src="XX-projekty_files/figure-html/unnamed-chunk-8-1.png" style="display: block; margin: auto;" /> ] .pull-right[ ```r prop2 = table(ras2) / sum(table(ras2)) prop2 ``` ``` ## ras2 ## 1 2 ## 0.734375 0.265625 ``` ```r shdi2 = sum(-prop2 * log2(prop2)) shdi2 ``` ``` ## [1] 0.8351165 ``` ] --- # 2 - przykład - https://en.wikipedia.org/wiki/Entropy_(information_theory) $$ H(X) = -\sum_{i=1}^n {\mathrm{P}(x_i) \log_b \mathrm{P}(x_i)} $$ .pull-left[ <img src="XX-projekty_files/figure-html/unnamed-chunk-10-1.png" style="display: block; margin: auto;" /> ] .pull-right[ ```r prop3 = table(ras3) / sum(table(ras3)) prop3 ``` ``` ## ras3 ## 1 2 ## 0.46875 0.53125 ``` ```r shdi3 = sum(-prop3 * log2(prop3)) shdi3 ``` ``` ## [1] 0.9971804 ``` ] --- # 2 - przykład - https://en.wikipedia.org/wiki/Entropy_(information_theory) $$ H(X) = -\sum_{i=1}^n {\mathrm{P}(x_i) \log_b \mathrm{P}(x_i)} $$ .pull-left[ <img src="XX-projekty_files/figure-html/unnamed-chunk-12-1.png" style="display: block; margin: auto;" /> ] .pull-right[ ```r prop4 = table(ras4) / sum(table(ras4)) prop4 ``` ``` ## ras4 ## 1 2 3 ## 0.390625 0.296875 0.312500 ``` ```r shdi4 = sum(-prop4 * log2(prop4)) shdi4 ``` ``` ## [1] 1.574288 ``` ] --- # 2 - dane ```r ras1 = readr::read_csv("data/ras1.csv") ras2 = readr::read_csv("data/ras2.csv") ras3 = readr::read_csv("data/ras3.csv") ras4 = readr::read_csv("data/ras4.csv") ``` ```r ras4 ``` ``` ## # A tibble: 8 × 8 ## V1 V2 V3 V4 V5 V6 V7 V8 ## <dbl> <dbl> <dbl> <dbl> <dbl> <dbl> <dbl> <dbl> ## 1 1 1 1 1 1 2 3 1 ## 2 2 1 1 2 1 1 2 3 ## 3 2 2 3 2 2 1 2 1 ## 4 1 3 3 1 1 2 1 2 ## 5 1 2 3 3 3 3 2 2 ## 6 3 2 1 2 1 3 3 3 ## 7 3 1 1 2 2 3 3 3 ## 8 2 1 3 3 1 3 1 1 ``` --- # 2 - wymagania 1. **Podstawowe** - stworzenie funkcji/aplikacji generującej dane przestrzenne na podstawie zadanej entropii 2. **Dodatkowe** - stworzenie funkcji/aplikacji generującej dane przestrzenne na podstawie zadanej entropii oraz liczbie kategorii 3. **Dodatkowe** - stworzenie wizualizacji wyników 4. **Dodatkowe** - rozszerzenie rozwiązania poprzez umożliwienie generacji danych na podstawie innych parametrów 5. **Dodatkowe** - wszelkie inne pomysły --- class: inverse, left, bottom # 3 --- # 3 - problem ## Zlokalizowanie sześciu sklepów <img src="XX-projekty_files/figure-html/unnamed-chunk-17-1.png" style="display: block; margin: auto;" /> --- # 3 - przykład <img src="XX-projekty_files/figure-html/unnamed-chunk-18-1.png" style="display: block; margin: auto;" /> --- # 3 - dane ```r library(sf) ludnosc = read_sf("data/ludnosc_poznan_250.gpkg") ludnosc ``` ``` ## Simple feature collection with 4459 features and 1 field ## Geometry type: POLYGON ## Dimension: XY ## Bounding box: xmin: 345850 ymin: 493650 xmax: 369100 ymax: 517900 ## Projected CRS: ETRF2000-PL / CS92 ## # A tibble: 4,459 × 2 ## ludnosc geom ## <dbl> <POLYGON [m]> ## 1 0 ((362850 493650, 363100 493650, 363100 493900, 362850 493900, 362850… ## 2 0 ((363100 493650, 363350 493650, 363350 493900, 363100 493900, 363100… ## 3 0 ((363350 493650, 363600 493650, 363600 493900, 363350 493900, 363350… ## 4 0 ((362850 493900, 363100 493900, 363100 494150, 362850 494150, 362850… ## 5 0 ((363100 493900, 363350 493900, 363350 494150, 363100 494150, 363100… ## 6 0 ((363350 493900, 363600 493900, 363600 494150, 363350 494150, 363350… ## 7 0 ((363600 493900, 363850 493900, 363850 494150, 363600 494150, 363600… ## 8 0 ((363850 493900, 364100 493900, 364100 494150, 363850 494150, 363850… ## 9 0 ((362350 494150, 362600 494150, 362600 494400, 362350 494400, 362350… ## 10 0 ((362600 494150, 362850 494150, 362850 494400, 362600 494400, 362600… ## # ℹ 4,449 more rows ``` --- # 3 - wymagania 1. **Podstawowe** - określenie lokalizacji sześciu sklepów; każdy sklep ma strefę wpływu o promieniu 1,5 km. Strefa wpływu wszystkich sklepów powinna obejmować swoim zasięgiem jak największą liczbę osób. 2. **Dodatkowe** - stworzenie funkcji/aplikacji pozwalającej na określenie dowolnej liczby sklepów i ich stref wpływu 3. **Dodatkowe** - stworzenie wizualizacji wyników 4. **Dodatkowe** - rozszerzenie rozwiązania poprzez uwzględnienie odległości wzdłuż sieci drogowej 5. **Dodatkowe** - wszelkie inne pomysły --- class: inverse, left, bottom # 4 --- # 4 - inne <img src="images/qmark.png" width="68%" style="display: block; margin: auto;" /> --- class: inverse, left, bottom # Założenia --- # Założenia - 1-2 osoby - Przesyłanie projektu poprzez https://jakubnowosad.com/dydaktyka/ - Termin przesłania projektu: 2022-05-23 12:00 - Termin prezentacji projektu: 2022-05-25 ## Efekty: 1. Kod/funkcje/aplikacja rozwiązująca problem 2. Prezentacja (ok. 10 minut) obrazująca przyjęte podejście i rozwiązanie problemu