Bagaimana nilai acak dapat disebarkan dengan probabilitas tertentu?

Untuk AI, saya menggunakan nilai acak untuk memutuskan tindakan mana yang harus dilakukan selanjutnya (hanya jika tidak ada aturan yang harus dilakukan). Beberapa tindakan harus dipilih lebih sering dibandingkan tindakan lainnya.

Idenya adalah untuk mendefinisikan sekelompok probabilitas dan memilih suatu tindakan dari kemungkinan 2 dua kali lebih sering daripada tindakan dengan 1, tindakan 4 dengan probabilitas lima kali lebih tinggi.

action prob
0         1
1         2 (twice as often than 1)
2         2
3         2
4         5 (5 times morer often than 1)

Apakah ada algoritma terkenal untuk perilaku ini atau pendekatan yang lebih matematis?

Implementasi pengujian saya agak canggung. Saya lebih suka menghindari lingkaran dalam.

public static void main(String[] args) {
    int[] counts = new int[5];
    int[] props = { 1 ,2 ,2 ,2 ,5 };
    int sum = 0;
    for (int i = 0; i < props.length ; i++) {
        sum += props[i];
    }
    for ( int i = 0 ; i < 100 ; i++ ) {
        int rand = (int) (Math.random() * sum);
        for ( int j = 0 ; j < props.length ; j++ ) {
            if ( rand - props[j] <= 0 ) {
                counts[j] = counts[j] + 1;
            }
        }
    }
    for ( int j = 0 ; j < props.length ; j++ ) {
        System.out.println( "count " + j + "=" + counts[j] );
    }
}

Bergantung pada pengujian yang dijalankan, ini menghasilkan hasil seperti:

count 0=14
count 1=25
count 2=25
count 3=25
count 4=50

java algorithm math probability language-agnostic
person stacker    schedule 16.08.2015    source sumber

Jawaban (2)


arrow_upward
2
arrow_downward

Anda ingin menyelesaikan persamaan:

p0 + p1 + p2 + p3 + p4 = 1
p0 = p
p1 = 2p
p2 = 2p
p3 = 2p
p4 = 5p

Ini adalah sekumpulan persamaan linier dan dapat diselesaikan dengan mudah menggunakan aljabar linier.

Dalam contoh ini:

p + 2p + 2p + 2p + 5p = 1
12p = 1
p = 1/12
p0 = 1/12
p1 = p2 = p3 = 2/12
p5 = 5/12

Anda dapat menggunakan satu nomor yang terdistribusi secara merata di [0,1) x untuk memilih peristiwa mana yang akan terjadi dengan mengatur array:

aux[0] = 0
aux[i] = aux[0] + p_{i-1}

jadi dalam contoh Anda:

aux = [0,1/12,3/12,5/12,7/12,1]

Kemudian, ambil nilai untuk x, dan lakukan pencarian biner pada i untuk menemukan nilai terdekat yang lebih tinggi dari x, dan itulah kejadian Anda.

person amit    schedule 16.08.2015

arrow_upward
3
arrow_downward

Bagaimana dengan array dengan nilai-nilai, dengan nilai-nilai yang lebih umum muncul lebih sering:

int[] actions = {0, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4} // 12 values.

Anda kemudian bisa melakukannya

int action = actions[Math.random() * actions.length]

untuk mendapatkan tindakan acak berbobot.

person saagarjha    schedule 16.08.2015
comment
Saya pikir mengacak elemen actions akan memberikan distribusi tertimbang yang lebih baik. - person John; 16.08.2015
comment
Tidak masalah, karena Math.random() terdistribusi secara merata, bukan? Tentu saja bisa jika Anda mau. - person saagarjha; 16.08.2015
comment
Tergantung pada seberapa tepat acak yang Anda butuhkan. Ini sebenarnya tidak salah, dan generator kongruensial Linear juga merupakan pilihan yang paling tepat. Anda mungkin menganggap ini menarik: stackoverflow.com/ pertanyaan/453479/seberapa baik-java-util-random - person John; 16.08.2015
comment
Mungkin agak rewel :) Saya memberi suara positif pada jawabannya. - person John; 16.08.2015
comment
Bagaimana rencana Anda untuk mengacak actions? Bukankah Anda harus menggunakan Math.random()? - person saagarjha; 16.08.2015
comment
Harus, tidak. Akankah aku ? Mungkin. Saya mengerti tujuan Anda dengan ini, tetapi saran saya adalah jangan menempatkan beban yang sama berdekatan satu sama lain, itu saja. - person John; 16.08.2015