class: center, middle, inverse, title-slide .title[ # Optymalizacja dyskretna
(w tym algorytmy heurystyczne) ] .subtitle[ ## Projekty ] .author[ ### Jakub Nowosad
https://jakubnowosad.com/
] --- 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)) ```
--- # 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)) ```
--- # 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