Eine Zeile wird angegeben und eine Reihe von Punkten wird angegeben. Ich muss einen Punkt auf der Linie finden, für den die Summe der Abstände von den gegebenen Punkten minimal ist. Ich konnte keinen Algorithmus in c zu implementieren finden. Bitte helfen Sie, danke im Voraus.Wie finde ich einen optimalen Standort auf einer Linie?
Ohne Einschränkung der Allgemeinheit ist die Linie die X-Achse (andernfalls die gesamte Geometrie drehen). Dann sind Sie
Sum √[(X - Xk)² + Yk²]
minimieren möchten, welche Sie durch Aufheben der ersten Ableitung
tun könnenSum (X - Xk)/√[(X - Xk)² + Yk²] = 0
Leider ist dies eine nicht-lineare Gleichung, die numerische Methoden erfordern.
Als Ausgang Näherung Sie die Minimierer der Summe der Quadrate der Abstände verwenden können,
Sum [(X - Xk)² + Yk²]
durch Lösen
Sum (X - Xk) = 0
, die einfach den Punkt (X*, 0) gibt, wo die durchschnittlichen Abszisse .
Solange keiner der angegebenen Punkte auf der Linie ist, scheint die Verwendung von Newton-Raphson gut zu funktionieren. Wenn jedoch einige der Punkte auf der Linie sind, dann ist das Ziel nicht differenzierbar (an diesen Punkten) und die Dinge sind nicht so nett. – dmuir
Es ist ein klassisches * Minimierungsproblem *. Sie sollten darüber erfahren. –
Beginnen Sie mit dem Finden des Rechtecks, das alle Punkte einschließt. Damit erhalten Sie einen ungefähren Suchbereich für X und Y. – user3386109
@ user3386109 Dieses Rechteck enthält nicht unbedingt einen Teil der Linie. –