l'optimisation d'une fonction de distance 2 de paramètres sur les segments de ligne

Question

Ce problème est un sous-problème d'un problème posé dans l'ACM ICPC Kanpur Regionals élimination ronde (ACM ICPC Regionals Elim.):

donné 2 segments de droite délimitée par les points 2D (Pa, Pb) et (Pc, Pd) respectivement, pour p et q (dans la plage [0,1]) qui minimise la fonction

f(p, q) = D(Px, Pa) + D(Py, Pd) + k D(Px, Py) where 
           2 <= k <= 5, 
           Px = p Pa + (1-p) Pb, 
           Py = q Pc + (1-q) Pd and 
D(x, y) is the euclidean distance between points x and y 

(effectivement, Px et Py sont des points sur les segments de ligne et la fonction code pour le coût d'aller de Pa à Pd à travers un conne lien ction d'un coût qui est k fois la distance euclidienne)

Quelques observations concernant cette fonction:

1. segments de ligne parallèle entraînera toujours atleast un des p et q pour être 0 ou 1
2. Les segments de ligne d'intersection provoquent toujours p et q pour localiser le point d'intersection des segments de ligne (l'inégalité de triangle peut être appliquée pour le prouver)

La question: Dans le cas général où les lignes sont inclinées et potentiellement séparées, comment minimisons-nous cette fonction?

Answer 1

Je pense que vous devriez être en mesure de prendre les dérivées partielles de f par rapport à p et q, les mettre à 0, et pour résoudre p et q. Cela vous donnera un minimum (local). Si le minimum a 0 <= p <= 1 et 0 <= q <= 1, vous avez terminé, sinon vérifiez les quatre points de terminaison (p=0,q=1 et ainsi de suite).

Je ne suis pas sûr que cela va gérer toutes les conditions dégénérées, mais ce devrait être un bon début.