Memulihkan titik yang disematkan dari grafik dengan tepi tertimbang oleh jarak titik

Misalkan saya memberi Anda grafik tanpa arah dengan tepi tertimbang, dan memberi tahu Anda bahwa setiap node sesuai dengan titik dalam ruang 3d. Setiap kali ada tepi antara dua node, berat tepi adalah jarak antara titik.

Tujuan Anda adalah merekonstruksi posisi relatif dari titik-titik tersebut, hanya diberikan jarak yang tersedia (diwakili oleh bobot tepi). Misalnya, jika saya memberi Anda , maka Anda tahu titik adalah simpul dari tetrahedron. Anda tidak tahu di mana itu relatif terhadap asal, atau orientasinya, atau jika sudah dicerminkan, tetapi Anda bisa tahu itu tetrahedron.$d_{0,1} = d_{0,2} = d_{0,3} = d_{1,2} = d_{1,3} = d_{2,3} = 1$

Secara umum, masalahnya mudah jika saya memberi Anda semua panjang tepi. titik menjadi , lalu pilih titik tetangga dan letakkan di , lalu tetangganya yang biasa akan di-triangulasi ke XY pesawat, maka tetangga umum terakhir akan triangulasi ke dalam ruang setengah dan memecah simetri yang tersisa (dengan asumsi Anda tidak mengambil titik degenerasi). Anda dapat menggunakan keempat poin itu untuk melakukan triangulasi semua poin yang tersisa. ( 0 , 0 , 0 ) p 1 ( d 0 , 1 , 0 , 0 ) p 2 p 3 z > $p_0$$(0,0,0)$$p_1$$(d_{0,1},0,0)$$p_2$$p_3$$z > 0$

Di sisi lain, ketika beberapa panjang tepi hilang, tidak mungkin memulihkan embedding. Sebagai contoh, jika ada titik yang memutus grafik ketika dipotong, maka dua komponen itu akan terpisah jika dihapus dapat berayun relatif satu sama lain.

Yang menimbulkan pertanyaan:

• Seberapa mahal untuk menemukan solusi?
• Bagaimana Anda menentukan apakah suatu solusi unik, hingga terjemahan / rotasi / mirroring? Apakah 3-keterhubungan cukup? Perlu?
• Kondisi apa yang membuat masalah itu sepele?
• Jika saya tidak menjanjikan bobot tepi sebenarnya sesuai dengan 3d distance point sin, seberapa mahalkah itu untuk menentukan apakah embedding dimungkinkan sama sekali?

Salah satu pendekatan algoritmik untuk memecahkan masalah ini: perlakukan ini sebagai satu set node, dihubungkan oleh pegas, lalu biarkan mereka mengendap / rileks.

Setiap tepi sesuai dengan pegas; jika jarak antara titik v dan w seharusnya d v , w , maka pegas dipilih sehingga idealnya ingin menjadi panjang d v , w (bisa lebih lama atau lebih pendek, tetapi biaya energi ini). Kami sekarang ingin menyelesaikan satu set posisi yang meminimalkan total energi. Misalkan setiap titik v ditempatkan pada titik x v ∈ R 3 . Maka energi total dari pengaturan ini akan menjadi$(v,w)$$v$$w$$d_{v,w}$$d_{v,w}$$v$$x_v \in \mathbb{R}^3$

Di sini 's diberikan (mereka adalah bobot di tepi), dan kami ingin memecahkan untuk x v ' s (mereka adalah koordinat titik-titik).$d_{v,w}$$x_v$

Kita dapat menyelesaikan untuk pengaturan yang meminimalkan energi total ini. Pengaturan ini kemudian memberikan kandidat yang masuk akal untuk posisi poin. Ini adalah masalah optimisasi, dan ada teknik standar untuk menyelesaikan masalah optimasi semacam ini. Lihat, misalnya, artikel Network Solutions oleh Erica Klarreich.$x$

Saya tidak berpikir ada jaminan ini akan memberikan solusi yang diinginkan benar. Mungkin saja masalah pengoptimalan mungkin diselesaikan pada optimum berbeda yang tidak mencerminkan pengaturan aktual dari poin yang Anda cari. Namun, jika grafik Anda cukup padat, saya curiga mungkin sering bekerja dan memberi Anda solusi yang diinginkan.

Catatan Kaki: Tentu saja bahkan dalam kasus terbaik kita hanya dapat menyelesaikan masalah ini hingga terjemahan, rotasi, dan refleksi karena transformasi tersebut menjaga semua jarak. Dengan demikian, Anda tidak dapat mengharapkan solusi yang unik - tetapi Anda mungkin berharap bahwa solusi tersebut unik hingga terjemahan, rotasi, dan refleksi.

Akhirnya, ada banyak pekerjaan pada grafik embedding ke dalam ruang, sambil meminimalkan distorsi dari embedding. Itu sangat terkait; Anda pada dasarnya meminta nol-distorsi menanamkan ke ℓ 2 . Dengan demikian, teknik yang dikembangkan dalam konteks itu mungkin berguna untuk masalah Anda juga. Biasanya, pekerjaan itu berfokus pada menemukan penyisipan dengan distorsi rendah, karena pekerjaan itu berfokus pada kasus di mana tidak ada penyematan sempurna yang membuat semua jarak cocok dengan tepat, jadi alih-alih mencari solusi distorsi rendah (yang merupakan tempat di mana sebagian besar jarak tepi cocok dengan sangat baik) - sehingga pekerjaan difokuskan pada masalah yang sedikit berbeda. Namun, mungkin saja teknik mereka juga efektif dalam situasi Anda. Ini patut dicoba.$\ell_2$$\ell_2$

Masalahnya adalah NP-Complete . Posisi poin adalah sertifikat yang baik, jadi di NP, dan Anda dapat menyandikan sirkuit ke "apakah ada set poin yang memuaskan?" masalah.

Pengurangan dari Evaluasi Sirkuit ke Penyisipan Jarak

Kita akan mengurangi evaluasi rangkaian menjadi masalah penyisipan jarak dengan membuat sistem koordinat, meletakkan bit logis di dalamnya, bit kabel agar sama, dan membuat widget untuk gerbang NOT dan AND.

1. Koordinat . Kita membutuhkan semacam sistem koordinat yang dapat kita gunakan untuk memposisikan poin. Lakukan ini dengan membuat "titik" tetrahedron poin. Tambahkan empat poin yang semuanya dinyatakan sebagai jarak dari satu sama lain. Ini memaksa bentuk keempat titik itu menjadi tetrahedron. Kami dapat memposisikan titik-titik lain relatif terhadap sistem koordinat tetrahedron kami dengan menentukan jarak mereka ke masing-masing dari empat sudut pangkalan. Tetrahedron dapat diterjemahkan dan diputar dan dipantulkan, tetapi hal yang sama akan terjadi pada semua poin lainnya juga.$1$

2. Bits . Untuk sedikit, kami memposisikan segitiga titik relatif terhadap tetrahedron dasar. Normal segitiga harus mengarah ke atas sepanjang sumbu Z, sehingga segitiga sejajar dengan bidang XY (dalam koordinat tetrahedron). Tepinya juga harus memiliki panjang . Setelah selesai, kami menambahkan "nilai" titik v , yang ditentukan sebagai jarak 1 dari tiga lainnya. Kami tidak menghubungkan v ke sistem koordinat basis. Ini memberinya dua posisi yang memungkinkan: centered $1$$v$$1$$v$ atas atau di bawah segitiga, sebagai sudut akhir tetrahedron. Bitnya ON jika titik di atas segitiga, dan OFF jika di bawah.$\frac{1}{\sqrt{3}}$

3. Kabel . Kita dapat memaksa dua bit agar sama dengan mengatakan jarak antara titik nilai mereka sama dengan jarak antara pusat segitiga mereka. Ada satu pengecualian: ketika sudut atas atau bawah salah satu bit persis berbaris dengan bidang tengah yang lain. Dalam hal ini pertama-tama kita menggunakan kawat untuk memindahkan salah satu bit secara vertikal.

4. BUKAN . Kita bisa mendapatkan negasi sedikit dengan menambahkan titik nilai kedua ke segitiga yang sama, tetapi mengharuskan w menjadi jarak $w$$w$ dariv. Ini pasukanwuntuk mengambil kebalikan posisiv, sehubungan dengan segitiga, memberikan kita sedikit dengan nilai yang berlawanan.$\frac{2}{\sqrt{3}}$$v$$w$$v$

5. TERSIRAT . Masalah yang sama-sama kita hadapi dengan kabel sebenarnya cukup berguna. Ketika bit berbaris dengan cara itu, yang bisa kita paksa dengan kabel vertikal, semakin tinggi berarti semakin rendah. Jika yang lebih tinggi benar, hanya bagian atas yang lebih rendah adalah jarak yang tepat. Jika yang lebih tinggi salah, baik bagian atas dan bawah adalah jarak yang tepat.

6. DAN . Untuk membuat sedikit sama dengan A AND B , kita perlu dua implikasi dan widget untuk memaksa kesetaraan ketika A dan B setuju. Implikasinya hanya $C$$A$$B$$A$$B$ dan$C \implies A$ . Untuk membuat widget kita bergerak A dan B secara vertikal sehingga mereka berada pada level dan jarak yang sama$C \implies B$$A$$B$ terpisah, maka kita pindahkanCagar berjarak sama di antara mereka. Kami kemudian menambahkan titikSAdanSBjarak$\frac{2}{\sqrt 3}$$C$$S_A$$S_B$ darititik nilaiAdanBmasing-masing, dan memaksa jarak antaraSAdanSBmenjadi$\frac{\sqrt 2 - 1}{2 \sqrt 3}$$A$$B$$S_A$$S_B$ . Kami juga menambahkan titikSCjarak$\frac{\sqrt 2 + 1}{\sqrt 3}$$S_C$ dari keduaSAdanSB. Ini menciptakan rantai antaratitik nilaiAdanB, denganSCdi pusat rantai. KetikaA≠B, rantai direntangkan ke batas danSCberada di tengahsegitigaC. KetikaA=Brantai link dipaksa untuk pergi di arah sebaliknya,mendorongke batas dan menempatkanSCdiCtitik nilai 's sama untukA. Untuk memaksa$\frac{\sqrt 2 + 1}{2 \sqrt 3}$$S_A$$S_B$$A$$B$$S_C$$A \neq B$$S_C$$C$$A = B$$S_C$$C$$A$$C$'s nilai titik, kita insert titik jarak $S_D$ darititik nilaiSCdanC. Ini tidak membatasiC's titik nilai ketikaA≠B, tapi pasukanA=B=CketikaA=B.$\frac{1}{2 \sqrt 3}$$S_C$$C$$C$$A \neq B$$A=B=C$$A=B$

Dengan elemen-elemen itu, Anda dapat menyandikan sirkuit apa pun ke penyematan jarak. Input menjadi bit, gerbang didekomposisi menjadi BUKAN dan AND memperkenalkan bit baru seperlunya, dan hanya itu. Paksa posisi output menjadi benar, dan Anda mendapatkan masalah kepuasan Anda.

Sebagian jawaban tentang keunikan : keterhubungan 3 tidak cukup.

Contoh penghitung minimal: grafik kubus ( dari keluarga Hypercube Graph )$Q_3$

Untuk melihat bagaimana memperbaiki panjang semua tepi di tidak memberikan posisi ke simpul dalam ruang 3-d yang unik hingga terjemahan / rotasi / mirroring, lihat bagaimana Anda bisa meratakan kotak kardus (dengan 2 wajah yang berlawanan dihilangkan) .$Q_3$

Ambil sudut kotak kardus untuk menjadi simpul yang menarik. Setiap sudut kotak kardus memiliki jarak tetap dari sudut lain yang berbagi wajah kotak.

$Q_3$

ini dikenal sebagai masalah berikut dan terjadi misalnya dengan merekonstruksi koordinat dari jaringan sensor yang dapat mengukur jarak ke node terdekat, & makalah ini dapat berfungsi sebagai survei mini bersama dengan algoritma terkemuka. metode utama dikenal sebagai Proyeksi Nilai Singular, metode lain untuk Nilai Ambang. algoritma umumnya didasarkan pada aljabar matriks & pengurangan peringkat. makalah ini mengimplementasikan kedua algoritma dan memberikan beberapa analisis empiris.

Rekonstruksi Jarak Euclidean dari Informasi Jarak Sebagian Xu, Chen