Teka-teki grafik lainnya | juliablogger.com – Beragampengetahuan

Oleh: Blog Bogumił Kamiński

Repost dari:

Saya baru-baru ini menulis presentasi kuis
dapat diselesaikan dengan menggunakan analisis grafik. Saya mendapat umpan balik yang cukup bagus
dari pembaca saya dan salah satu dari mereka berbagi dengan saya hal menarik lainnya
Teka-teki dapat diselesaikan secara grafis.

Hari ini saya ingin membahas teka-teki ini. Seperti pada postingan baru-baru ini
Saya memecahkan masalah baik secara analitik maupun komputasi.

Posting ditulis di bawah Julia 1.9.2 dan Graphs.jl 1.8.0.

Masalah yang dibagikan teman saya kepada saya adalah sebagai berikut:

Tujuh orang A, B, C, E, F, G dan H mengunjungi orang D.
Setelah menyelidiki, mereka melaporkan bahwa mereka telah melihat
orang-orang berikut selama kunjungan mereka:

• A bertemu B, C, F, G;
• B bertemu A, C, E, F, H;
• C bertemu A, B, E;
• E bertemu B, C, F;
• F memenuhi A, B, E, H;
• G memenuhi A dan H;
• H bertemu B, F, dan G.

Nah, yang menarik, mereka semua juga melaporkan itu semua
mereka hanya mengunjungi D sekali dalam jangka waktu yang terus menerus.
Pertanyaannya adalah:

1. Buktikan bahwa ini tidak mungkin,
   yaitu satu pengunjung harus membuat beberapa kali.
2. Tunjukkan bahwa cukup untuk mengasumsikan itu
   seseorang telah mengunjungi D beberapa kali dan mengidentifikasi orang ini.

Pertama, perhatikan bahwa jawaban tentang siapa melihat siapa konsisten
dari semua orang yang melaporkan.
Kita dapat memvisualisasikannya menggunakan bagan berikut:

Untuk memulai, mari pikirkan mengapa setiap orang tidak dapat mengunjungi D hanya sekali.
Pertimbangkan turis A, B, H, dan G. Kita lihat A dan H belum pernah bertemu.
Artinya, periode kunjungan mereka tidak terus-menerus. Karena B dan G
keduanya melihat A dan H, lalu menganggap mereka hanya berkunjung sekali,
keduanya harus ada antara kunjungan A dan H.
Tapi ini berarti selama waktu itu B dan H akan bertemu,
bukan itu masalahnya.
Oleh karena itu, setidaknya satu orang harus mengunjungi D lebih dari satu kali.

Kami perhatikan bahwa kami memiliki masalah karena kami memiliki siklus dengan panjang 4 dalam grafik,
yaitu ABGH, yang tidak mengandung siklus yang lebih pendek di dalamnya
(yaitu sisi yang menghubungkan A dan H atau B dan G). Dengan penalaran
kami telah menyajikan di atas semua siklus seperti itu akan bermasalah. Ada tiga seperti itu
Siklus: ABGH, AGHF, ACEF. Kami menemukan itu di semua siklus ini
A hadir dan ini adalah satu-satunya yang biasanya ada di semuanya.
Ini berarti bahwa:

• menghapus A dari grafik (yaitu dengan asumsi bahwa A telah mengunjungi D berkali-kali) bisa
  penyelesaian masalah;
• menghapus tombol lain tidak akan menyelesaikan masalah.

Jadi, untuk menyelesaikan teka-teki tersebut, kita perlu menunjukkan bahwa jika kita menghilangkan A dari
mengingat semua yang lain benar-benar hanya bisa berkunjung sekali D. Seperti itu
solusi dapat ditemukan relatif cepat secara manual, misalnya:

• B tiba;
• C ke;
• E datang;
• daun C;
• F ke;
• kertas timah elektronik;
• H tiba;
• daun B;
• F daun;
• G ke;
• daun G;
• Daun H.

Solusinya tidak lama, tetapi membutuhkan pemikiran.
Sekarang kita memecahkan teka-teki dengan perhitungan brute force.

Mulailah dengan menentukan bagan yang akan kita kerjakan:

using Graphs
g = SimpleGraph(7)
add_edge!(g, 1, 2)
add_edge!(g, 1, 3)
add_edge!(g, 1, 5)
add_edge!(g, 1, 6)
add_edge!(g, 2, 3)
add_edge!(g, 2, 4)
add_edge!(g, 2, 5)
add_edge!(g, 2, 7)
add_edge!(g, 3, 4)
add_edge!(g, 4, 5)
add_edge!(g, 5, 7)
add_edge!(g, 6, 7)

Perhatikan bahwa saya memetakan orang ke angka, A ke 1, B ke 2, C ke 3, E ke 4, F ke 5, G ke 6, H ke 7.

Sekarang, tentukan fungsi yang memeriksa apakah setiap orang hanya memiliki satu akses untuk menyelesaikan grafik.

Logika kodenya adalah sebagai berikut. Jika kita n orang, kita bisa, tanpa kehilangan kesamaan,
misalkan mereka datang atau pergi dalam waktu 1, 2, …, 2n-1, 2n, dimana pada waktu tertentu
hanya satu peristiwa (kedatangan atau keberangkatan beberapa orang) yang terjadi.
Kami akan memeriksa semua kemungkinan pencarian
orang dalam waktu berpasangan (berpasangan, karena seseorang datang dan pergi dalam dua waktu yang berbeda).
Tes ini dilakukan secara iteratif:

• kami mencoba menambahkan orang berikutnya (mulai dari yang pertama dan diakhiri dengan yang terakhir);
• kami memeriksa semua kemungkinan garis waktu Paris masih kosong oleh mereka yang telah ditunjuk;
• untuk setiap pasangan, kami memeriksa apakah penetapan ini cocok dengan batasan yang ditentukan oleh grafik.

Saya menerapkan prosedur ini secara rekursif menggunakan pencarian mendalam-pertama. Itu find_assignment
fungsi melakukan opsi penelusuran. Dibutuhkan tiga argumen:

• g adalah grafik kendala (siapa melihat siapa);
• v adalah vektor dengan panjang 2n yang berisi informasi yang sudah dimiliki pengunjung
  dialokasikan waktu kedatangan dan keberangkatan (0 tunjukkan titik bebas)
• level adalah informasi tentang jumlah pengunjung yang sedang kami ulas.

Itu check_g_v tes menambahkan orang tertentu (dengan level nomor) pada saat-saat yang ditunjukkan oleh
itu v vektor yang cocok dengan informasi yang diberikan dalam grafik g.

Kode ini adalah sebagai berikut:

function check_g_v(g, v, level)
    lev_v = findall(==(level), v)
    for i in 1:level-1 # need to check only against previous visitors
        lev_i = findall(==(i), v)
        if has_edge(g, i, level)
            if lev_v[2] < lev_i[1] || lev_v[1] > lev_i[2]
                return false
            end
        else
            if !(lev_v[2] < lev_i[1] || lev_v[1] > lev_i[2])
                return false
            end
        end
    end
    return true
end

function find_assignment(g, level=1, v=zeros(Int, 2*nv(g)))
    n = nv(g)
    if level == n # we check last person
        loc = findall(==(0), v) # no choice of free spots
        @assert length(loc) == 2
        v[loc] .= n
        if check_g_v(g, v, level)
            @info "Graph is good! Solution $v"
            return true # signal success up the recursion
        end
        v[loc] .= 0 # clean up on failure
    else
        for i in 1:2*n-1 # i indicates arrival time
            v[i] == 0 || continue
            v[i] = level
            for j in i+1:2*n # j indicates departure time
                v[j] == 0 || continue
                v[j] = level
                if check_g_v(g, v, level)
                    if find_assignment(g, level+1, v)
                        return true # signal success up the recursion
                    end
                end
                v[j] = 0 # clean up on failure
            end
            v[i] = 0 # clean up on failure
        end
    end
    if level == 1 # all attempts to find good allocations failed
        @info "Graph is not good!"
    end
    return false # signal failure up the recursion
end

Kita dapat menggunakannya untuk memeriksa apakah grafik aslinya mungkin:

julia> find_assignment(g);
[ Info: Graph is not good!

As we already knew – the graph is not good and the computational
procedure confirmed it.

How can we check graphs when we would remove one of the persons from it?
It is easy with Graphs.jl, as we can just subset our graph
by removing some node from it. Let us see:

julia> for i in 1:nv(g)
           @info "removing $i"
           find_assignment(g[[1:i-1; i+1:7]]) akhir
[ Info: removing 1
[ Info: Graph is good! Solution [1, 2, 3, 2, 4, 3, 6, 1, 4, 5, 5, 6]
[ Info: removing 2
[ Info: Graph is not good!
[ Info: removing 3
[ Info: Graph is not good!
[ Info: removing 4
[ Info: Graph is not good!
[ Info: removing 5
[ Info: Graph is not good!
[ Info: removing 6
[ Info: Graph is not good!
[ Info: removing 7
[ Info: Graph is not good!

As we can see indeed removing node 1 (representing person A) solves the problem
and this is the only solution.

Let us do the mapping of numbers to letters to make the solution more readable.
Note that since we removed node 1 (corresponding to person A)
from the graph numbers of all nodes got decreased by 1.
This can be done by comprehension or by broadcasting (I show both approaches
for a reference):

julia> mapping = ["B", "C", "E", "F", "G", "H"]



vektor 6 elemen{String}: "B" "C" "E" "F" "G" "H" julia> [mapping[i] berikan aku [1, 2, 3, 2, 4, 3, 6, 1, 4, 5, 5, 6]]12 elemen vektor{String}: "B" "C" "E" "C" "F" "E" "H" "B" "F" "G" "G" "H" julia> getindex.( Referensi (pemetaan), [1, 2, 3, 2, 4, 3, 6, 1, 4, 5, 5, 6]) 12 elemen vektor{String}: "B" "C" "E" "C" "F" "E" "H" "B" "F" "G" "G" "H"

Memang, ini adalah urutan yang kami miliki dalam solusi analitik.

Saya harap Anda menemukan teka-teki ini dan solusi yang menarik.

Minggu depan saya akan memposting tentang fitur-fitur yang diperkenalkan di
rilis 1.6 dari DataFrames.jl yang kami kerjakan baru-baru ini.

Terkait