Perbedaan antara heuristik dan algoritma aproksimasi?

Saya punya masalah dengan situasi berikut.

Saya memiliki dua array angka seperti ini:

index/pos     0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15 
Array 1(i):   1   2   3   4   7   5   4   3   7   6   5   1   2   3   4   2
Array 2(j):   4   4   8  10  10   7   7  10  10  11   7   4   7   7   4

sekarang anggap array kedua sangat sulit untuk dihitung tetapi saya perhatikan bahwa jika saya tambahkan

A [i] + A [i + 1]

dalam array 1 saya mendapatkan nomor yang sangat dekat dengan angka A [j] dalam array 2.

Apakah solusi saya heuristik atau perkiraan?
Jika saya punya alasan untuk percaya bahwa saya tidak akan pernah melampaui nilai A [j] dengan + -x dengan algoritma ini dan dapat membuktikannya, akankah solusi saya menjadi heuristik atau perkiraan?

Apakah ada literatur yang berkaitan dengan pertanyaan heuristik vs perkiraan untuk masalah kelas P di mana solusi dapat dicapai dalam waktu polinomial tetapi inputnya terlalu besar untuk algoritma waktu poli menjadi praktis.

Terima kasih

approximation heuristics pengguna6697
sumber

Pertama-tama Anda perlu menentukan apa yang ingin Anda perkirakan untuk menilai apakah pendekatan Anda adalah perkiraan.

Dan

Apa sebenarnya masalah pengoptimalan yang Anda coba selesaikan? Setelah itu diketahui maka jika Anda membuktikan batas heuristik Anda menjadi perkiraan. Selain itu, satu-satunya (klasik, yaitu, non-streaming) masalah dalam P yang memiliki algoritma aproksimasi (yang saya tahu) adalah algoritma max-flow.

Nicholas Mancuso

ok jadi hal yang ingin saya hitung adalah angka-angka dalam array kedua. tetapi ini terlalu lama, namun saya menemukan bahwa jika saya menambahkan dua nilai berturut-turut dari array 1 bersama-sama saya mendapatkan sesuatu yang ok dan saya dapat membuktikan bahwa estimasi akan selalu dalam + -x. awal alg untuk komputasi A [j] adalah O (n ^ 100)

user6697

Saya mengerti Anda ingin menghitung angka dalam array kedua, tetapi apa rumusan masalah optimasi. Diberikan X hitung Y di bawah batasan Z. Mengatakan Anda ingin menghitung beberapa fungsi arbitrer tidak membantu.

Nicholas Mancuso

Solusi Anda adalah contoh sempurna heuristik!

Björn Lindqvist

Jawaban:

Sebuah heuristik pada dasarnya adalah sebuah firasat, yaitu, kasus Anda menggambarkan ( "Saya melihat itu dekat", Anda tidak memiliki bukti itu begitu) adalah heuristik. Seperti memecahkan masalah salesman keliling dengan mulai dari titik acak dan pergi ke yang terdekat belum mengunjungi setiap langkah. Ini adalah ide yang masuk akal , yang seharusnya tidak memberikan solusi yang terlalu buruk. Dalam hal ini, dapat ditunjukkan bahwa itu tidak selalu memberikan solusi yang baik.

Sebuah algoritma pendekatan biasanya dipahami untuk memberikan solusi perkiraan, dengan beberapa jenis jaminan kinerja (yaitu, itu memecahkan TSP, dan total biaya tidak pernah off oleh lebih dari faktor 2, atau bahkan lebih baik, itu memecahkan TSP dan, tergantung pada <beberapa parameter yang dapat bervariasi> solusinya tidak pernah lebih buruk daripada optimal oleh lebih dari satu faktor $1 + \epsilon$ dimana $\epsilon$ tergantung pada <parameter>).

vonbrand
sumber

Anda menggunakan sampel yang buruk, TSP sulit diperkirakan, sehingga tidak ada PTAS untuk TSP juga tidak ada 2 perkiraan untuk TSP mudah ditampilkan jika ada waktu polinomial 2-perkiraan untuk TSP ada algoritma waktu polinomial untuk menyelesaikan masalah siklus hamiltonian , Saya pikir maksud Anda metrik TSP yang merupakan kasus khusus tetapi masih tidak ada PTAS dalam kasus ini (dan terbukti tidak mungkin untuk memiliki PTAS kecuali P = NP). Saya akan menyarankan untuk memilih tempat sampah untuk membicarakan hal ini. (atau masalah sederhana lainnya).

@ SaeedAmiri, itu hanya untuk tujuan ilustrasi. Mungkin bukan contoh terbaik (seperti yang Anda sebutkan), tetapi masalahnya mudah dipahami. Terima kasih atas komentarnya.

vonbrand

Jadi jika Anda mengerti ini adalah contoh yang salah mengapa Anda tidak memperbaikinya?

@ SaeedAmiri saya pikir itu baik-baik saja. Ingat kita tidak tahu kalau misalnya

P = N P

$\mathsf{P}=\mathsf{NP}$ , di mana kekerasan pendekatan dapat didasarkan pada.

Juho

@ Juho, sepengetahuan saya benar-benar salah bahkan dengan mengetahui bahwa kita tidak tahu

P = N P

$P=NP$ , titik utama adalah mungkin dalam arah yang dihormati (

P \neq N P

$P\not =NP$ ), Jadi kita tidak boleh menggunakan sampel yang buruk, kita harus menggunakan sampel yang kita tahu mereka benar terlepas dari hal-hal yang tidak kita ketahui.

Anda dapat melihat jawaban yang sangat menarik tentang Heuristik di Wikipedia ini:

"heuristik adalah teknik yang dirancang untuk memecahkan masalah lebih cepat ketika metode klasik terlalu lambat. Tujuan heuristik adalah menghasilkan solusi yang cukup cepat yang cukup baik untuk menyelesaikan masalah yang ada."

Heuristik dapat berasal dari teori atau pengalaman eksperimental, tetapi algoritma aproksimasi memiliki dasar teori yang kuat (solusi yang dapat dibuktikan).

Reza
sumber

Adapun pertanyaan terakhir Anda, tidak ada teori terpisah untuk algoritma aproksimasi untuk masalah yang dapat dipecahkan dalam waktu polinomial. Bahkan, mungkin itu $\mathsf{P}=\mathsf{NP}$ . Beberapa contoh algoritma aproksimasi untuk masalah dalam $\mathsf{P}$ termasuk algoritma untuk aljabar linear numerik dan geometri komputasi. Lihat pertanyaan Algoritme pendekatan untuk masalah dalam P untuk lebih lanjut.

Juho
sumber