Cara memperlambat pemabuk dalam perjalanan pulang

15

Pertimbangkan kotak dengan grafik kotak yang terlihat seperti ini.

grafik kotak

Penting untuk diperhatikan bahwa grafik ini adalah 11 oleh 11 .

Pada titik tertentu, seorang pria berdiri di persimpangan dan dia hanya pernah bergerak secara vertikal atau horizontal satu langkah pada satu waktu ke persimpangan berikutnya. Sayangnya dia terlalu banyak minum sehingga dia memilih arah yang dia bergerak secara acak dari hingga 4 kemungkinan arah (atas, bawah, kiri, kanan). Ini hingga 4 seolah-olah dia berdiri di dinding dia hanya memiliki 3 pilihan saja dan di sudut dia hanya memiliki 2.

Dia mulai di sudut kiri bawah dan tujuannya adalah untuk pulang yang merupakan sudut kanan atas. Waktu hanyalah jumlah langkah yang dibutuhkannya.

Namun, Anda adalah musuh jahat yang ingin dia pulang selambat mungkin. Anda dapat menghapus sejumlah tepi dari grafik kapan saja selama perjalanannya. Satu-satunya batasan adalah bahwa Anda harus selalu meninggalkan beberapa cara baginya untuk pulang dan Anda tidak dapat menghapus tepi yang telah ia gunakan.

Tantangannya adalah untuk merancang musuh yang jahat sebanyak mungkin dan kemudian mengujinya pada grafik 100 x 100 20 x 20 dengan walker mabuk secara acak. Skor Anda hanyalah waktu rata-rata yang dibutuhkan walker acak untuk pulang lebih dari 10 1000 kali jalan.

Anda dapat menggunakan bahasa dan perpustakaan apa saja yang Anda suka asalkan tersedia secara bebas dan mudah diinstal di Linux.

Apa yang perlu saya terapkan?

Anda harus menerapkan kode untuk walker acak dan juga untuk musuh dan kode harus digabungkan sehingga output saat dijalankan hanyalah rata-rata 1000 berjalan menggunakan kode musuh Anda. Kode walker acak harus sangat sederhana untuk ditulis karena ia hanya memilih dari (x-1, y), (x + 1, y), (x, y-1), dan (x, y + 1) memastikan bahwa tidak ada yang telah dihapus atau berada di luar jangkauan.

Kode musuh tentu saja lebih sulit dan juga perlu mengingat sisi-sisi pemabuk yang telah dilalui sehingga ia tidak mencoba untuk menghapus salah satu dari mereka dan untuk memastikan masih ada rute pulang ke pemabuk, yang sedikit rumit harus dilakukan dengan cepat.

Adendum 10 lari tidak cukup tetapi saya tidak ingin menghukum orang yang berhasil berjalan sangat lama. Saya sekarang telah meningkatkannya menjadi 1000 karena permintaan populer. Namun, jika perjalanan Anda begitu lama sehingga Anda tidak dapat melakukan 1000 lari dalam jumlah waktu yang realistis, harap laporkan saja untuk jumlah lari maksimum yang Anda bisa.

Tabel skor tinggi untuk 100 oleh 100.

  • 976124.754 oleh Optimizer.
  • 103000363.218 oleh Peter Taylor.

Sunting 1. Mengubah ukuran grafik menjadi 20 dengan 20 untuk membantu waktu pengujian orang berjalan. Saya akan membuat skor tabel tinggi baru untuk ukuran itu ketika orang mengirimkan skor.

Tabel skor tinggi untuk 20 dengan 20.

230,794.38 (100k runs) by justhalf
227,934 by Sparr 
213,000 (approx) by Peter Taylor
199,094.3 by stokastic
188,000 (approx) by James_pic
 64,281 by Geobits
code-challenge graph-theory
sumber
2
Saya tidak mengerti; tidak bisakah Anda menghapus semua tepi di awal kecuali yang membentuk jalur terpanjang?
Peter Olson
3
Saya tidak melihat aturan yang menunjukkan bahwa pemabuk tidak dapat berjalan kembali di tepi yang sama dua kali. Jika ia dapat mengambil jalur yang sama antara dua titik dua kali, dan memilih belokan secara acak, maka secara logika bukankah grafik dengan rata-rata terpanjang (acak) melintasi yang paling ujung? Yaitu, bukankah grafik optimal (terpanjang) adalah grafik tanpa tepi yang dihapus?
milinon
3
Saya bukan penggemar yang mengharuskan setiap entri untuk menemukan kembali roda (walker). Jika seseorang memposting test harness / framework maka saya akan membesarkan mereka dan menggunakannya.
Sparr
1
Keuntungan dari menghapus bagian dari jalan untuk membuatnya kembali untuk menempuh jalan yang panjang benar-benar hilang ketika jalannya acak; seharusnya sama kemungkinannya bahwa ia akan kembali pada suatu titik tanpa perlu Anda menghilangkan kelebihan. Saya ingin melihat beberapa data uji yang menunjukkan waktu rata-rata tanpa tepi dihilangkan, dan kemudian dengan tepi tertentu dihapus seperti yang Anda sarankan. Sejauh tantangan ini, saya pikir akan jauh lebih menarik jika jalur pemabuk itu deterministik.
milinon
3
10 putaran hampir tidak cukup. Bahkan dengan labirin 10x10 statis, apalagi musuh yang cerdas dan labirin 100x100, standar deviasi adalah sekitar 50% dari kasus rata-rata. Saya menjalankan 10.000 putaran dan saya masih tidak akan mempertimbangkan hasil perbandingan yang layak.
Sparr

Jawaban:

10

230.794,38 pada 20x20, 100rb berjalan

Pembaruan Terbaru: Saya akhirnya membangun solusi 2-path dinamis yang sempurna. Saya mengatakan sempurna karena versi sebelumnya sebenarnya tidak simetris, lebih mudah untuk mendapatkan jalur yang lebih panjang jika pemabuk mengambil satu jalur di atas yang lain. Yang saat ini simetris, sehingga bisa mendapatkan jumlah langkah yang diharapkan lebih tinggi. Setelah beberapa uji coba, tampaknya sekitar 230rb, peningkatan dari yang sebelumnya sekitar 228rb. Tetapi secara statistik angka-angka itu masih dalam penyimpangan besar mereka, jadi saya tidak mengklaim bahwa ini secara signifikan lebih baik, tetapi saya percaya ini harus lebih baik daripada versi sebelumnya.

Kode di bagian bawah posting ini. Ini diperbarui sehingga jauh lebih cepat daripada versi sebelumnya, menyelesaikan 1000 berjalan dalam 23 detik.

Di bawah ini adalah contoh dijalankan dan sampel labirin:

Walker Sempurna
Rata-rata: 230794.384
Maks: 1514506
Min: 25860
Selesai dalam 2317.374s
 _ _ _ _ _ _ _ _ _ _ _ _. 
| | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | _ _ _ _ |
| | | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | _ _ _ _ |
| | | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | _ _ _ _ |
| | | | | | | | | | | | | | _ | | _ _ _ _  
| | | | | | | | | | | | | _ _ _ _ _ _ |
| | | | | | | | | | | | | | _ _ _ _ _ _  
| | | | | | | | | | | | | _ _ _ _ _ _ |
| | | | | | | | | | | | | | _ _ _ _ _ _  
| | | | | | | | | | | | | _ _ _ _ _ _ |
| | | | | | _ | | _ | | _ | | _ | | _ _ _ _ _ _  
| | | | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | | | | | _ _ _ _ _ _ _ _ _ _ _ _ _  
| | | | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ | | _ | | _ _ _ _ _ _ _ _ _ _ _ _ _  
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Kiriman sebelumnya

Akhirnya saya bisa mencocokkan hasil Sparr! = D

Berdasarkan percobaan saya sebelumnya (lihat bagian bawah posting ini), strategi terbaik adalah memiliki jalur ganda dan menutup satu ketika pemabuk mencapai salah satu dari mereka, dan variabel berasal dari seberapa baik kita dapat secara dinamis memprediksi ke mana pemabuk akan pergi ke tingkatkan peluang dia masuk ke jalur yang lebih panjang.

Jadi berdasarkan DOUBLE_PATHstrategi saya , saya membangun yang lain, yang mengubah labirin ( DOUBLE_PATHlabirin saya mudah dimodifikasi) tergantung pada gerakan pemabuk. Ketika ia mengambil jalan dengan lebih dari satu opsi yang tersedia, saya akan menutup jalan sehingga hanya menyisakan dua opsi yang mungkin (satu dari mana ia datang, yang lain yang tidak terurai).

Ini terdengar mirip dengan apa yang telah dicapai Sparr, seperti yang ditunjukkan hasilnya. Perbedaannya dengan dia terlalu kecil untuk dianggap lebih baik, tetapi saya akan mengatakan bahwa pendekatan saya lebih dinamis daripada dia, karena labirin saya lebih dapat dimodifikasi daripada Sparr's =)

Hasil dengan labirin akhir sampel:

EXTREME_DOUBLE_PATH
Rata-rata: 228034.89
Maks: 1050816
Min: 34170
Selesai dalam 396.728s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ | | _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Bagian Eksperimen

Yang terbaik ternyata menjadi strategi yang sama dengan stokastic, saya bangga bereksperimen menggunakan berbagai strategi dan mencetak output yang bagus :)

Masing-masing labirin tercetak di bawah adalah labirin terakhir setelah pemabuk mencapai rumah, sehingga mereka mungkin sedikit berbeda dari berlari untuk berlari karena keacakan dalam gerakan pemabuk dan dinamika musuh.

Saya akan menjelaskan setiap strategi:

Jalur Tunggal

Ini adalah pendekatan paling sederhana, yang akan membuat satu jalur dari entri ke keluar.

SINGLE_PATH
Rata-rata: 162621.612
Maks: 956694
Min: 14838
Selesai dalam 149,430-an
 _ _ _ _ _ _ _ _ _ _
| | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Pulau (level 0)

Ini adalah pendekatan yang mencoba menjebak pemabuk di pulau yang hampir terisolasi. Tidak berfungsi sebaik yang saya harapkan, tetapi ini adalah salah satu ide pertama saya, jadi saya memasukkannya.

Ada dua jalan menuju ke pintu keluar, dan ketika si pemabuk mendekati salah satu dari mereka, musuh menutupnya, memaksanya untuk menemukan jalan keluar yang lain (dan mungkin terjebak lagi di pulau itu)

PULAU
Rata-rata: 74626.070
Maks: 428560
Min: 1528
Selesai dalam 122.512s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _   
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Jalan Ganda

Ini adalah strategi yang paling banyak dibahas, yaitu memiliki dua jalur panjang yang sama ke pintu keluar, dan tutup salah satunya saat pemabuk mendekati salah satunya.

DOUBLE_PATH
Rata-rata: 197743.472
Maks: 1443406
Min: 21516
Selesai dalam 308.177s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Pulau (level 1)

Terinspirasi oleh beberapa jalur pulau dan jumlah langkah jalan tinggi dalam jalur tunggal, kami menghubungkan pulau ke pintu keluar dan membuat jalur tunggal labirin di pulau itu, menciptakan total tiga jalur untuk keluar, dan mirip dengan kasus sebelumnya, tutup semua keluar saat pemabuk mendekat.

Ini bekerja sedikit lebih baik daripada jalur tunggal murni, tetapi masih tidak mengalahkan jalur ganda.

PULAU
Rata-rata: 166265.132
Maks: 1162966
Min: 19544
Selesai dalam 471.982s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ | _
| | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | |  
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |

Pulau (level 2)

Mencoba untuk memperluas ide sebelumnya, saya membuat pulau bersarang, menciptakan total lima jalur, tetapi tampaknya tidak berhasil dengan baik.

PULAU
Rata-rata: 164222.712
Maks: 927608
Min: 22024
Selesai dalam 793.591s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _
| | _ _ _ _ _ _ _ _ | _ |  
| | | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | | |
| _ | _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Pulau (level 3)

Memperhatikan bahwa jalur ganda sebenarnya bekerja lebih baik daripada jalur tunggal, mari kita buat pulau di jalur ganda!

Hasilnya adalah peningkatan di atas Pulau (level 1), tetapi masih belum mengalahkan jalur ganda murni.

Sebagai perbandingan, hasil untuk jalur ganda ukuran pulau adalah 131.134,42 bergerak rata-rata. Jadi ini menambah jumlah gerakan yang cukup signifikan (sekitar 40k), tetapi tidak cukup untuk mengalahkan jalur ganda.

PULAU
Rata-rata: 171730.090
Maks: 769080
Min: 29760
Selesai dalam 587.646s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |  
| _ _ _ _ _ _ _ _ | | | _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | | _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | | _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | | _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | | _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | | _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | | _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | | _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |

Pulau (level 4)

Sekali lagi, bereksperimen dengan pulau bersarang, dan sekali lagi itu tidak berfungsi dengan baik.

PULAU
Rata-rata: 149723.068
Maks: 622106
Min: 25752
Selesai dalam 830.889s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _    
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _ |  
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | | |
| | _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Kesimpulan

Secara keseluruhan, ini membuktikan bahwa memiliki jalur panjang tunggal dari posisi pemabuk saat ini ke jalan keluar paling baik, yang dicapai oleh strategi jalur ganda, karena setelah menutup jalan keluar, pemabuk harus menempuh jarak maksimum yang mungkin untuk sampai ke keluar.

Ini lebih lanjut mengisyaratkan bahwa strategi dasar masih harus berupa jalur ganda, dan kita hanya dapat memodifikasi seberapa dinamis jalur tersebut dibuat, yang telah dilakukan oleh Sparr. Jadi saya percaya strateginya adalah cara untuk pergi!

Kode

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.TreeSet;

public class Walker {

    enum Strategy{
        SINGLE_PATH,
        ISLAND,
        DOUBLE_PATH,
        EXTREME_DOUBLE_PATH,
        PERFECT_DOUBLE_PATH,
    }

    int width,height;
    int x,y; //walker's position
    int dX,dY; //destination
    Point[][] points;
    int stepCount = 0;

    public static void main(String[]args){
        int side = 20;
//      runOnce(side, Strategy.EXTREME_DOUBLE_PATH, 0);
        runOnce(side, Strategy.PERFECT_DOUBLE_PATH, 0);
//      for(Strategy strategy: Strategy.values()){
//          runOnce(side, strategy, 0);
//      }
//      runOnce(side, Strategy.ISLAND, 1);
//      runOnce(side, Strategy.ISLAND, 2);
//      Scanner scanner = new Scanner(System.in);
//      System.out.println("Enter side, strategy (SINGLE_PATH, ISLAND, DOUBLE_PATH, EXTREME_DOUBLE_PATH), and level:");
//      while(scanner.hasNext()){
//          side = scanner.nextInt();
//          Strategy strategy = Strategy.valueOf(scanner.next());
//          int level = scanner.nextInt();
//          scanner.nextLine();
//          runOnce(side, strategy, level);
//          System.out.println("Enter side, strategy (SINGLE_PATH, ISLAND, DOUBLE_PATH, EXTREME_DOUBLE_PATH), and level:");
//      }
//      scanner.close();
    }

    private static Walker runOnce(int side, Strategy strategy, int level) {
        Walker walker = null;
        long total = 0;
        int max = 0;
        int min = Integer.MAX_VALUE;
        double count = 1000;
        long start = System.currentTimeMillis();
        for(int i=0; i<count; i++){
            walker = new Walker(0,0,side,side,side-1,side-1, strategy, level, false);
            total += walker.stepCount;
            max = Math.max(walker.stepCount, max);
            min = Math.min(walker.stepCount, min);
//          System.out.println("Iteration "+i+": "+walker.stepCount);
        }
        System.out.printf("%s\nAverage: %.3f\nMax: %d\nMin:%d\n",strategy, total/count, max, min);
        System.out.printf("Completed in %.3fs\n", (System.currentTimeMillis()-start)/1000.0);
        walker.printPath();
        return walker;
    }

    private void createIsland(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY+1; i<topRightY; i++){
            if(i>botLeftY+1) deletePath(points[botLeftX][i].right());
            if(i<topRightY-1) deletePath(points[topRightX][i].left());
        }
        for(int i=botLeftX+1; i<topRightX; i++){
            if(i>botLeftX+1) deletePath(points[i][botLeftY].up());
            if(i<topRightX-1) deletePath(points[i][topRightY].down());
        }
    }

    private void createSinglePath(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY; i<topRightY; i++){
            if(i==topRightY-1 && (topRightY+1-botLeftY)%2==0){
                for(int j=botLeftX; j<topRightX; j++){
                    if(j==topRightX-1 && (j-botLeftX)%2==0){
                        deletePath(points[topRightX][topRightY].down());
                    } else {
                        deletePath(points[j][topRightY-1+((j-botLeftX)%2)].right());
                    }
                }
            } else {
                for(int j=botLeftX+(i-botLeftY)%2; j<topRightX+((i-botLeftY)%2); j++){
                    deletePath(points[j][i].up());
                }
            }
        }
    }

    private void createDoublePath(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY; i<topRightY; i++){
            if(i>botLeftY && (width%4!=1 || i<topRightY-1)) deletePath(points[width/2-1][i].right());
            if(i==topRightY-1 && (topRightY+1-botLeftY)%2==1){
                for(int j=botLeftX; j<topRightX; j++){
                    if((j-botLeftX)%2==0 || j<topRightX-1){
                        deletePath(points[j][topRightY-1+((j-botLeftX)%2)].right());
                    } else {
                        deletePath(points[topRightX-1][topRightY-1].right());
                    }
                }
            } else {
                if((i-botLeftY)%2==0){
                    for(int j=botLeftX+1; j<topRightX; j++){
                        deletePath(points[j][i].up());
                    }
                } else {
                    for(int j=botLeftX; j<topRightX+1; j++){
                        if(j!=width/2 && j!=width/2-1){
                            deletePath(points[j][i].up());
                        }
                    }
                }
            }
        }
    }

    public Walker(int startingX,int startingY, int Width, int Height, int destinationX, int destinationY, Strategy strategy, int level, boolean animate){
        width = Width;
        height = Height;
        dX = destinationX;
        dY = destinationY;
        x=startingX;
        y=startingY;
        points = new Point[width][height];
        for(int y=0; y<height; y++){
            for(int x=0; x<width; x++){
                points[x][y] = new Point(x,y);
            }
        }
        for(int y=0; y<height; y++){
            for(int x=0; x<width; x++){
                if(x<width-1) new Edge(points[x][y], points[x+1][y]);
                if(y<height-1) new Edge(points[x][y], points[x][y+1]);
            }
        }

        if(strategy == Strategy.SINGLE_PATH) createSinglePath(0,0,width-1,height-1);

        if(strategy == Strategy.DOUBLE_PATH) createDoublePath(0,0,width-1,height-1);

        List<EdgeList> edgeLists = new ArrayList<EdgeList>();
        if(strategy == Strategy.ISLAND){
            List<Edge> edges = new ArrayList<Edge>();
            if(level==0){
                createIsland(0,0,width-1,height-1);
                deletePath(points[width-2][height-2].right());
                deletePath(points[width-2][height-2].up());
            } else {
                for(int i=0; i<level; i++){
                    createIsland(i,i,width-1-i, height-1-i);
                }
                createDoublePath(level,level,width-1-level,height-1-level);
                for(int i=height-1; i>=height-level; i--){
                    edges.add(points[i-2][i].right());
                    edges.add(points[i][i-2].up());
                    edgeLists.add(new EdgeList(points[i-1][i].right(), points[i][i-1].up()));
                }
            }
            edges.add(points[width-1-level][height-1-level].down());
            edges.add(points[width-1-level][height-1-level].left());
            edgeLists.add(new EdgeList(edges.toArray(new Edge[0])));
        }

        int[] availableVerticals = new int[height];
        if(strategy == Strategy.EXTREME_DOUBLE_PATH){
            for(int i=1; i<width-1; i++){
                deletePath(points[i][0].up());
            }
            availableVerticals[0] = 2;
            for(int i=1; i<height; i++){
                availableVerticals[i] = width;
            }
        }

        boolean[][] available = new boolean[width][height];
        if(strategy == Strategy.PERFECT_DOUBLE_PATH){
            for(int x=0; x<width; x++){
                for(int y=0; y<height; y++){
                    if(x%2==1 && y%2==1){
                        available[x][y] = true;
                    } else {
                        available[x][y] = false;
                    }
                }
            }
        }
//      printPath();
        while(!walk()){
            if(animate)try{Thread.sleep(500);}catch(InterruptedException e){}
            if(strategy == Strategy.ISLAND){
                if(x==y && (x==1 || (x>=2 && x<=level))){
                    if(!hasBeenWalked(points[x][x].down())){
                        deletePath(points[x][x].down());
                    } else if(!hasBeenWalked(points[x][x].left())){
                        deletePath(points[x][x].left());
                    }
                }
            }
            if(strategy == Strategy.EXTREME_DOUBLE_PATH){
                Point cur = points[x][y];
                int untravelled = 0;
                for(Edge edge: cur.edges) if(edge!=null && !edge.walked) untravelled++;
                if(untravelled>1){
                    if(cur.up()!=null && availableVerticals[y]>2 && !cur.up().walked){
                        deletePath(cur.up());
                        availableVerticals[y]--;
                    }
                    if(cur.down()!=null && !cur.down().walked){
                        deletePath(cur.down());
                        availableVerticals[y-1]--;
                    }
                    if(cur.up()!=null && cur.left()!=null && !cur.left().walked){
                        deletePath(cur.left());
                        deletePath(points[x][y+1].left());
                    }
                    if(cur.up()!=null && cur.right()!=null && !cur.right().walked){
                        deletePath(cur.right());
                        if(y<height-1) deletePath(points[x][y+1].right());
                    }
                }
            }
            if(strategy == Strategy.PERFECT_DOUBLE_PATH){
                Point cur = points[x][y];
                int untravelled = 0;
                for(Edge edge: cur.edges) if(edge!=null && !edge.walked) untravelled++;
                if(x%2!=1 || y%2!=1){
                    if(untravelled>1){
                        if(cur.down()==null && hasBeenWalked(cur.right())){
                            if(canBeDeleted(cur.up())) deletePath(cur.up());
                        }
                        if(cur.down()==null && hasBeenWalked(cur.left())){
                            if(x%2==0 && y%2==1 && canBeDeleted(cur.right())) deletePath(cur.right());
                            else if(cur.right()!=null && canBeDeleted(cur.up())) deletePath(cur.up());
                        }
                        if(cur.left()==null && hasBeenWalked(cur.up())){
                            if(canBeDeleted(cur.right())) deletePath(cur.right());
                        }
                        if(cur.left()==null && hasBeenWalked(cur.down())){
                            if(x%2==1 && y%2==0 && canBeDeleted(cur.up())) deletePath(cur.up());
                            else if (cur.up()!=null && canBeDeleted(cur.right())) deletePath(cur.right());
                        }
                    }
                } else {
                    if(!hasBeenWalked(cur.left())){
                        if(x>1 && available[x-2][y]){
                            if(untravelled>1){
                                available[x-2][y] = false;
                                deletePath(cur.up());
                            }
                        } else if(cur.up()!=null){
                            if(canBeDeleted(cur.left())) deletePath(cur.left());
                            if(canBeDeleted(points[x][y+1].left())) deletePath(points[x][y+1].left());
                        }
                    }
                    if(!hasBeenWalked(cur.down())){
                        if(y>1 && available[x][y-2]){
                            if(untravelled>1){
                                available[x][y-2] = false;
                                deletePath(cur.right());
                            }
                        } else if(cur.right()!=null){
                            if(canBeDeleted(cur.down())) deletePath(cur.down());
                            if(canBeDeleted(points[x+1][y].down())) deletePath(points[x+1][y].down());
                        }
                    }
                }
            }
            if(strategy == Strategy.DOUBLE_PATH || strategy == Strategy.EXTREME_DOUBLE_PATH
                    || strategy == Strategy.PERFECT_DOUBLE_PATH){
                if(x==width-2 && y==height-1 && points[width-1][height-1].down()!=null){
                    deletePath(points[width-1][height-1].left());
                }
                if(x==width-1 && y==height-2 && points[width-1][height-1].left()!=null){
                    deletePath(points[width-1][height-1].down());
                }
            } else if(strategy == Strategy.ISLAND){
                for(EdgeList edgeList: edgeLists){
                    boolean deleted = false;
                    for(Edge edge: edgeList.edges){
                        if(edge.start.x == x && edge.start.y == y){
                            if(!hasBeenWalked(edge)){
                                deletePath(edge);
                                edgeList.edges.remove(edge);
                                if(edgeList.edges.size() == 1){
                                    edgeLists.remove(edgeList);
                                }
                                deleted = true;
                                break;
                            }
                        }
                    }
                    if(deleted) break;
                }
            }
            if(animate)printPath();
        }
    }

    public boolean hasBeenWalked(Edge edge){
        if(edge == null) return false;
        return edge.walked;
    }

    public boolean canBeDeleted(Edge edge){
        if(edge == null) return false;
        return !edge.walked;
    }

    public List<Edge> getAdjacentUntravelledEdges(){
        List<Edge> result = new ArrayList<Edge>();
        for(Edge edge: points[x][y].edges){
            if(edge!=null && !hasBeenWalked(edge)) result.add(edge); 
        }
        return result;
    }

    public void printPath(){
        StringBuilder builder = new StringBuilder();
        for(int y=height-1; y>=0; y--){
            for(int x=0; x<width; x++){
                Point point = points[x][y];
                if(this.x==x && this.y==y){
                    if(point.up()!=null) builder.append('?');
                    else builder.append('.');
                } else {
                    if(point.up()!=null) builder.append('|');
                    else builder.append(' ');
                }
                if(point.right()!=null) builder.append('_');
                else builder.append(' ');
            }
            builder.append('\n');
        }
        System.out.print(builder.toString());
    }

    public boolean walk(){
        ArrayList<Edge> possibleMoves = new ArrayList<Edge>();
        Point cur = points[x][y];
        for(Edge edge: cur.edges){
            if(edge!=null) possibleMoves.add(edge);
        }
        int random = (int)(Math.random()*possibleMoves.size());
        Edge move = possibleMoves.get(random);
        move.walked = true;
        if(move.start == cur){
            x = move.end.x;
            y = move.end.y;
        } else {
            x = move.start.x;
            y = move.start.y;
        }
        stepCount++;
        if(x==dX && y == dY){
            return true;
        } else {
            return false;
        }
    }

    public boolean isSolvable(){
        TreeSet<Point> reachable = new TreeSet<Point>();
        Queue<Point> next = new LinkedList<Point>();
        next.offer(points[x][y]);
        reachable.add(points[x][y]);
        while(next.size()>0){
            Point cur = next.poll();
            ArrayList<Point> neighbors = new ArrayList<Point>();
            if(cur.up()!=null) neighbors.add(cur.up().end);
            if(cur.right()!=null) neighbors.add(cur.right().end);
            if(cur.down()!=null) neighbors.add(cur.down().start);
            if(cur.left()!=null) neighbors.add(cur.left().start);
            for(Point neighbor: neighbors){
                if(!reachable.contains(neighbor)){
                    if(neighbor == points[dX][dY]) return true;
                    reachable.add(neighbor);
                    next.offer(neighbor);
                }
            }
        }
        return false;
    }

    public boolean deletePath(Edge toDelete){
        if(toDelete == null) return true;
//      if(toDelete.walked){
//          System.err.println("Edge already travelled!");
//          return false;
//      }
        int startIdx = toDelete.getStartIdx();
        int endIdx = toDelete.getEndIdx();
        toDelete.start.edges[startIdx] = null;
        toDelete.end.edges[endIdx] = null;
//      if(!isSolvable()){
//          toDelete.start.edges[startIdx] = toDelete;
//          toDelete.end.edges[endIdx] = toDelete;
//          System.err.println("Invalid deletion!");
//          return false;
//      }
        return true;
    }

    static class EdgeList{
        List<Edge> edges;

        public EdgeList(Edge... edges){
            this.edges = new ArrayList<Edge>();
            this.edges.addAll(Arrays.asList(edges));
        }
    }

    static class Edge implements Comparable<Edge>{
        Point start, end;
        boolean walked;

        public Edge(Point start, Point end){
            walked = false;
            this.start = start;
            this.end = end;
            this.start.edges[getStartIdx()] = this;
            this.end.edges[getEndIdx()] = this;
            if(start.compareTo(end)>0){
                Point tmp = end;
                end = start;
                start = tmp;
            }
        }

        public Edge(int x1, int y1, int x2, int y2){
            this(new Point(x1,y1), new Point(x2,y2));
        }

        public boolean exists(){
            return start.edges[getStartIdx()] != null || end.edges[getEndIdx()] != null;
        }

        public int getStartIdx(){
            if(start.x == end.x){
                if(start.y < end.y) return 0;
                else return 2;
            } else {
                if(start.x < end.x) return 1;
                else return 3;
            }
        }

        public int getEndIdx(){
            if(start.x == end.x){
                if(start.y < end.y) return 2;
                else return 0;
            } else {
                if(start.x < end.x) return 3;
                else return 1;
            }
        }

        public boolean isVertical(){
            return start.x==end.x;
        }

        @Override
        public int compareTo(Edge o) {
            int result = start.compareTo(o.start);
            if(result!=0) return result;
            return end.compareTo(o.end);
        }
    }

    static class Point implements Comparable<Point>{
        int x,y;
        Edge[] edges;

        public Point(int x, int y){
            this.x = x;
            this.y = y;
            edges = new Edge[4];
        }

        public Edge up(){ return edges[0]; }
        public Edge right(){ return edges[1]; }
        public Edge down(){ return edges[2]; }
        public Edge left(){ return edges[3]; }

        public int compareTo(Point o){
            int result = Integer.compare(x, o.x);
            if(result!=0) return result;
            result = Integer.compare(y, o.y);
            if(result!=0) return result;
            return 0;
        }
    }
}
justhalf
sumber
Ini sangat mengesankan. Berapa lama untuk berjalan? Jika entri yang menang tetap sedekat ini kita harus menambah jumlah run untuk melihat apakah kita dapat memisahkannya.
1
Waktunya sudah termasuk dalam cuplikan. Sekitar 400 untuk 1000 berjalan. Itu termasuk pemeriksaan solvabilitas pada setiap penghapusan jalur. Saya bisa menghapusnya untuk memiliki sekitar 170 untuk 1000 berjalan. Jadi saya bisa melakukan 20k lari dalam waktu sekitar satu jam.
justhalf
Sebenarnya mengoptimalkan lebih jauh saya mungkin bisa berlari 100k dalam 3,5 jam.
justhalf
Skor saya dengan 100k lari dan butuh 10 menit. @ Cukuphalf sangat bagus di labirin jalur ganda yang lebih fleksibel. Saya tahu bagaimana membuat yang lebih baik, tetapi saya tidak memiliki kesabaran untuk mengimplementasikannya sekarang.
Sparr
2
Senang melihat solusi simetris diimplementasikan. Saya punya ide lain untuk meningkatkan solusi ini, dan kali ini saya pikir saya mungkin mengimplementasikannya sendiri :)
Sparr
10

227934 (20x20)

Upaya ketiga saya. Menggunakan pendekatan umum yang sama dengan @stokastic dengan dua jalur keluar. Ketika walker mencapai ujung satu jalan, itu menutup, mengharuskan dia untuk kembali ke ujung jalan lain untuk keluar. Peningkatan saya adalah menghasilkan jalur saat pejalan maju, sehingga jalur mana pun yang ia laju lebih jauh di paruh pertama proses akan berakhir lebih lama dari jalur lainnya.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <iostream>

#define DEBUG 0
#define ROUNDS 10000

#define Y 20
#define X 20
#define H (Y*2+1)
#define W (X*2+1)

int maze[H][W];
int scores[ROUNDS];

int x, y;

void print_maze(){
    char line[W+2];
    line[W+1]=0;
    for(int row=0;row<H;row++) {
        for(int col=0;col<W;col++) {
            switch(maze[row][col]) {
                case 0:
                    line[col]=' ';
                    break;
                case 1:
                    line[col]=row%2?'-':'|';
                    break;
                case 8:
                    line[col]=(row==y*2+1&&col==x*2+1)?'@':'?';
                    break;
                case 9:
                    line[col]=(row==y*2+1&&col==x*2+1)?'@':'*';
                    break;
            }
        }
        line[W]='\n';
        printf("%s",line);
    }
    printf("%d %d\n",y,x);
}

int main(){
    srand (time(NULL));
    long long total_turns = 0;
    for(int round=0;round<ROUNDS;round++) {
        for (int r=0;r<H;r++) {
            for (int c=0;c<W;c++) {
                maze[r][c]=0;
            }
        }
        maze[1][1]=9;
        maze[1][2]=1;
        maze[2][1]=1;
        maze[1][3]=8;
        maze[3][1]=8;
        int progress_l = 0;
        int progress_r = 0;
        int side = 0;
        int closed_exit = 0;
        x=0;
        y=0;
        if (DEBUG) print_maze();
        long long turn = 0;
        int in = 0;
        while (x!=X-1||y!=Y-1) {
            turn++;
            int r = y*2+1;
            int c = x*2+1;
            int dx=0, dy=0;
            if (DEBUG) {
                std::cin>>in;
                switch(in) {
                    case 0:
                        dy=-1; dx=0; break;
                    case 1:
                        dy=0; dx=1; break;
                    case 2:
                        dy=1; dx=0; break;
                    case 3:
                        dy=0; dx=-1; break;
                    default:
                        dy=0; dx=0; break;
                }
            } else {
                int exits = maze[r-1][c] + maze[r][c+1] + maze[r+1][c] + maze[r][c-1];
                int exit_choice = -1;
                do {
                    if (rand()%exits == 0) {
                        exit_choice = exits;
                        break;
                    } else {
                        exits--;
                    }
                }while(exits);

                --exits;

                if (maze[r-1][c]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = -1;
                        dx = 0;
                    }
                }
                if (maze[r][c+1]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 0;
                        dx = 1;
                    }
                }
                if (maze[r+1][c]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 1;
                        dx = 0;
                    }
                }
                if (maze[r][c-1]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 0;
                        dx = -1;
                    }
                }
            }

            x+=dx;
            y+=dy;

            if(x==X-1 && y==Y-1) continue;

            if (x==0&&y==1) side=-1;
            if (x==1&&y==0) side=1;
            if (maze[y*2+1][x*2+1]==8) { // room needs another exit, maybe
                if (side==-1) { // left half of maze
                    if (y==1) { // top of a column
                        if (x%2) { // going up, turn right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // going right, turn down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==Y-1) { // bottom of a column
                        if (x%2 && x<(X-progress_r-3)) { // going right, turn up if there's room
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                            progress_l=x+1;
                        } else { // going down or exiting, go right
                            if (x!=X-2 or closed_exit==1) {
                                maze[y*2+1][x*2+2]=1;
                                maze[y*2+1][x*2+3]=8;
                            } else {
                                closed_exit = -1;
                            }
                        }
                    } else { // in a column
                        if (maze[y*2+0][x*2+1]) { // going down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        } else { // going up
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                        }
                    }
                } else { // right half of maze
                    if (y==0) { // top row
                        if (x<X-1) { // go right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // go down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==Y-2) { // heading right to the exit
                        if (x<X-1) { // go right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // go down
                            if (x!=X-1 or closed_exit==-1) {
                                maze[y*2+2][x*2+1]=1;
                                maze[y*2+3][x*2+1]=8;
                            } else {
                                closed_exit = 1;
                            }
                        }
                    } else if (y==Y-3) { // bottom of a column
                        if (x>progress_l+1) { // do we have room for another column?
                            if (!(x%2)&&y>1) { // going left, turn up
                                maze[y*2+0][x*2+1]=1;
                                maze[y*2-1][x*2+1]=8;
                            } else { // going down, turn left
                                maze[y*2+1][x*2+0]=1;
                                maze[y*2+1][x*2-1]=8;
                                progress_r=X-x-1;
                            }
                        } else { // abort, move down to escape row
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==1) { // top of a column
                        if (!(x%2)) { // going up, turn left
                            maze[y*2+1][x*2+0]=1;
                            maze[y*2+1][x*2-1]=8;
                        } else { // going left, turn down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else { // in a column
                        if (maze[y*2+0][x*2+1]) { // going down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        } else { // going up
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                        }
                    }

                }
                maze[y*2+1][x*2+1]=9;
            }

            if (DEBUG) print_maze();
        }
        // print_maze();
        printf("turns:%lld\n",turn);
        scores[round] = turn;
        total_turns += turn;
    }
    printf("%d rounds in a %d*%d maze\n",ROUNDS,X,Y);
    long long avg = total_turns/ROUNDS;
    printf("average: % 10lld\n",avg);
    long long var = 0;
    for(int r=0;r<ROUNDS;r++){
        var += (scores[r]-avg)*(scores[r]-avg);
    }
    var/=ROUNDS;
    // printf("variance: %lld\n",var);
    int stddev=sqrt(var);
    printf("stddev:  % 10d\n",stddev);

}

output (dengan waktu):

...
turns:194750
turns:506468
turns:129684
turns:200712
turns:158664
turns:156550
turns:311440
turns:137900
turns:86948
turns:107134
turns:81806
turns:310274
100000 rounds in a 20*20 maze
average:     227934
stddev:      138349
real    10m54.797s
...

contoh labirin saya, dengan panjang kira-kira sama panjang dengan jalan, menunjukkan jalan kiri / bawah terputus dari pintu keluar (kanan bawah):

  _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 |  _   _   _   _   _   _   _   _   _  |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | |_| |_| |_| |_| |_|
 | | | | | | | | | |_ _ _ _ _ _ _ _ _ _
 |_| |_| |_| |_| |_ _ _ _ _ _ _ _ _ _  !

PS: Saya menyadari peningkatan yang sangat kecil untuk algoritma ini yang membutuhkan kode yang lebih pintar untuk menghasilkan bentuk yang berbeda untuk dua jalur, tangga bukannya tinggi zig zag yang konsisten.

Sparr
sumber
Warna saya terkesan. Anda memiliki suara saya Pak!
stokastic
1
Itu cukup mengesankan. Ingat ketika kita baru saja menggambar di wajah para pemabuk?
Dennis
Cukup sulit untuk membedakan grafik Anda, mungkin Anda dapat mengubah pencetakan grafik Anda menjadi sesuatu yang mirip dengan milik saya?
justhalf
1
@ justhalf keinginanmu adalah perintahku
Sparr
1
@ justhalf Aku sudah mengeluarkannya di atas kertas. Hanya perlu menulis logikanya. Jika saya tidak menyelesaikannya dalam beberapa hari lagi, saya akan memberi Anda sketsa? :)
Sparr
6

135.488.307,9 untuk 98x98

199094.3 untuk 20x20

Saya telah menerapkan solusi yang menciptakan dua jalur ke garis finish, dan menutup salah satu dari mereka begitu pemabuk mencapai itu. Ini mensimulasikan panjang lintasan yang setidaknya 1,5 kali panjang lintasan tunggal dari awal sampai akhir. Setelah 27 berjalan saya mencapai rata-rata sekitar 135 juta. Sayangnya dibutuhkan beberapa menit per berjalan, jadi saya harus menjalankannya selama beberapa jam ke depan. Satu peringatan - generator jalur ganda saya hanya berfungsi jika ukuran grafik dalam bentuk 4 * n + 2, artinya yang terdekat yang bisa saya dapatkan dengan 100 adalah 102 atau 98. Saya akan memposting hasil menggunakan 98, yang saya harapkan masih melampaui metode jalur zigzag. Saya akan bekerja pada sistem jalur yang lebih baik nanti. Saat ini hasil keluaran dalam bentuk (numSteps, currentAverage) setelah setiap berjalan.

EDIT: diperbaiki jadi kode sekarang bekerja pada ukuran grafik yang merupakan kelipatan dari 2, bukan 4 * n + 2.

Kode: (tambahkan argumen 'Benar' ke konstruktor walker on line 187 untuk menggambar grafik penyu).

import random
import turtle

WIDTH  = 20
HEIGHT = 20
L, U, R, D = 1, 2, 4, 8

def delEdge(grid, x1, y1, x2, y2):

    # check that coordinates are in-bounds
    if not (0 <= x1 < WIDTH):  return False
    if not (0 <= y1 < HEIGHT): return False
    if not (0 <= x2 < WIDTH):  return False
    if not (0 <= y2 < HEIGHT): return False

    # swap order such that x1 <= x2 and y1 <= y2
    if x2 < x1:
        x2 ^= x1
        x1 ^= x2
        x2 ^= x1
    if x2 < x1: print "Swap failure: {}, {}".format(x1, x2)

    if y2 < y1:
        y2 ^= y1
        y1 ^= y2
        y2 ^= y1
    if y2 < y1: print "Swap failure: {}, {}".format(y1, y2)

    # check that only one of the deltas is = 1
    dx = x2 - x1
    dy = y2 - y1

    if dx and dy:       return False
    if not (dx or dy):  return False
    if dx > 1:          return False
    if dy > 1:          return False

    #print "<{}, {}>, <{}, {}>".format(x1, y1, x2, y2)

    if dx > 0:
        try: grid[x1][y1].remove(R)
        except: pass
        try: grid[x2][y2].remove(L)
        except: pass
    if dy > 0:
        try: grid[x1][y1].remove(D)
        except: pass
        try: grid[x2][y2].remove(U)
        except: pass

    return True

def newGrid():

    grid = [[[] for y in xrange(HEIGHT)] for x in xrange(WIDTH)]

    for x in xrange(WIDTH):
        for y in xrange(HEIGHT):
            if x > 0:
                grid[x][y].append(L)
            if x < WIDTH-1:
                grid[x][y].append(R)
            if y > 0:
                grid[x][y].append(U)
            if y < HEIGHT-1:
                grid[x][y].append(D)

    return grid

class walker:

    def __init__(self, grid, mode, draw=False):
        self.x  = 0
        self.y  = 0
        self.dx = WIDTH-1
        self.dy = HEIGHT-1

        self.grid     = grid
        self.mode     = mode
        self.draw     = draw
        self.numSteps = 0

        self.initGrid()

    def initGrid(self):
        if self.mode == 0:
            #pass
            if self.draw: drawGrid(grid)

        elif self.mode == 1:

            for y in xrange(HEIGHT-1):
                if y % 2 == 0:
                    for x in xrange(WIDTH - 1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(1, WIDTH):
                        delEdge(grid, x, y, x, y+1)
            if self.draw: drawGrid(grid)

        elif self.mode == 2:
            for y in xrange(HEIGHT/2):
                if y % 2 == 0:
                    for x in xrange(1, WIDTH-1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(2, WIDTH):
                        delEdge(grid, x, y, x, y+1)
            for y in xrange(HEIGHT/2, HEIGHT-1):
                if y%2 == 0:
                    for x in xrange(1, WIDTH-1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(0, WIDTH-2):
                        delEdge(grid, x, y, x, y+1)
            for y in xrange(1, HEIGHT-1):
                midpoint = HEIGHT/2
                if HEIGHT % 4 == 0: 
                    midpoint = HEIGHT/2 + 1
                if y < midpoint:
                    delEdge(grid, 0, y, 1, y)
                else:
                    delEdge(grid, WIDTH-1, y, WIDTH-2, y)
            if self.draw: drawGrid(grid)

    def walk(self):
        self.numSteps += 1
        choices = grid[self.x][self.y]
        direction = random.choice(choices)
        #print (self.x, self.y), grid[self.x][self.y], direction
        if direction   == L: self.x -= 1
        elif direction == U: self.y -= 1
        elif direction == R: self.x += 1
        elif direction == D: self.y += 1

    def main(self):
        hasBlocked = False
        while (self.x, self.y) != (self.dx, self.dy):
            #print (self.x, self.y), (self.dx, self.dy)
            self.walk()
            if self.mode == 2:
                if not hasBlocked:
                    if (self.x, self.y) == (WIDTH-2, HEIGHT-1):
                        delEdge(self.grid, WIDTH-2, HEIGHT-1, WIDTH-1, HEIGHT-1)
                        hasBlocked = True
                    elif (self.x, self.y) == (WIDTH-1, HEIGHT-2):
                        delEdge(self.grid, WIDTH-1, HEIGHT-1, WIDTH-1, HEIGHT-2)
                        hasBlocked = True

        return self.numSteps

def drawGrid(grid):
    size = 3
    turtle.speed(0)
    turtle.delay(0)
    turtle.ht()
    for x in xrange(WIDTH):
        for y in xrange(HEIGHT):
            dirs = grid[x][y]
            for dir in dirs:
                if dir == L:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos(((x-1)*4, y*4))
                elif dir == R:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos(((x+1)*4, y*4))
                elif dir == U:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos((x*4, (y-1)*4))
                elif dir == D:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos((x*4, (y+1)*4))
    turtle.mainloop()

numTrials  = 100
totalSteps = 0.0
i = 0
try:
    while i < numTrials:
        grid = newGrid()

        w = walker(grid, 2)
        steps = w.main()
        totalSteps += steps
        print steps, totalSteps/(i+1)
        i += 1

    print totalSteps / numTrials

except KeyboardInterrupt:
    print totalSteps / i

Data mentah: (numSteps saat ini, rata-rata berjalan)

358796490 358796490.0
49310430 204053460.0
106969130 171692016.667
71781702 146714438.0
49349086 127241367.6
40874636 112846912.333
487607888 166384194.571
56423642 152639125.5
71077302 143576700.667
101885368 139407567.4
74423642 133499937.818
265170542 144472488.167
59524778 137938048.923
86919630 134293876.143
122462528 133505119.6
69262650 129489965.25
85525556 126903823.529
161165512 128807250.667
263965384 135920836.632
128907594 135570174.5
89535930 133378067.619
97344576 131740181.636
98772132 130306788.174
140769524 130742735.5
198274280 133443997.28
95417374 131981434.846
226667006 135488307.852
stokastik
sumber
Saya mengurangi ukuran grafik menjadi 20 dengan 20 untuk membuat waktu berlari lebih cepat. Saya harap ini membantu.
Anda saat ini menang :)
Apakah skor 20 kali 20 Anda lebih dari 1000 kali?
@Lembik ya itu.
stokastic
1
@Dennis au contraire :)
Sparr
6

Pendekatan 4 jalur, 213k

Pendekatan satu jalur adalah

Garis lurus dari S ke E

dan skor rata-rata N^2.

Pendekatan dua jalur adalah

Loop dengan S dan E saling berhadapan

tetapi kemudian saat pemabuk pertama kali mencapai titik akhir, ia terpotong:

Loop dipotong untuk memberikan garis lengkung dari S ke E

Ini skor rata-rata (N/2)^2 + N^2.

Pendekatan empat jalur menggunakan dua pemotongan:

Loop bersarang, bergabung dalam dua garpu, satu sisi E Potong salah satu garpu di sisi E Di sisi lain, potong garpu di sisi non-E. Ini menyisakan satu jalan berbelit-belit

Asumsikan bahwa loop luar panjang xNdan loop dalam panjang (1-x)N. Untuk kesederhanaan, saya akan menormalkanN=1 .

Dari mulai hingga skor cut pertama rata-rata (x/2)^2. Dari potongan pertama ke potongan kedua memiliki dua opsi, panjangx dan 1-x; ini memberikan rata-rata(1-x)x^2 + x(1-x)^2 = x-x^2 . Akhirnya jalan yang tersisa memberi 1. Jadi skor totalnya adalah N^2 (1 + x - 3/4 x^2).

Saya awalnya berasumsi bahwa menjaga jalur yang tersedia dengan panjang yang sama di setiap langkah akan optimal, jadi pendekatan awal saya digunakan x = 1/2memberikan skor 1.3125 N^2. Tetapi setelah melakukan analisis di atas ternyata pembagian optimal diberikan ketika x = 2/3dengan skor 1.3333 N^2.

1000 walks with average 210505.738 in 202753ms


1000 walks with average 212704.626 in 205191ms

dengan kode

import java.awt.Point;
import java.util.*;

// http://codegolf.stackexchange.com/q/37484/194
public class RandomWalker {
    private static final int SIZE = 19;
    private static final Point dest = new Point(SIZE, SIZE);

    private final Random rnd = new Random();
    private Point p = new Point(0, 0);
    private int step = 0;
    private Set<Set<Point>> edges;
    private Map<Set<Point>, String> cuttableEdgeNames;
    private Set<String> cutSequences;
    private String cutSequence = "";

    public static void main(String[] args) {
        long start = System.nanoTime();
        long total = 0;
        int walks = 0;
        while (walks < 1000 && total < 1L << 40) {
            RandomWalker rw = new RandomWalker();
            total += rw.walk();
            walks++;
        }

        long timeTaken = System.nanoTime() - start;
        System.out.println(walks + " walks with average " + total / (double)walks + " in " + (timeTaken / 1000000) + "ms");
    }

    RandomWalker() {
        loadMaze(
            "+-+ +-+ +-+ +-+ +-+ +-+ +-+-+-+-+-+-+-+",
            "| | | | | | | | | | | | |             |",
            "+ + + + + + + + + + + + + +-+ +-+ +-+ +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | |     | | | | | | |",
            "+ + + + + + + + + + + +-+-+ + + + + + +",
            "| | | | | | | | | | | |     | | | | | |",
            "+ + + + + + + + + + + + +-+ + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ +-+ +-+ +-+ +-+ +-+ + + + + + + + + +",
            "|                     | | | | | | | | |",
            "+ +-+ +-+ +-+ +-+ +-+ + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | |     | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | d",
            "+ + + + + + + + + + + + + + +-+ +-+ +c+",
            "| | | | | | | | | | | | | |           |",
            "+ + + + + + + + + + + + + +-+-+-+-+-+ +",
            "| | | | | | | | | | | | |           f b",
            "+-+ +-+ +-+ +-+ +-+ +-+ +-+-+-+-+-+e+a+"
        );
        cutSequences = new HashSet<String>();
        cutSequences.add("ac");
        cutSequences.add("ad");
        cutSequences.add("be");
        cutSequences.add("bf");
    }

    private void loadMaze(String... row) {
        edges = new HashSet<Set<Point>>();
        cuttableEdgeNames = new HashMap<Set<Point>, String>();

        // Horizontal edges
        for (int y = 0; y <= SIZE; y++) {
            for (int x0 = 0; x0 < SIZE; x0++) {
                char ch = row[y * 2].charAt(x0 * 2 + 1);
                if (ch == ' ') continue;
                Set<Point> edge = new HashSet<Point>();
                edge.add(new Point(x0, y));
                edge.add(new Point(x0 + 1, y));
                edges.add(edge);
                if (ch != '-') cuttableEdgeNames.put(edge, "" + ch);
            }
        }

        // Vertical edges
        for (int y0 = 0; y0 < SIZE; y0++) {
            for (int x = 0; x <= SIZE; x++) {
                char ch = row[y0 * 2 + 1].charAt(x * 2);
                if (ch == ' ') continue;
                Set<Point> edge = new HashSet<Point>();
                edge.add(new Point(x, y0));
                edge.add(new Point(x, y0 + 1));
                edges.add(edge);
                if (ch != '|') cuttableEdgeNames.put(edge, "" + ch);
            }
        }
    }

    int walk() {
        while (!p.equals(dest)) {
            List<Point> neighbours = neighbours(p);
            int idx = rnd.nextInt(neighbours.size());
            p = neighbours.get(idx);
            step++;
        }

        return step;
    }

    List<Point> neighbours(Point p) {
        List<Point> rv = new ArrayList<Point>();
        if (p.x > 0) handlePossibleNeighbour(rv, p, new Point(p.x - 1, p.y));
        if (p.x < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x + 1, p.y));
        if (p.y > 0) handlePossibleNeighbour(rv, p, new Point(p.x, p.y - 1));
        if (p.y < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x, p.y + 1));
        return rv;
    }

    private void handlePossibleNeighbour(List<Point> neighbours, Point p1, Point p2) {
        if (edgeExists(p1, p2)) neighbours.add(p2);
    }

    private boolean edgeExists(Point p1, Point p2) {
        Set<Point> edge = new HashSet<Point>();
        edge.add(p1);
        edge.add(p2);

        // Is it cuttable?
        String id = cuttableEdgeNames.get(edge);
        if (id != null) {
            String prefix = cutSequence + id;
            for (String seq : cutSequences) {
                if (seq.startsWith(prefix)) {
                    // Cut it
                    cutSequence = prefix;
                    edges.remove(edge);
                    return false;
                }
            }
        }

        return edges.contains(edge);
    }
}
Peter Taylor
sumber
Ah, saya mengerti, itu sebabnya pendekatan pulau saya tidak berhasil, saya tidak membuat panjang jalur seimbang. Hanya untuk memperjelas pemahaman saya, panjang dari fke cdalam kode Anda adalah tentang N/2, baik melalui e(dan d) atau tidak, kan?
justhalf
bagaimana panjang jalur yE N dan bukan panjang N / 2?
Sparr
@ justhalf, ya. Ada 400 simpul, jadi ada 401 tepi (setelah satu potong grafik adalah siklus Hamiltonian); dua lintasan luar masing-masing 100 tepi, dan loop dalam karenanya 101 tepi.
Peter Taylor
mengerti. dua pengamatan: a) labirin yang lebih besar akan mendapat manfaat dari jalur yang lebih besar. b) jika Anda membuat panjang jalur Anda dinamis, Anda akan mengalahkan para pemimpin saat ini dengan solusi dua jalur dinamis (saya dan @justhalf)
Sparr
@Parr: itu N^2, bukan 2^N. Dan ya, membuat dinamika ini akan menjadikannya yang terbaik, tantangannya adalah bagaimana membuatnya dinamis sambil mempertahankan properti empat jalur. @PeterTaylor: Gambar yang bagus!
justhalf
5

Saya bereksperimen dengan mengiris grid hampir seluruhnya di setiap kbaris. Ini secara efektif mengubahnya menjadi sesuatu yang mirip dengan acak berjalan pada koleh N * N/kjaringan. Opsi yang paling efektif adalah mengiris setiap baris sehingga kami memaksa pemabuk ke zigzag.

Untuk kasus 20x20 ( SIZE=19) saya punya

time java RandomWalker 
1000 walks with average 148577.604

real    0m14.076s
user    0m13.713s
sys     0m0.360s

dengan kode

import java.awt.Point;
import java.util.*;

// http://codegolf.stackexchange.com/q/37484/194
// This handles a simpler problem where the grid is mutilated before the drunkard starts to walk.
public class RandomWalker {
    private static final int SIZE = 19;
    private final Random rnd = new Random();

    public static void main(String[] args) {
        RandomWalker rw = new RandomWalker();
        long total = 0;
        int walks = 0;
        while (walks < 1000 && total < 1L << 40) {
            total += rw.walk();
            walks++;
        }

        System.out.println(walks + " walks with average " + total / (double)walks);
    }

    int walk() {
        Point dest = new Point(SIZE, SIZE);
        Point p = new Point(0, 0);
        int step = 0;

        while (!p.equals(dest)) {
            List<Point> neighbours = neighbours(p);
            int idx = rnd.nextInt(neighbours.size());
            p = neighbours.get(idx);
            step++;
        }

        return step;
    }

    List<Point> neighbours(Point p) {
        List<Point> rv = new ArrayList<Point>();
        if (p.x > 0) handlePossibleNeighbour(rv, p, new Point(p.x - 1, p.y));
        if (p.x < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x + 1, p.y));
        if (p.y > 0) handlePossibleNeighbour(rv, p, new Point(p.x, p.y - 1));
        if (p.y < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x, p.y + 1));
        return rv;
    }

    private void handlePossibleNeighbour(List<Point> neighbours, Point p1, Point p2) {
        if (edgeExists(p1, p2)) neighbours.add(p2);
    }

    private boolean edgeExists(Point p1, Point p2) {
        return p1.x != p2.x || p1.x == SIZE * (Math.max(p1.y, p2.y) & 1);
    }
}
Peter Taylor
sumber
Apakah saya benar dalam berpikir bahwa semua penghapusan tepi terjadi sebelum perjalanan dimulai pada solusi Anda?
@Lembik, ya. Saya pikir komentar di atas akan memperjelasnya.
Peter Taylor
Ya, terima kasih. Saya bertanya-tanya berapa banyak perbedaan yang dapat Anda buat dengan menghapus tepian selama berjalan.
Karena penasaran, berapa lama waktu yang dibutuhkan untuk menjalankan (semuanya dan per proses)?
stokastic
@stokastic, sekitar 3 detik per lari.
Peter Taylor
3

Bagi mereka yang tidak ingin menemukan kembali roda

Jangan khawatir! Saya akan menciptakannya untuk Anda :)

Omong-omong, ini di Jawa.

Saya membuat kelas Walker yang berhubungan dengan berjalan secara acak. Ini juga mencakup metode yang bermanfaat untuk menentukan apakah suatu langkah valid (jika sudah berjalan di atas).

Saya berasumsi kalian semua orang pintar bisa mencari untuk memasukkan angka acak untuk konstruktor, saya menyerahkannya kepada Anda sehingga Anda dapat menguji kasus-kasus tertentu. Juga, panggil saja fungsi walk () untuk (Anda dapat menebaknya!) Membuat pemabuk tersebut berjalan (secara acak).

Saya akan mengimplementasikan fungsi canComeHome () di lain waktu. Lebih disukai setelah saya mencari cara terbaik untuk melakukan itu.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeSet;

public class Walker {
    int width,height;
    int x,y; //walker's position (does anyone else keep thinking about zombies?!?)
    int dX,dY; //destination
    TreeSet<Edge> pathsNoLongerAvailable = new TreeSet<Edge>();
    TreeSet<Edge> previouslyTraveled = new TreeSet<Edge>();
    int stepCount = 0;

    public static void main(String[]args){
        int side = 10;
        Walker walker = null;
        int total = 0;
        double count = 1000;
        for(int i=0; i<count; i++){
            walker = new Walker(0,0,side,side,side-1,side-1);
            total += walker.stepCount;
            System.out.println("Iteration "+i+": "+walker.stepCount);
        }
        System.out.printf("Average: %.3f\n", total/count);
        walker.printPath();
    }

    public Walker(int startingX,int startingY, int Width, int Height, int destinationX, int destinationY){
        width = Width;
        height = Height;
        dX = destinationX;
        dY = destinationY;
        x=startingX;
        y=startingY;
        while(!walk()){
            // Do something
        }
    }

    public void printPath(){
        for(int i=0; i<width-1; i++){
            if(!pathsNoLongerAvailable.contains(new Edge(i,height-1,i+1,height-1))){
                System.out.print(" _");
            } else {
                System.out.print("  ");
            }
        }
        System.out.println();
        for(int i=height-2; i>=0; i--){
            for(int j=0; j<2*width-1; j++){
                if(j%2==0){
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2,i+1))){
                        System.out.print("|");
                    } else {
                        System.out.print(" ");
                    }
                } else {
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2+1,i))){
                        System.out.print("_");
                    } else {
                        System.out.print(" ");
                    }
                }
            }
            System.out.println();
        }
    }

    public boolean walk(){
        ArrayList<int[]> possibleMoves = new ArrayList<int[]>();
        if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
            possibleMoves.add(new int[]{-1,0});
        }
        if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
            possibleMoves.add(new int[]{1,0});
        }
        if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
            possibleMoves.add(new int[]{0,-1});
        }
        if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
            possibleMoves.add(new int[]{0,1});
        }
        int random = (int)(Math.random()*possibleMoves.size());
        int[] move = possibleMoves.get(random);
        previouslyTraveled.add(new Edge(x,y,x+move[0],y+move[1]));
        x+=move[0];
        y+=move[1];
        stepCount++;
        if(x==dX && y == dY){
            return true;
        } else {
            return false;
        }
    }

    public boolean isSolvable(){
        TreeSet<Point> reachable = new TreeSet<Point>();
        Queue<Point> next = new LinkedList<Point>();
        next.offer(new Point(x,y));
        reachable.add(new Point(x,y));
        while(next.size()>0){
            Point cur = next.poll();
            int x = cur.x;
            int y = cur.y;
            ArrayList<Point> neighbors = new ArrayList<Point>();
            if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
                neighbors.add(new Point(x-1, y));
            }
            if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
                neighbors.add(new Point(x+1, y));
            }
            if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
                neighbors.add(new Point(x, y-1));
            }
            if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
                neighbors.add(new Point(x, y+1));
            }
            for(Point neighbor: neighbors){
                if(!reachable.contains(neighbor)){
                    if(neighbor.compareTo(new Point(dX, dY))==0){
                        return true;
                    }
                    reachable.add(neighbor);
                    next.offer(neighbor);
                }
            }
        }
        return false;
    }

    public boolean hasBeenWalked(int x1, int y1, int x2, int y2){
        return previouslyTraveled.contains(new Edge(x1, y1, x2, y2));
    }

    public boolean hasBeenWalked(Edge edge){
        return previouslyTraveled.contains(edge);
    }

    public void deletePath(int startX, int startY, int endX, int endY){
        Edge toAdd = new Edge(startX,startY,endX,endY);
        if(hasBeenWalked(toAdd)){
            System.out.println("Edge already travelled!");
            return;
        }
        pathsNoLongerAvailable.add(toAdd);
        if(!isSolvable()){
            pathsNoLongerAvailable.remove(toAdd);
            System.out.println("Invalid deletion!");
        }
    }

    static class Edge implements Comparable<Edge>{
        Point start, end;

        public Edge(int x1, int y1, int x2, int y2){
            start = new Point(x1, y1);
            end = new Point(x2, y2);
            if(start.compareTo(end)>0){
                Point tmp = end;
                end = start;
                start = tmp;
            }
        }

        @Override
        public int compareTo(Edge o) {
            int result = start.compareTo(o.start);
            if(result!=0) return result;
            return end.compareTo(o.end);
        }
    }

    static class Point implements Comparable<Point>{
        int x,y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        public int compareTo(Point o){
            int result = Integer.compare(x, o.x);
            if(result!=0) return result;
            result = Integer.compare(y, o.y);
            if(result!=0) return result;
            return 0;
        }
    }
}
Regangkan Maniac
sumber
Ini mengandung beberapa bug dan ketidakkonsistenan. previouslyTraveled.add(new int[]{x,y,move[0],move[1]})harus x+move[0]dan y+move[1]. The Width-1dan Height-1, dan ketidakefisienan dalam memeriksa jalur yang dihapus. Saya telah mengedit kode Anda (dengan fungsi tambahan untuk mencetak labirin). Jangan ragu untuk mengembalikan jika Anda pikir itu tidak pantas.
justhalf
Anda Edgetidak menerapkan dengan benar Comparable<Edge>. Jika Anda ingin tepi membandingkan sebagai sama bahkan jika Anda membalikkannya, Anda perlu memperhitungkan pembalikan juga dalam kasus yang tidak sama. Cara termudah untuk melakukan ini adalah mengubah konstruktor untuk menjaga agar poin tetap tertata.
Peter Taylor
@PeterTaylor: Terima kasih atas bantuannya. Saya sedikit memikirkan kasus yang tidak sama, tetapi tidak bisa mengerti mengapa itu penting. Apakah Anda tahu di mana saya dapat mencari persyaratan implementasi Comparable?
justhalf
1
docs.oracle.com/javase/7/docs/api/java/lang/Comparable.html Kuncinya adalah perlu mendefinisikan total pemesanan. Tetapi jika Adan Badalah ujung yang sama terbalik dan Cberbeda, Anda bisa mendapatkan A.compareTo(B) == B.compareTo(A) == 0tetapi A.compareTo(C) < 0dan B.compareTo(C) > 0.
Peter Taylor
Bagaimana kalau sekarang? Saya menambahkan kelas lain. Dan saya menambahkan fungsi untuk memeriksa apakah itu dapat dipecahkan (atau canComeHome())
justhalf
3

64.281

Memperbarui sejak kisi diubah dari 100x100 ke 20x20 (1000 tes). Skor 100x100 (100 tes) kira-kira 36M.

Meskipun ini tidak akan mengalahkan jalan 1D, saya ingin bermain dengan ide yang saya miliki.

Ide dasarnya adalah bahwa grid dibagi menjadi ruang-ruang persegi, dengan hanya satu jalur yang menuju 'rumah' dari masing-masing. Jalur terbuka adalah yang mana pun pemabuk itu mendekati yang terakhir , artinya dia harus menjelajahi setiap kemungkinan keluar, hanya untuk memiliki semua kecuali satu dari mereka yang terbanting di wajahnya.

Setelah bermain dengan ukuran kamar, saya sampai pada kesimpulan yang sama dengan Peter, mengirisnya menjadi lebih kecil lebih baik. Skor terbaik datang dengan ukuran kamar 2.

Average score over 100 trials: 36051265

Kode ini ceroboh, tidak masalah berantakan. Anda dapat menyalakan SHOWsakelar dan itu akan menampilkan gambar jalur setiap SHOW_INTlangkah sehingga Anda dapat melihatnya beraksi. Proses yang selesai terlihat seperti:

masukkan deskripsi gambar di sini

(Ini adalah gambar dari kisi 100x100 sebelumnya. 20x20 persis seperti ini, tetapi, yah, lebih kecil. Kode di bawah ini telah diperbarui untuk ukuran / proses baru.)

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;
import java.awt.image.*;
import java.util.*;
import javax.swing.*;

public class DrunkWalk {

    boolean SHOW = false;
    int SHOW_INT = 10;
    int SIZE = 20;
    Random rand = new Random();
    Point pos;
    int[][] edges;
    int[][] wally;
    int[] wallx;
    int roomSize = 2;
    JFrame frame;
    final BufferedImage img;

    public static void main(String[] args){
        long total=0,runs=1000;
        for(int i=0;i<runs;i++){
            int steps = new DrunkWalk().run();
            total += steps;
            System.out.println("("+i+") "+steps);
        }
        System.out.println("\n Average " + (total/runs) + " over " + runs + " trials.");
    }

    DrunkWalk(){
        edges = new int[SIZE][SIZE];
        for(int x=0;x<SIZE;x++){
            for(int y=0;y<SIZE;y++){
                if(x>0) edges[x][y] |= WEST;
                if(x+1<SIZE) edges[x][y] |= EAST;
                if(y>0) edges[x][y] |= NORTH;
                if(y+1<SIZE) edges[x][y] |= SOUTH;
            }
        }
        wallx = new int[SIZE/roomSize+1];
        wally = new int[SIZE/roomSize+1][SIZE/roomSize+1];
        pos = new Point(SIZE-1,SIZE-1);
        img = new BufferedImage(SIZE*6+1,SIZE*6+1, BufferedImage.TYPE_INT_RGB);
        frame = new JFrame(){
            public void paint(Graphics g) {
                g.drawImage(img, 50, 50, null);
            }
        };
        frame.setSize(700,700);
        if(SHOW)
            frame.show();
    }

    void draw(){
        try {
            Thread.sleep(200);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        Graphics g = img.getGraphics();
        g.setColor(Color.WHITE);
        g.clearRect(0, 0, img.getWidth(), img.getHeight());
        for(int x=0;x<SIZE;x++){
            for(int y=0;y<SIZE;y++){
                if((edges[x][y]&EAST)==EAST)
                    g.drawLine(x*6, y*6, x*6+5, y*6);
                if((edges[x][y]&SOUTH)==SOUTH)
                    g.drawLine(x*6, y*6, x*6, y*6+5);
            }
        }
        g.setColor(Color.RED);
        g.drawOval(pos.x*6-2, pos.y*6-2, 5, 5);
        g.drawOval(pos.x*6-1, pos.y*6-1, 3, 3);
        frame.repaint();
    }

    int run(){
        int steps = 0;
        Point home = new Point(0,0);
        while(!pos.equals(home)){
            if(SHOW&&steps%SHOW_INT==0){
                System.out.println(steps);
                draw();
            }
            step();
            adversary();
            steps++;
        }
        if(SHOW)
            draw();
        return steps;
    }

    void adversary(){
        int rx = pos.x / roomSize;
        int ry = pos.y / roomSize;
        int maxWalls = roomSize - 1;
        if(wally[rx][ry] < maxWalls){
            if(pos.y%roomSize==0)
                if(delete(pos.x,pos.y,NORTH))
                    wally[rx][ry]++;
        }
        maxWalls = SIZE-1;
        if(pos.x%roomSize==0){
            if(wallx[rx] < maxWalls)
                if(delete(pos.x, pos.y,WEST))
                    wallx[rx]++;


        }       
    }

    void step(){
        List<Integer> choices = getNeighbors(pos);
        Collections.shuffle(choices);
        int dir = choices.get(0);
        pos.x += dir==WEST?-1:dir==EAST?1:0;
        pos.y += dir==NORTH?-1:dir==SOUTH?1:0;
    }

    boolean delete(int x, int y, int dir){
        if((edges[x][y] & dir) != dir)
            return false;
        edges[x][y] -= dir;
        if(dir == NORTH)
            if(y>0) edges[x][y-1] -= SOUTH;
        if(dir == SOUTH)
            if(y+1<SIZE) edges[x][y+1] -= NORTH;
        if(dir == EAST)
            if(x+1<SIZE) edges[x+1][y] -= WEST;
        if(dir == WEST)
            if(x>0) edges[x-1][y] -= EAST;
        return true;
    }

    List<Integer> getNeighbors(Point p){
        if(p.x==SIZE || p.y==SIZE){
            System.out.println("wtf");
            System.exit(0);
        }
        List<Integer> choices = new ArrayList<Integer>();
        if((edges[p.x][p.y] & NORTH) == NORTH)
            choices.add(NORTH);
        if((edges[p.x][p.y] & SOUTH) == SOUTH)
            choices.add(SOUTH);
        if((edges[p.x][p.y] & EAST) == EAST)
            choices.add(EAST);
        if((edges[p.x][p.y] & WEST) == WEST)
            choices.add(WEST);
        return choices;
    }

    final static int NORTH=1,EAST=2,SOUTH=4,WEST=8;
}
Geobit
sumber
Saya hanya memperhatikan bahwa ia harus pergi dari bot / kiri-> atas / kanan, sedangkan milik saya pergi dari bot / kanan-> atas / kiri. Saya bisa mengubahnya jika itu benar-benar penting, tapi ...
Geobits
Ini sangat bagus dan merupakan solusi dinamis pertama yang saya pikir. Saya tertarik bahwa jalur Anda belum cukup lama seperti yang statis.
Jika dengan "tidak cukup lama" yang Anda maksud ~ 1/3 selama satu dan ~ 36x selama yang lain? : P
Geobits
3

188k, dengan 2 jalur

Entri terbaik semua tampaknya mengambil pendekatan menghasilkan 2 jalur, dan kemudian memotong satu ketika mabuk mendekati akhir jalan. Saya tidak berpikir saya bisa mengalahkan entri justhalf, tetapi saya bertanya-tanya: Mengapa 2 jalur? Kenapa tidak 3, atau 5, atau 20?

TL; DR : 2 jalur tampaknya optimal

Jadi saya melakukan percobaan. Berdasarkan kerangka Stretch Maniac, saya menulis entri untuk menguji berbagai jumlah jalur. Anda dapat mengubah featureSizeparameter untuk memvariasikan jumlah jalur. A featureSizedari 20 memberi 1 jalur, 10 memberi 2 jalur, 7 memberi 3, 5 memberi 4, dan seterusnya.

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.ThreadLocalRandom;

public class Walker {
    final int width,height;
    int x,y; //walker's position (does anyone else keep thinking about zombies?!?)
    final int dX,dY; //destination
    final int featureSize;
    Set<Edge> pathsNoLongerAvailable = new HashSet<>();
    Set<Edge> previouslyTraveled = new HashSet<>();
    int stepCount = 0;
    private final BitSet remainingExits;

    public static void main(String[]args){
        int side = 20;
        Walker walker = null;
        int total = 0;
        int featureSize = 10;
        double count = 1000;
        for(int i=0; i<count; i++){
            walker = new Walker(0,0,side,side,side-1,side-1, featureSize);
            total += walker.stepCount;
            System.out.println("Iteration "+i+": "+walker.stepCount);
        }
        System.out.printf("Average: %.3f\n", total/count);
        walker.printPath();
    }

    public Walker(int startingX,int startingY, int Width, int Height, int destinationX, int destinationY, int featureSize){
        width = Width;
        height = Height;
        dX = destinationX;
        dY = destinationY;
        x=startingX;
        y=startingY;
        this.featureSize = featureSize;

        deleteBars();

        remainingExits = new BitSet();
        for (int yy = 0; yy < height; yy++) {
            if (!pathsNoLongerAvailable.contains(new Edge(width - 2, yy, width - 1, yy))) {
                remainingExits.set(yy);
            }
        }

        while(!walk()){
            if (x == width - 2
                    && remainingExits.get(y)
                    && remainingExits.cardinality() > 1) {
                deletePath(x, y, x + 1, y);
                remainingExits.set(y, false);
            }
        }
    }

    private void deleteBars() {
        for (int xx = 0; xx < width - 1; xx++) {
            for (int yy = 0; yy < height / featureSize + 1; yy++) {
                if (xx != 0) deletePath(xx, featureSize * yy + featureSize - 1, xx, featureSize * yy + featureSize);
                boolean parity = xx % 2 == 0;
                if (yy == 0) parity ^= true; // First path should be inverted
                for (int i = 0; i < featureSize && featureSize * yy + i < height; i++) {
                    if (i == 0 && !parity) continue;
                    if ((i == featureSize - 1 || featureSize * yy + i == height - 1) && parity) continue;
                        deletePath(xx, featureSize * yy + i, xx + 1, featureSize * yy + i);
                }
            }
        }
    }

    public void printPath(){
        for(int i=0; i<width-1; i++){
            if(!pathsNoLongerAvailable.contains(new Edge(i,height-1,i+1,height-1))){
                System.out.print(" _");
            } else {
                System.out.print("  ");
            }
        }
        System.out.println();
        for(int i=height-2; i>=0; i--){
            for(int j=0; j<2*width-1; j++){
                if(j%2==0){
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2,i+1))){
                        System.out.print("|");
                    } else {
                        System.out.print(" ");
                    }
                } else {
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2+1,i))){
                        System.out.print("_");
                    } else {
                        System.out.print(" ");
                    }
                }
            }
            System.out.println();
        }
    }

    public boolean walk(){
        ArrayList<int[]> possibleMoves = new ArrayList<int[]>();
        if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
            possibleMoves.add(new int[]{-1,0});
        }
        if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
            possibleMoves.add(new int[]{1,0});
        }
        if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
            possibleMoves.add(new int[]{0,-1});
        }
        if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
            possibleMoves.add(new int[]{0,1});
        }
        int random = ThreadLocalRandom.current().nextInt(possibleMoves.size());
        int[] move = possibleMoves.get(random);
        previouslyTraveled.add(new Edge(x,y,x+move[0],y+move[1]));
        x+=move[0];
        y+=move[1];
        stepCount++;
        if(x==dX && y == dY){
            return true;
        } else {
            return false;
        }
    }

    public boolean isSolvable(){
        Set<Point> reachable = new HashSet<>();
        Queue<Point> next = new LinkedList<>();
        next.offer(new Point(x,y));
        reachable.add(new Point(x,y));
        while(next.size()>0){
            Point cur = next.poll();
            int x = cur.x;
            int y = cur.y;
            ArrayList<Point> neighbors = new ArrayList<>();
            if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
                neighbors.add(new Point(x-1, y));
            }
            if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
                neighbors.add(new Point(x+1, y));
            }
            if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
                neighbors.add(new Point(x, y-1));
            }
            if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
                neighbors.add(new Point(x, y+1));
            }
            for(Point neighbor: neighbors){
                if(!reachable.contains(neighbor)){
                    if(neighbor.compareTo(new Point(dX, dY))==0){
                        return true;
                    }
                    reachable.add(neighbor);
                    next.offer(neighbor);
                }
            }
        }
        return false;
    }

    public boolean hasBeenWalked(int x1, int y1, int x2, int y2){
        return previouslyTraveled.contains(new Edge(x1, y1, x2, y2));
    }

    public boolean hasBeenWalked(Edge edge) {
        return previouslyTraveled.contains(edge);
    }

    public void deletePath(int startX, int startY, int endX, int endY){
        Edge toAdd = new Edge(startX,startY,endX,endY);
        if(hasBeenWalked(toAdd)){
            System.out.println("Edge already travelled!");
            return;
        }
        pathsNoLongerAvailable.add(toAdd);
        if(!isSolvable()){
            pathsNoLongerAvailable.remove(toAdd);
            System.out.println("Invalid deletion!");
        }
    }

    public static class Edge implements Comparable<Edge>{
        Point start, end;

        public Edge(int x1, int y1, int x2, int y2){
            start = new Point(x1, y1);
            end = new Point(x2, y2);
            if(start.compareTo(end)>0){
                Point tmp = end;
                end = start;
                start = tmp;
            }
        }

        @Override
        public int compareTo(Edge o) {
            int result = start.compareTo(o.start);
            if(result!=0) return result;
            return end.compareTo(o.end);
        }

        @Override
        public String toString() {
            return start.toString() + "-" + end.toString();
        }

        @Override
        public int hashCode() {
            int hash = 7;
            hash = 83 * hash + Objects.hashCode(this.start);
            hash = 83 * hash + Objects.hashCode(this.end);
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Edge other = (Edge) obj;
            if (!Objects.equals(this.start, other.start)) {
                return false;
            }
            if (!Objects.equals(this.end, other.end)) {
                return false;
            }
            return true;
        }


    }

    static class Point implements Comparable<Point>{
        int x,y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        public int compareTo(Point o){
            int result = Integer.compare(x, o.x);
            if(result!=0) return result;
            result = Integer.compare(y, o.y);
            if(result!=0) return result;
            return 0;
        }
        @Override
        public String toString() {
            return "(" + x + "," + y + ")";
        }

        @Override
        public int hashCode() {
            int hash = 7;
            hash = 23 * hash + this.x;
            hash = 23 * hash + this.y;
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Point other = (Point) obj;
            if (this.x != other.x) {
                return false;
            }
            if (this.y != other.y) {
                return false;
            }
            return true;
        }


    }
}

Ada beberapa optimisasi yang bisa saya lakukan tetapi belum, dan itu tidak mendukung tipu daya adaptif yang hanya digunakan.

Bagaimanapun, inilah hasil untuk berbagai featureSizenilai:

20 (1 path):  156284 
10 (2 paths): 188553
7 (3 paths):  162279
5 (4 paths):  152574
4 (5 paths):  134287
3 (7 paths):  118843
2 (10 paths): 94171
1 (20 paths): 64515

Dan inilah peta dengan 3 jalur:

 _   _   _   _   _   _   _   _   _    
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| |_| |_| |_| |_| |_| |_| |_| |_| |_| |
|_   _   _   _   _   _   _   _   _   _|
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| |_| |_| |_| |_| |_| |_| |_| |_| |_| |
|  _   _   _   _   _   _   _   _   _  |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
|_| |_| |_| |_| |_| |_| |_| |_| |_| | |
James_pic
sumber
Terima kasih untuk ini. Tampaknya semua uang ada dalam tipuan adaptif sekarang :)
Mengapa Anda memotong jalan di bagian bawah? Anda dapat memotong jalan antara jalan yang lebih rendah dan jalan tengah untuk skor yang lebih baik, saya pikir.
justhalf
@ justhalf Ya, saya berharap begitu. Saya memutuskan untuk tidak, karena itu akan membuat kode lebih rumit, dan itu tidak akan menjadi entri yang menang.
James_pic
1
Tiga lintasan (dengan asumsi lintasan 3 optimal) akan rata-rata sama dengan lintasan tunggal: biarkan Nlintasan panjang (yaitu n^2-1), lintasan tunggal rata-rata akan memerlukan N^2gerakan, sedangkan tiga lintasan (N/3)^2 + (2N/3)^2 + (2N/3)^2 = N^2ditambah beberapa nilai yang relatif kecil, sehingga tiga jalur tidak memiliki keuntungan signifikan atas jalur tunggal, apalagi jalur ganda. (Perhitungan didasarkan pada hasil probabilitas yang menyatakan bahwa gerakan acak pada lintasan 1-D Nmembutuhkan N^2gerakan rata-rata dari satu ujung ke ujung lainnya.)
justhalf
@ justhalf Bagus. Saya sedang berjuang untuk mengajukan argumen prinsip pertama yang baik tentang mengapa saya adalah yang terbaik, tetapi ini berhasil.
James_pic
2

131r (20x20)

Upaya pertama saya adalah untuk menghapus semua tepi horisontal kecuali baris atas dan bawah, maka setiap kali walker mencapai bagian bawah kolom saya akan menghapus tepi di depannya, sampai dia mengunjungi bagian bawah setiap kolom dan akhirnya akan dapat mencapai pintu keluar. Ini menghasilkan rata-rata 1/8 langkah dari pendekatan berjalan 1d @ PeterTaylor.

Selanjutnya saya memutuskan untuk mencoba sesuatu yang sedikit lebih berputar-putar. Saya telah membagi labirin menjadi serangkaian chevron berongga bersarang, dan mengharuskannya untuk melintasi perimeter setiap chevron setidaknya 1,5 kali. Ini memiliki waktu rata-rata sekitar 131 ribu langkah.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <math.h>

#define DEBUG 0
#define ROUNDS 10000

#define Y 20
#define X 20
#define H (Y*2+1)
#define W (X*2+1)

int maze[H][W];
int scores[ROUNDS];

int x, y;

void print_maze(){
    char line[W+2];
    line[W+1]=0;
    for(int row=0;row<H;row++) {
        for(int col=0;col<W;col++) {
            switch(maze[row][col]) {
                case 0:
                    line[col]=' ';
                    break;
                case 1:
                    line[col]=row%2?'-':'|';
                    break;
                case 9:
                    line[col]=(row==y*2+1&&col==x*2+1)?'@':' ';
                    break;
            }
        }
        line[W]='\n';
        printf("%s",line);
    }
    printf("%d %d\n",y,x);
}

int main(){
    srand (time(NULL));
    long long total_turns = 0;
    for(int round=0;round<ROUNDS;round++) {
        for (int r=0;r<H;r++) {
            for (int c=0;c<W;c++) {
                if (r==0 || r==H-1 || c==0 || c==W-1) maze[r][c]=0; // edges
                else if (r%2) { // rows with cells and E/W paths
                    if (c%2) maze[r][c] = 9; // col with cells
                    else if (r==1 || r==H-2) maze[r][c]=1; // E/W path on N/Smost row
                    else if (c>r) maze[r][c]=1; // E/W path on chevron perimeter
                    else maze[r][c]=0; // cut path between cols
                } else { // rows with N/S paths
                    if (c%2==0) maze[r][c] = 0; // empty space
                    else if (c==1 || c==W-2) maze[r][c]=1; // N/S path on E/Wmost row
                    else if (r>c) maze[r][c]=1; // N/S path on chevron perimeter
                    else maze[r][c]=0;
                }
            }
        }
        int progress = 0;
        int first_cut = 0;
        x=0;
        y=0;
        if(DEBUG) print_maze();
        long long turn = 0;
        while (x!=X-1||y!=Y-1) {
            if(DEBUG) std::cin.ignore();
            turn++;
            int r = y*2+1;
            int c = x*2+1;
            int exits = maze[r-1][c] + maze[r][c+1] + maze[r+1][c] + maze[r][c-1];
            int exit_choice = -1;
            do {
                if (rand()%exits == 0) {
                    exit_choice = exits;
                    break;
                } else {
                    exits--;
                }
            }while(exits);
            int dx=0, dy=0;
            --exits;
            if (maze[r-1][c]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = -1;
                    dx = 0;
                }
            }
            if (maze[r][c+1]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = 0;
                    dx = 1;
                }
            }
            if (maze[r+1][c]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = 1;
                    dx = 0;
                }
            }
            if (maze[r][c-1]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = 0;
                    dx = -1;
                }
            }
            x+=dx;
            y+=dy;
            if (first_cut==0) {
                if(x==X-1 && y==progress*2+1) {
                    first_cut = 1;
                    maze[y*2+2][x*2+1]=0;
                }
                if(y==Y-1 && x==progress*2+1) {
                    first_cut = 2;
                    maze[y*2+1][x*2+2]=0;
                }
            }
            else if (first_cut==1) {
                if (y==Y-1 && x==progress*2) {
                    maze[y*2+1][x*2+2]=0;
                    progress++;
                    first_cut=0;
                }
                else if (y==Y-2 && x==progress*2+1) {
                    maze[y*2+2][x*2+1]=0;
                    progress++;
                    first_cut=0;
                }
            }
            else if (first_cut==2) {
                if (x==X-1 && y==progress*2) {
                    maze[y*2+2][x*2+1]=0;
                    progress++;
                    first_cut=0;
                }
                else if (x==X-2 && y==progress*2+1) {
                    maze[y*2+1][x*2+2]=0;
                    progress++;
                    first_cut=0;
                }
            }
            if(DEBUG) print_maze();
        }
        // printf("turns:%lld\n",turn);
        scores[round] = turn;
        total_turns += turn;
    }
    long long avg = total_turns/ROUNDS;
    printf("average: % 10lld\n",avg);
    long long var = 0;
    for(int r=0;r<ROUNDS;r++){
        var += (scores[r]-avg)*(scores[r]-avg);
    }
    var/=ROUNDS;
    // printf("variance: %lld\n",var);
    int stddev=sqrt(var);
    printf("stddev:  % 10d\n",stddev);

}
Sparr
sumber
0

Tidak melakukan apapun

Karena pria itu bergerak secara acak, orang mungkin berpikir bahwa menghapus simpul apa pun hanya akan meningkatkan peluangnya untuk pulang dalam jangka panjang.

Pertama, mari kita lihat kasus satu dimensi, ini dapat dicapai dengan menghapus node sampai Anda berakhir dengan jalan berlekuk, tanpa tenggat waktu atau siklus, yang mengunjungi (hampir) setiap titik jaringan. Pada N x Nkisi, panjang maksimal jalur tersebut adalah L = N*N - 2 + N%2 (98 untuk kisi 10x10). Berjalan di sepanjang jalan dapat digambarkan oleh matriks transisi seperti yang dihasilkan oleh T1d. matriks transisi

(Asimetri yang sedikit membuat sulit untuk menemukan solusi analitis, kecuali untuk matriks yang sangat kecil atau tidak terbatas, tetapi kami memperoleh solusi numerik lebih cepat daripada yang dibutuhkan untuk mendiagonisasi matriks itu).
Vektor state memiliki satu 1di posisi awal dan setelahK langkah (T1d**K) * statememberi kita distribusi probabilitas berada pada jarak tertentu dari awal (yang setara dengan rata-rata atas semua2**K jalan yang mungkin di sepanjang jalan!)

Menjalankan simulasi untuk 10*L**2langkah - langkah dan menyimpan elemen terakhir dari vektor keadaan setelah setiap langkah yang memberi kita kemungkinan berhasil mencapai tujuan setelah sejumlah langkah tertentu - distribusi probabilitas kumulatif cd(t). Membedakannya memberi kita kemungkinan puntuk mencapai tujuan tepat pada waktu tertentu. Untuk menemukan waktu rata-rata yang kami integrasikan, t*p(t) dt
Waktu rata-rata untuk mencapai tujuan adalah proporsional L**2dengan faktor yang berjalan sangat cepat ke 1. Deviasi standar hampir konstan pada sekitar 79% dari waktu rata-rata.
Grafik ini menunjukkan waktu rata-rata untuk mencapai tujuan untuk panjang jalur yang berbeda (sesuai dengan ukuran kisi 5x5 hingga 15x15) masukkan deskripsi gambar di sini

Di sini terlihat seperti kemungkinan mencapai tujuan. Kurva kedua terlihat terisi karena pada setiap timestep ganjil posisi ganjil dan karenanya tidak dapat mencapai tujuan. masukkan deskripsi gambar di sini

Dari situ kita dapat melihat bahwa strategi jalur ganda seimbang bekerja paling baik di sini. Untuk grid yang lebih besar, di mana biaya overhead untuk membuat lebih banyak jalur dapat diabaikan dibandingkan dengan ukurannya, kita mungkin lebih baik meningkatkan jumlah jalur, mirip dengan cara Peter Taylor menggambarkannya, tetapi menjaga panjangnya seimbang

Bagaimana jika kita tidak menghapus node sama sekali?

Maka kita akan memiliki dua kali lebih banyak walkable node, ditambah empat kemungkinan arah, bukan dua. Tampaknya itu membuatnya sangat tidak mungkin untuk pergi ke mana pun. Namun, simulasi menunjukkan sebaliknya, setelah hanya 100 langkah pada grid 10x10, pria tersebut kemungkinan besar akan mencapai tujuannya, jadi menjebaknya di pulau-pulau adalah upaya yang sia-sia, karena Anda berdagang N**2jalur berliku panjang yang potensial dengan waktu penyelesaian rata-rata N**4untuk sebuah pulau yang dilewati secara N**2bertahap

probabilitas berjalan di grid 2d

from numpy import *
import matplotlib.pyplot as plt

def L(N): # maximal length of a path on an NxN grid
    return N*N - 2 + N%2

def T1d(N): # transition along 1d path
    m = ( diag(ones(N-1),1) + diag(ones(N-1),-1) )/2.
    m[1,0] = 1
    m[-2,-1] = 0
    m[-1,-1] = 1
    return m

def walk(stepmatrix, state, N):
    data = zeros(N)
    for i in xrange(N):
        data[i] = state[-1]
        state = dot(stepmatrix, state)
    return data

def evaluate(data):
    rho = diff(data)/data[-1]
    t = arange(len(rho))
    av = sum(rho*t)
    stdev = sum((t-av)**2 * rho)**.5
    print 'average: %f\nstd: %f'%(av, stdev)
    return rho, av, stdev

gridsize = 10
M = T1d(L(gridsize))
initpos = zeros(L(gridsize))
initpos[0] = 1
cd = walk(M, initpos, L(gridsize)**2*5)

plt.subplot(2,1,1)
plt.plot(cd)
plt.title('p of reaching the goal after N steps')
plt.subplot(2,1,2)
plt.plot(evaluate(cd)[0])
plt.title('p of reaching the goal at step N')
plt.show()


''' 
# uncomment to run the 2D simulation
# /!\ WARNING /!\ generates a bunch of images, dont run on your desktop

def links(k,n):
    x = [k-n, k+n]
    if k%n != 0: x.append(k-1)
    if k%n != n-1: x.append(k+1)
    x = [i for i in x if 0<= i <n*n]
    return x

N = 10 # gridsize    

MM = zeros((N*N, N*N)) # build transition matrix
for i in range(N*N):
    temp = links(i,N)
    for j in temp: MM[i,j] = 1./len(temp)
MM[:,-1] = zeros(N*N)
MM[-1,-1] = 1

pos = zeros(N*N)
pos[0] = 1
for i in range(N*N):
    plt.imsave('grid_%.2d'%i, kron(pos.reshape((N,N)), ones((10,10))), cmap='gray')
    pos = dot(MM, pos)
'''
DenDenDo
sumber
+1 untuk upaya dan grafik yang bagus. Tetapi ini tidak menjawab pertanyaan, dan dua kata pertama bertentangan dengan kesimpulan analisis Anda. Dan, Anda benar-benar harus memberi label sumbu grafik Anda. Untuk ukuran grid apa grafik probabilitas Anda berlaku?
justhalf
Gambar-gambar indah tetapi saya tidak yakin Anda memiliki pertanyaan yang benar. Misalnya "Karena pria itu bergerak secara acak, orang mungkin berpikir bahwa menghapus simpul apa pun hanya akan meningkatkan peluangnya untuk pulang dalam jangka panjang." 1) pria itu akan selalu sampai di rumah akhirnya di bawah aturan yang ditetapkan sehingga ini tampaknya tidak relevan dan 2) kami menghapus tepi bukan node.