Pertemuan Hongaria dengan Euler pada ulang tahun ketiga – Beragampengetahuan
Oleh: Blog Bogumił Kamiński
Repost dari:
Saya sudah ngeblog ini selama tiga tahun sekarang, jadi saya sudah
Pikirkan tentang apa yang akan dikirim untuk merayakan ini.
Saya baru-baru ini mengetahui tentang paket ProjectElement.jl.
Aku sangat menyukainya. Ini menyediakan akses ke masalah yang disajikan di
Situs web Project Euler di Julia REPL.
Juga, saat membaca dokumentasi paket, itu
menyebutkan masalah yang belum pernah saya lihat sebelumnya. Karena itu
Saya berpikir untuk mengatasinya di posting ini.
Posting ini ditulis di bawah Julia 1.9.0-rc2, HiGHS v1.5.1,
Hongaria v0.7.0, JuMP v1.10.0, ProjectEuler v0.1.1.
Mari kita gunakan ProjectElement.jl untuk mendapatkan deskripsi
Masalah yang ingin kami selesaikan:
julia> import ProjectEuler
julia> ProjectEuler.question(345)
│ Source: The following problem is taken from Project Euler
│ Problem Title: Problem 345: Matrix Sum
│ Published On: Saturday, 3rd September 2011, 04:00 pm
│ Solved By: 5813
│ Difficulty Rating: 15%
Problem
≡≡≡≡≡≡≡≡≡≡
We define the Matrix Sum of a matrix as the maximum possible sum of matrix
elements such that none of the selected elements share the same row or column.
For example, the Matrix Sum of the matrix below equals
3315 ( = 863 + 383 + 343 + 959 + 767):
7 53 183 439 863
497 383 563 79 973
287 63 343 169 583
627 343 773 959 943
767 473 103 699 303
Find the Matrix Sum of:
7 53 183 439 863 497 383 563 79 973 287 63 343 169 583
627 343 773 959 943 767 473 103 699 303 957 703 583 639 913
447 283 463 29 23 487 463 993 119 883 327 493 423 159 743
217 623 3 399 853 407 103 983 89 463 290 516 212 462 350
960 376 682 962 300 780 486 502 912 800 250 346 172 812 350
870 456 192 162 593 473 915 45 989 873 823 965 425 329 803
973 965 905 919 133 673 665 235 509 613 673 815 165 992 326
322 148 972 962 286 255 941 541 265 323 925 281 601 95 973
445 721 11 525 473 65 511 164 138 672 18 428 154 448 848
414 456 310 312 798 104 566 520 302 248 694 976 430 392 198
184 829 373 181 631 101 969 613 840 740 778 458 284 760 390
821 461 843 513 17 901 711 993 293 157 274 94 192 156 574
34 124 4 878 450 476 712 914 838 669 875 299 823 329 699
815 559 813 459 522 788 168 586 966 232 308 833 251 631 107
813 883 451 509 615 77 281 613 459 205 380 274 302 35 805
Untuk memulainya, mari kita definisikan matriks yang memberikan spesifikasi masalah
dan mengaitkannya dengan M Mengubah:
M = [ 7 53 183 439 863 497 383 563 79 973 287 63 343 169 583
627 343 773 959 943 767 473 103 699 303 957 703 583 639 913
447 283 463 29 23 487 463 993 119 883 327 493 423 159 743
217 623 3 399 853 407 103 983 89 463 290 516 212 462 350
960 376 682 962 300 780 486 502 912 800 250 346 172 812 350
870 456 192 162 593 473 915 45 989 873 823 965 425 329 803
973 965 905 919 133 673 665 235 509 613 673 815 165 992 326
322 148 972 962 286 255 941 541 265 323 925 281 601 95 973
445 721 11 525 473 65 511 164 138 672 18 428 154 448 848
414 456 310 312 798 104 566 520 302 248 694 976 430 392 198
184 829 373 181 631 101 969 613 840 740 778 458 284 760 390
821 461 843 513 17 901 711 993 293 157 274 94 192 156 574
34 124 4 878 450 476 712 914 838 669 875 299 823 329 699
815 559 813 459 522 788 168 586 966 232 308 833 251 631 107
813 883 451 509 615 77 281 613 459 205 380 274 302 35 805]
Perhatikan bahwa ini dapat dengan mudah dilakukan di Julia REPL, dengan menyalin dan menempelkan teks
dari spesifikasi masalah dan hanya mengemasnya M = [ and ].
Untuk mengatasi masalah secara manual, mari berikan komentar berikut:
- Karena setiap kolom harus dipilih tepat sekali dikurangi
nilai yang sama dari setiap elemen beberapa kolom tidak berpengaruh
solusi (sama untuk baris). - Jika di setiap baris max elemen ada di kolom lain maka kita bisa
cukup pilih elemen maks ini di setiap baris dan item ini
adalah solusi untuk masalah kita.
Dengan menggunakan dua fakta ini, kami akan mencoba menyelesaikan masalah kami. Mari kita dulu
memeriksa bahwa dalam matriks asli kami M setiap baris memiliki kolom unik di dalamnya
memiliki nilai terbesar:
julia> findall(==(0), M .- maximum(M, dims=2))
15-element Vector{CartesianIndex{2}}:
CartesianIndex(15, 2)
CartesianIndex(2, 4)
CartesianIndex(5, 4)
CartesianIndex(11, 7)
CartesianIndex(3, 8)
CartesianIndex(4, 8)
CartesianIndex(12, 8)
CartesianIndex(13, 8)
CartesianIndex(6, 9)
CartesianIndex(14, 9)
CartesianIndex(1, 10)
CartesianIndex(10, 12)
CartesianIndex(7, 14)
CartesianIndex(8, 15)
CartesianIndex(9, 15)
Sayangnya, bukan itu masalahnya. Kita melihat bahwa misalnya baris 2 dan 5 memiliki
maksimum di kolom 4. Oleh karena itu, kita tidak bisa menyelesaikan masalah kita dengan sepele.
Namun, mari kita coba kurangi beberapa nilai dari kolom
matriks M berharap bahwa kita akan mendapatkan orisinalitas yang diinginkan.
Nilai yang kami kurangi dari setiap kolom adalah:
julia> sub = [55 0 23 56 40 0 101 171 175 62 53 151 0 0 26]
1×15 Matrix{Int64}:
55 0 23 56 40 0 101 171 175 62 53 151 0 0 26
Mari kita periksa:
julia> M2 = M .- sub
15×15 Matrix{Int64}:
-48 53 160 383 823 497 282 392 -96 911 234 -88 343 169 557
572 343 750 903 903 767 372 -68 524 241 904 552 583 639 887
392 283 440 -27 -17 487 362 822 -56 821 274 342 423 159 717
162 623 -20 343 813 407 2 812 -86 401 237 365 212 462 324
905 376 659 906 260 780 385 331 737 738 197 195 172 812 324
815 456 169 106 553 473 814 -126 814 811 770 814 425 329 777
918 965 882 863 93 673 564 64 334 551 620 664 165 992 300
267 148 949 906 246 255 840 370 90 261 872 130 601 95 947
390 721 -12 469 433 65 410 -7 -37 610 -35 277 154 448 822
359 456 287 256 758 104 465 349 127 186 641 825 430 392 172
129 829 350 125 591 101 868 442 665 678 725 307 284 760 364
766 461 820 457 -23 901 610 822 118 95 221 -57 192 156 548
-21 124 -19 822 410 476 611 743 663 607 822 148 823 329 673
760 559 790 403 482 788 67 415 791 170 255 682 251 631 81
758 883 428 453 575 77 180 442 284 143 327 123 302 35 779
julia> sol = findall(==(0), M2 .- maximum(M2, dims=2))
15-element Vector{CartesianIndex{2}}:
CartesianIndex(6, 1)
CartesianIndex(15, 2)
CartesianIndex(8, 3)
CartesianIndex(5, 4)
CartesianIndex(4, 5)
CartesianIndex(12, 6)
CartesianIndex(11, 7)
CartesianIndex(3, 8)
CartesianIndex(14, 9)
CartesianIndex(1, 10)
CartesianIndex(2, 11)
CartesianIndex(10, 12)
CartesianIndex(13, 13)
CartesianIndex(7, 14)
CartesianIndex(9, 15)
Sekarang kita melihat bahwa kita memiliki tepat satu nilai maksimum di setiap baris dan masing-masingnya
di kolom lain. Oleh karena itu, solusi untuk masalah tersebut dapat dihitung sebagai
(Saya tidak menunjukkan solusi untuk mendorong Anda mencoba menyelesaikan sendiri masalahnya):
Sekarang Anda mungkin bertanya bagaimana seseorang bisa mendapatkannya sub vektor?
Anda dapat menemukannya dengan coba-coba atau menggunakan cara yang lebih sistematis.
Menariknya, masalah yang kita hadapi hari ini adalah masalah penting
dalam riset operasi dan algoritma khusus telah dikembangkan untuk menyelesaikannya.
Algoritma yang dapat digunakan untuk menyelesaikan masalah seperti ini disebut
Algoritma Hungaria. Itu dibuat di Julia di Hungaria.jl
paket. Saya mendorong Anda untuk menelitinya, namun, izinkan saya menyebutkan bahwa itu digunakan
versi halus dari dua pengamatan yang kami lakukan saat mengembangkan panduan ini
larutan.
Paket ini sangat mudah digunakan. Anda hanya perlu mengingat bahwa secara default ini diminimalkan
jumlah, jadi kita perlu menggunakan -M matriks. Inilah cara Anda bisa mendapatkannya
solusi (saya tunjukkan indeksnya, tetapi bukan nilai solusinya):
julia> using Hungarian
julia> hungarian(-M)[1]
15-element Vector{Int64}:
10
11
8
5
4
1
14
3
15
12
7
6
13
9
2
Anda dapat bertanya bagaimana kami dapat memeriksa solusi manual kami dan mendapatkan solusi
Gunakan paket yang tepat. Anda dapat melakukan hal berikut:
julia> getindex.(sol, 1) == hungarian(-M')[1]
true
Semua pertandingan seperti yang diharapkan.
Perhatikan bahwa untuk pengujian saya menggunakan hungarian berfungsi dengan transpos
Nanti M matriks karena indeks kartesian kami diurutkan berdasarkan jumlah kolom
(alasannya karena Julia menggunakan urutan penyimpanan utama kolom) dan secara defaulthungarian mengembalikan indeks kolom yang diurutkan berdasarkan nomor baris.
Bagaimana jika kita tidak memiliki paket Hungaria.jl?
Dalam hal ini masalah dapat diselesaikan dengan pemrograman bilangan bulat campuran.
Saya memutuskan untuk menggunakan paket JuMP.jl dan HiGHS.jl untuk mendapatkan jawabannya
(seperti biasa – nilai solusi tidak ditampilkan):
using JuMP
import HiGHS
model = Model(HiGHS.Optimizer)
@variable(model, x[1:15, 1:15], Bin)
for i in 1:15
@constraint(model, sum(x[i, j] for j in 1:15) == 1)
@constraint(model, sum(x[j, i] for j in 1:15) == 1)
end
@objective(model, Max, sum(x[i, j] * M[i, j] for i in 1:15, j in 1:15))
optimize!(model)
value.(x)
Saya sangat menikmati menggunakan API JuMP.jl untuk menyelesaikan masalah pengoptimalan.
Seperti di atas, mari kita periksa apakah solusinya cocok dengan solusi yang kita peroleh secara manual:
julia> findall(>=(0.5), value.(x)) == sol
true
Perhatikan bahwa saya menggunakan 0.5 cangkir 0 dari 1 solusi karena ini adalah
nilai batas aman bahkan jika ada beberapa ketidakakuratan
solusi pengembalian.
Saya sangat menikmati memecahkan teka-teki Project Euler dengan Julia.
Sintaks dan ekosistem paket yang saya miliki membuatnya
cukup nyaman. Kode yang dihasilkan biasanya pendek dan mudah dibaca.
Jika Anda menyukai masalah ini, izinkan saya memberi Anda tantangan. Perhatikan itu
jumlah nilai yang kami kurangi dalam solusi manual adalah:
Tantangan bagi Anda adalah menemukan entri non-negatif seperti itu sub
memecahkan masalah kita saja (dalam pendekatan manual) dan
meminimalkan jumlah entri dari sub. Saya harap Anda akan menikmati pemecahannya
Teka-teki ekstra ini!
Terkait
Software Terbaru Saat Ini
Aplikasi yang sedang trend saat ini
object oriented programming, programming language, programming adalah, web programming, belajar programming, tournament software, software, software adalah, contoh software, apa itu software, pengertian software, aplikasi, aplikasi penghasil uang, aplikasi bokep, aplikasi video, programming
#Pertemuan #Hongaria #dengan #Euler #pada #ulang #tahun #ketiga
