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

Il s'agit d'un problème relativement ouvert. Personnellement, je pense qu'il fait toujours partie de la théorie des graphes, mais il ne peut pas être résolu par les algorithmes existants liés au chemin le plus court tels que SPFA et l'algorithme de Dijkstra. Zeng Jin semble être un ami qui m'a demandé de quel genre de question de concurrence il s'agissait pour Huawei. Il est tout à fait possible d'utiliser l'algorithme A* pour cette question. La clé est de savoir comment concevoir cette fonction heuristique ?
Vous pouvez rechercher des connaissances associées
1. Algorithme du chemin le plus court via un ensemble spécifié de nœuds intermédiaires
2 Algorithme de recherche heuristique A*

.

Answer 2

Je ne pense pas que cette question ait une solution polynomiale. (Bienvenue pour gifler)
Supposons que le nombre de points soit n, le nombre d'arêtes est m, le nombre d'arêtes qui doivent être franchies est k, n<=500, m<=5000, k<= 500.
Considérez la méthode de la force brute, O(n^3) prétraitant le chemin le plus court entre deux points quelconques (bien sûr, vous pouvez également optimiser le tas n-time, mais ce n'est pas un goulot d'étranglement), O(k !) énumérant les k éléments réussis En arrangeant les bords et en calculant la réponse, la complexité totale est O(k!*k), ce qui est évidemment inacceptable.
Notez que la solution optimale ne doit pas nécessairement être obtenue en énumérant toutes les permutations. Vous pouvez utiliser des algorithmes aléatoires tels que le recuit simulé pour obtenir une meilleure solution. L'utilisation de paramètres appropriés devrait permettre d'obtenir la solution optimale la plupart du temps. .
Je veux essayer de prouver que cette question est NPC ou NPH.
Enregistrez les m bords du problème d'origine de [i] à [i].
Créez un nouveau graphique avec k points et spécifiez les i-ième et j-ème arêtes parmi les k. Si to[i] peut atteindre from[j], connectez-en une de i à j dans le nouveau graphique. bord de dis[à[i]][from[j]]. Le problème initial est donc réduit à un nouveau problème en temps polynomial : trouver un chemin répétable passant par tous les points d'un graphe de k points pour minimiser la longueur du chemin. Ce nouveau problème ressemble beaucoup à NPC ou NPH. (Drôle)
Mais je n'ai pas trouvé comment ramener le nouveau problème au problème d'origine. L'idée actuelle est que pour chaque point i du nouveau problème, connecter une arête +inf entre i<<1 à (i<<1)|1 du problème d'origine, et pour chaque arête i-&gt du nouveau problème ;j, connectez un bord disi de (i<<1)|1 à j<<1 du problème d'origine, mais il semble y avoir quelques problèmes, et je n'y ai pas encore réfléchi clairement.

Answer 3

Je ne comprends pas l'algorithme, mais je connais un cadre général pour résoudre ce type de problème CSP Vous pouvez y jeter un œil : Optaplanner

.