Apa intuisi mengapa masalah jalur terpanjang tidak memiliki substruktur optimal?

Saya belajar tentang jalur terpanjang dan menemukan fakta bahwa jalur terpanjang dalam grafik umum tidak dapat dipecahkan oleh pemrograman dinamis karena masalahnya tidak memiliki substruktur optimal (yang saya pikir pernyataan itu perlu diperbaiki ke jalur sederhana terpanjang pada grafik umum tidak dapat dipecahkan oleh pemrograman dinamis).

Jika kita berasumsi mereka harus sederhana (untuk beberapa alasan ini diperlukan yang belum saya hargai) dan terlama, maka mudah untuk membuat contoh balasan. Pertimbangkan grafik kotak dengan 4 simpul A → B → C → D → A.

Jalur terpanjang dari A ke D jelas A → B → CD. Tetapi jalur terpanjang dari B ke C bukan bagian dari jalur terpanjang ke dari A ke D karena jalur terpanjang dari B ke C adalah B → A → D → C yang jelas tidak sama dengan jalur B → C (yang dalam hal ini sebenarnya jalan terpendek!).

Ini tampaknya bekerja hanya karena kami membutuhkan jalur untuk menjadi sederhana. Apakah perlu untuk mengasumsikan bahwa jalur harus sederhana bagi kita untuk membuktikan bahwa substruktur optimal tidak ada?

Saya pikir contoh counter harus menjadi bukti / bukti yang baik (yang tidak saya tolak), saya hanya tidak menemukan contoh counter yang sangat mencerahkan sama sekali. Saya melihat mengapa ini membuktikan bahwa tidak memungkinkan substruktur yang optimal tetapi gagal memberikan saya pemahaman atau intuisi yang sebenarnya mengapa harus jelas bahwa seharusnya tidak ada jalur substruktur optimal terpanjang. Seperti misalnya, mengapa argumen potong dan rekat tidak berfungsi? Jika subpath tidak terpanjang, maka tetap di jalan yang lebih panjang! Kedengarannya sangat menggoda, maksud saya, jika kita menempatkan sesuatu lebih lama maka tentu saja itu akan menjadi lebih lama ... meskipun, ini untuk beberapa alasan salah . Apakah contoh itu sebenarnya membuktikan bahwa DP tidak pernah bisamenyelesaikan jalur terpanjang (sederhana?) secara efisien? Saya tidak memerlukan bukti umum bahwa itu tidak dalam P (karena thats mungkin meminta solusi P vs NP). Saya hanya setelah bukti bahwa itu tidak dapat dipecahkan oleh DP (atau setidaknya bukti yang sangat kuat bahwa DP tidak pernah bisa menyelesaikan masalah jalur terpanjang ini atau bahwa masalah tidak memiliki substruktur yang optimal).

Saya telah secara definitif melihat di wikipedia bahwa masalahnya adalah NP-Hard, yang berarti mungkin tidak ada algoritma yang cepat. Tidak yakin apakah itu satu-satunya jenis bukti / intuisi yang ada untuk menyediakan bahwa substruktur yang optimal harus jelas kurang (atau jika tidak kurang, bahwa itu tidak dapat digunakan untuk membuat masalah lebih cepat). Apakah itu satu-satunya cara untuk menunjukkan bahwa itu tidak bisa dipecahkan oleh program dinamis cepat?

Apakah alasan yang kami butuhkan sederhanahanya karena jika kita tidak menempatkan persyaratan itu masalah menjadi sepele / tidak menarik? Dengan kata lain, jika ada siklus apa pun maka seseorang telah memecahkan masalah jalur terpanjang untuk semua node yang dapat dicapai dari siklus itu (dengan menemukan jalur apa pun ke siklus itu). Untuk node yang tidak memiliki siklus yang dapat dijangkau, kami memiliki grafik asiklik, yang dapat dipecahkan oleh DP (jika bobotnya positif?). Selain itu jika ada siklus, kami telah secara otomatis membuat hal-hal memiliki substruktur optimal (saya pikir) karena setiap jalur terpanjang hanya terdiri dari jalur terpanjang yang mencakup dua kasus, 1 jalur melalui siklus atau 2 jalur melalui DAG, yang keduanya mengandung substruktur optimal. Jadi masalahnya menjadi sepele tanpa persyaratan jalur sederhana? Atau apakah saya melewatkan sesuatu atau ada penjelasan yang lebih baik mengapa jalur sederhana diperlukan? Tidakumum jalur terpanjang yang dipecahkan oleh DP?

Saya juga tidak 100% yakin persyaratan apa yang diperlukan untuk menjamin bahwa DP tidak dapat digunakan. Apakah perlu untuk bobot tepi negatif, positif, tidak berbobot, terarah, tidak terarah ... apa persyaratannya?

Masalah jalur terpanjang memang memiliki substruktur optimal, dan ini dapat digunakan untuk meningkatkan sepele $O(n!)$ algoritma ke $\tilde{O}(2^n)$algoritma. Pertama, kita harus menggeneralisasi masalah:

Jalur terpanjang umum: Diberikan grafik $G=(V,E)$, dua simpul $s,t \in V$, dan satu set simpul $A \subseteq V \setminus \{s,t\}$, temukan jalur terpanjang di $G$ dari $s$ untuk $t$ menghindari simpul dalam $A$.

Menandakan solusi untuk masalah ini dengan $\ell(s,t,A)$ (grafik dipahami), kita memiliki pengulangan

Anda dapat memecahkan masalah ini dengan menggunakan pemrograman dinamis dalam waktu $\tilde{O}(2^n)$.

Meskipun ada substruktur yang optimal di sini, ada terlalu banyak parameter untuk dilacak, dan inilah yang membuat masalah tidak terselesaikan.

Pertama-tama, jalur sederhana terpanjang adalah NP-hard dan tidak ada keraguan tentang itu (karena jalur Hamiltonian mengurangi itu).

Kedua, jika Anda mempertimbangkan jalur non-sederhana, maka masalahnya tidak masuk akal, karena jalur non-sederhana melewati satu sisi / titik lebih dari sekali, sehingga memiliki loop. Sebagai hasil dari memiliki loop di jalur, jalur non-sederhana terpanjang tidak terbatas .

Saya telah memikirkan hal yang sama dalam 1 jam terakhir dan sampai pada kesimpulan berikut:

i) Jalur terpanjang dalam grafik tanpa siklus memiliki substruktur optimal dan begitu juga jalur terpendek.

ii) Jalur terpanjang tanpa siklus positif memiliki substruktur optimal dan demikian juga jalur terpendek tanpa siklus negatif.

iii) Jalur terpanjang dengan siklus positif dan jalur terpendek dengan siklus negatif tidak ada karena kita dapat memutari siklus tanpa batas. Jadi kita melihat jalan yang sederhana.

iv) Jalur sederhana terpanjang dengan siklus positif dan jalur sederhana terpendek dengan siklus negatif adalah NP Hard.

DP memecahkan (i) dalam O (V + E). Bellman-Ford memecahkan (ii) dalam O (VE) dan Djisktra membantu dalam sub-kasus tertentu (ii).

Sastra membingungkan tentang topik ini ketika jalur terpanjang hanya jalur terpendek dengan bobot dinegasikan dan sebaliknya. Saya tidak melihat alasan untuk memberikan pernyataan selimut seperti jalur terpanjang tidak memiliki sub struktur optimal tetapi jalur terpendek memiliki dll.