Teka-teki wawancara tentang perjalanan di segmen garis

10

Pada garis bilangan panjang M, di mana 0 < M <= 1,000,000,000, Anda memberikan N( 1 < N <= 100,000) pasangan bilangan bulat poin. Dalam setiap pasangan, titik pertama mewakili di mana objek saat ini berada, dan titik kedua mewakili di mana objek harus dipindahkan. (Perlu diingat secondpoinnya mungkin lebih kecil dari first).

Sekarang, anggap Anda mulai dari titik 0dan memiliki gerobak yang dapat menampung 1objek. Anda ingin memindahkan semua objek dari posisi awal mereka ke posisi akhir masing-masing saat menempuh jarak paling sedikit di sepanjang garis angka ( bukan perpindahan). Anda harus tepat sasaran M.

Sekarang, saya sudah mencoba untuk mengurangi masalah ini menjadi masalah yang lebih sederhana. Sejujurnya aku bahkan tidak bisa memikirkan solusi brute force ( mungkin serakah). Namun, pemikiran pertama saya adalah untuk merosotkan gerakan mundur ke dua gerakan maju, tetapi itu tampaknya tidak berhasil dalam semua kasus.

Saya membuat 3contoh kasus uji ini di sini:http://i.stack.imgur.com/zRv4Q.png

Jawaban untuk testcase pertama adalah 12. Pertama, Anda mengambil reditem di titik 0. Kemudian Anda pindah ke titik 6(jarak = 6), jatuhkan reditem sementara, lalu ambil greenitem. Kemudian Anda pindah ke titik 5(jarak = 1) dan menjatuhkan greenitem. Kemudian Anda kembali ke titik 6(jarak = 1) dan mengambil reditem yang Anda jatuhkan, pindah ke titik 9 (jarak = 3), lalu pindah ke titik 10(jarak = 1) untuk menyelesaikan urutan.

Total jarak yang ditempuh adalah 6 + 1 + 1 + 3 + 1 = 12, yang merupakan jarak minimum yang memungkinkan.

Dua kasus lain punya jawaban 12, saya yakin. Namun, saya tidak dapat menemukan aturan umum untuk menyelesaikannya.

Ada yang punya ide?

David
sumber
Jika saya tidak salah, tidakkah Anda memerlukan struktur data untuk menghitung "tumpang tindih"? Kalau tidak, saya menyelesaikannya dengan cara yang salah.
david
Anda masih dapat menandai dan jika mod setuju ia akan membuka kembali dan bermigrasi
ratchet freak
Kami dapat memindahkan pertanyaan antar situs secara otomatis (bahkan jika ditutup), jangan lintas pos. Sebagai gantinya, ikuti saran @ ratchetfreak, beri tanda untuk perhatian moderat dan minta pertanyaan untuk dimigrasi.
yannis
1
Ini terdengar sangat aneh, tetapi bagaimana jika Anda mulai dengan bergerak ke kanan sampai Anda menabrak sepotong kargo. Setelah Anda menabrak kargo itu, jatuhkan apa pun yang Anda bawa, ambil kargo itu, dan lanjutkan untuk menempatkannya di tempat yang tepat. Jika Anda menabrak sepotong kargo lain yang perlu dipindahkan, jatuhkan arus, ambil, dan tangani. Ketika Anda tidak memiliki kargo, ke kanan.
supersam654
1
Apakah objek ada di semua titik atau hanya yang diberikan? Apakah mungkin untuk memiliki banyak objek di lokasi tertentu? Apakah diizinkan untuk sementara waktu meletakkan objek di lokasi selain yang terakhir?
Sean McSomething

Jawaban:

4
  1. Jika Anda kosong, mulailah bergerak ke kanan.

  2. Setiap kali Anda mencapai objek dan Anda kosong, ambil (duh) dan bergerak menuju tujuannya.

  3. Setiap kali Anda mencapai suatu objek adan Anda sudah membawa b, selalu pilih objek mana yang memiliki tujuan terkecil secara numerik (paling jauh ke kiri).

  4. Jika Anda belum berada di M, kembali ke langkah 1.

Ini optimal: Satu-satunya tempat di mana Anda memiliki pilihan nyata adalah dalam langkah 3. Menangani tujuan paling kiri terlebih dahulu memastikan bahwa pada saat Anda mengirim kedua objek, Anda akan sejauh mungkin ke kanan.

Mengapa pertanyaan ini ada di programmers.sx? Ya, "pertanyaan wawancara", tapi itu hanya teka-teki yang bagus.

PS. Dalam hal implementasi, yang Anda butuhkan adalah daftar tugas (pasangan integer poin) yang diurutkan berdasarkan posisi awal.

Alexis
sumber
1

Misalkan Anda diberikan gerakan ini (a, b), (c, d), (e, f), ...maka jarak minimum yang harus Anda tempuh adalah abs(b - a) + abs(d - c) + abs(f - e) + ...dan jarak sebenarnya yang Anda tempuh abs(b - a) + abs(c - b) + abs(d - c) + abs(e - d) + ....
Pada dasarnya, diberikan array gerakan, intinya adalah untuk meminimalkan fungsi "jarak perjalanan" dengan menukar elemen di sekitarnya. Jika Anda menganggap kombinasi tertentu sebagai simpul dan semua kombinasi yang dapat Anda capai darinya sebagai tepian, Anda dapat menggunakan salah satu dari banyak algoritma pencarian grafik yang memanfaatkan heuristik. Salah satu contohnya adalah pencarian balok .

Beruang hitam
sumber
0

Mungkin saya salah memahami masalah tetapi bagaimana dengan yang berikut ini:

  1. Urutkan pasangan dengan nomor pertama dari pasangan yang merupakan lokasi saat ini
  2. Pindahkan sepanjang elemen swapping baris ke lokasi yang tepat (Anda memiliki variabel temp)

Fakta bahwa itu diurutkan menjamin bahwa Anda tidak bolak-balik elemen untuk menempatkan mereka di lokasi yang tepat (terlepas dari apakah garis tersebut diwakili sebagai array atau daftar)

Perbarui setelah komentar @templatetypedef:
Gunakan a HashTableuntuk menyimpan semua pasangan. Gunakan lokasi saat ini dari setiap pasangan sebagai kunci indeks.
Gunakan indeks kedua di atas pasangan.

 1. Get next pair according to index from the line.
 2. If current pair exists in hashtable then place element to its target location.  
    2.a Remove pair from hashtable.  
    2.b Make current pair the target location. Then go to step 1  
 ELSE 
        Increment current index until you get a pair present in the hashtable. Go to step 2  
pengguna10326
sumber
Anda hanya dapat memindahkan satu unit pada satu waktu, saya pikir berkali-kali Anda harus menelusuri jalan Anda
david
Saya tidak benar-benar mengikuti Anda. Tampaknya persyaratannya hanya untuk bergerak maju dan bertukar angka. Anda sudah tahu lokasi saat ini dan lokasi target. Hanya menukar mereka (menggunakan variabel keranjang seperti yang Anda katakan) dan pindah ke pasangan berikutnya
user10326
Pertimbangkan contoh tandingan ini: (1, 10), (10, 1), (2, 3), (3, 4). Cara optimal untuk melakukan ini adalah dengan membawa objek 1 ke posisi 10, kemudian mengambil objek di posisi 10 dan membawanya ke posisi 1, kemudian membawa 2 ke 3 dan 3 ke 4. Melakukan hal ini dalam penyortiran urutan posisi awal akan membawa 1 ke 10, lalu kembali semua jalan ke awal untuk membawa 2 ke 3, 3 ke 4, kemudian pergi sampai ke ujung untuk mengambil 10 dan membawa kembali.
templatetypedef
@templatetypedef: Saya mengerti maksud Anda. Jawaban yang
diperbarui
Dalam jawaban Anda yang diperbarui, apakah "indeks saat ini" hanya mengindikasikan posisi saat ini?
david
0

Kecenderungan saya pada suatu algoritma yang pada dasarnya serakah:

Buat daftar poin yang perlu dipindahkan. Karena mengoptimalkan ini bukan bagian dari masalah yang diperlukan, saya tidak akan khawatir mengaturnya.

while !Done
    if CartIsEmpty()
        FindClosestObjectToMove()
        MoveToObject()
       LoadCart()
    else
        Destination = Cart.Contains.Target
        CurrentMove = [Location, Destination]
        SubList = List.Where(Move.Within(CurrentMove))
        if !SubList.Empty
            Destination = SubList.FindSmallest(Location, Move.Origin)
        MoveTo(Destination)
        if !Destination.Empty
            SwapCart()
            UpdateTaskList()
        else
            EmptyCart()
            DeleteTask()

Saya pikir ini mencakup semua kasus. Dalam arti itu rekursif tetapi melalui memperbarui daftar itu daripada memanggil dirinya sendiri.

Loren Pechtel
sumber
Terima kasih atas jawabannya. Bisakah Anda jelaskan Destination = SubList.FindSmallest(Location, Move.Origin)? Apa yang Move.Origindiwakili?
david
Move.Origin adalah lokasi di mana objek yang akan dipindahkan saat ini - asalnya. Pada dasarnya, ketika melihat suatu gerakan terlebih dahulu lakukan gerakan yang lebih kecil yang terkandung dalam rentang itu.
Loren Pechtel
-1

Ini adalah masalah salesman keliling yang asimetris . Anda dapat menganggap ini sebagai grafik. Tepi akan menjadi masing-masing (mulai, selesai) pasangan, satu untuk setiap (0, mulai), dan semua pasangan lainnya (selesai, mulai).

Dengan asumsi NP! = P, itu akan memiliki waktu berjalan yang diharapkan eksponensial.

MSN
sumber
3
Saya tidak yakin itu benar. Ini adalah kasus khusus TSP asimetris, sehingga mungkin memiliki solusi waktu polinomial.
templatetypedef
Tidakkah Anda membutuhkan tepi seperti (selesai, M), di mana Mtitik akhir dari garis bilangan?
david
Juga, algoritma eksponensial terlalu lambat, karena Nbisa 100.000.
david
Untuk mendukung pernyataan ini, mungkin Anda memiliki metode untuk mengubah setiap masalah salesman keliling yang asimetris menjadi masalah yang setara dengan deskripsi ini?
dan_waterworth
1
Itu tidak setara. Penjual keliling harus mengunjungi semua simpul grafik. Formulasi Anda mengharuskan dia untuk mengunjungi semua sisi.
alexis