java - 数据结构的图要求经过指定一些边，求最优解？

Question

数据结构的图要求经过指定一些边，求最优解？
能帮忙指点一下应该怎么去网上找资料吗，比如和哪个问题类似，应该用什么算法？这个问题是这样的,货运公司必须经过某一些城市,题目给出各个城市之间的花费,让用A*算法求最优解.

这是输入:
花费 360 Sydney 到 Wagga         
花费 200 Sydney 到 Bathurst      
花费 200 Dubbo 到 Grafton        
花费 240 Dubbo 到 Bathurst       
花费 480 Grafton 到 Wagga        
花费 440 Grafton 到 Bathurst     
花费 400 Wagga 到 Bathurst       

要求必须经过:
Grafton 到 Wagga
Dubbo 到 Grafton
Sydney 到 Wagga
Sydney 到 Bathurst

结果是:
Sydney 到 Bathurst
Bathurst 到 Dubbo
Dubbo 到 Grafton
Grafton 到 Wagga
Wagga 到 Sydney
Sydney 到 Wagga
总花费 1840

Answer 1

Ini adalah masalah yang agak terbuka, secara peribadi saya fikir ia masih sebahagian daripada teori graf, tetapi ia tidak boleh diselesaikan oleh algoritma berkaitan laluan terpendek seperti SPFA dan algoritma dijkstra. Zeng Jin seolah-olah seorang rakan bertanya kepada saya jenis soalan persaingan untuk Huawei. Sudah pasti mungkin untuk menggunakan algoritma A* untuk soalan ini Kuncinya ialah bagaimana untuk mereka bentuk fungsi heuristik ini?
Anda boleh mencari pengetahuan berkaitan
1 Algoritma laluan terpendek melalui set nod perantaraan yang ditentukan
2

Answer 2

Saya tidak fikir soalan ini mempunyai penyelesaian polinomial. (Dialu-alukan untuk menampar muka)
Andaikan bilangan mata ialah n, bilangan tepi ialah m, bilangan tepi yang perlu dilalui ialah k, n<=500, m<=5000, k<= 500.
Pertimbangkan kaedah kekerasan, O(n^3) mempraproses laluan terpendek antara mana-mana dua titik (sudah tentu anda juga boleh dijkstra pengoptimuman timbunan n-masa, tetapi ini bukan halangan), penghitungan O(k!) item k yang diluluskan Menyusun tepi dan mengira jawapan, jumlah kerumitan ialah O(k!*k), yang jelas tidak boleh diterima.
Perhatikan bahawa penyelesaian optimum tidak semestinya perlu diperolehi dengan menghitung semua pilih atur Anda boleh menggunakan algoritma rawak seperti penyepuhlindapan simulasi untuk mendapatkan penyelesaian yang lebih baik .
Saya ingin cuba membuktikan bahawa soalan ini adalah NPC atau NPH.
Rekodkan tepi m masalah asal sebagai dari[i] hingga ke[i].
Buat graf baharu dengan titik k, dan nyatakan tepi ke-i dan ke-j di antara k [i] boleh mencapai dari[j], sambungkan satu daripada i ke j dalam graf baharu tepi dis[ke[i]][dari[j]]. Jadi masalah asal dikurangkan kepada masalah baharu dalam masa polinomial: cari laluan berulang melalui semua titik dalam graf k titik untuk meminimumkan panjang laluan. Masalah baharu ini kelihatan seperti NPC atau NPH. (Lucu)
Tetapi saya tidak tahu bagaimana untuk mengurangkan masalah baru kembali kepada masalah asal. Idea semasa ialah untuk setiap titik i masalah baharu, sambungkan +inf tepi antara i<<1 hingga (i<<1)|1 daripada masalah asal dan untuk setiap tepi i-> baharu masalah ;j, sambungkan tepi disi dari (i<<1)|1 ke j<<1 masalah asal, tetapi nampaknya terdapat beberapa masalah dan saya belum memikirkannya dengan jelas lagi.

Answer 3

Saya tidak faham algoritma, tetapi saya tahu rangka kerja umum untuk menyelesaikan masalah CSP jenis ini Anda boleh lihat: Optaplanner