न्यूनतम निकटतम-पड़ोसी दूरी और अधिकतम घनत्व के साथ 3 डी अंतरिक्ष में नमूना दिए गए बिंदुओं को stochastically

Jan 10 2021

मेरे पास nएक 3 डी स्थान में अंक हैं। मैं stochastically सभी निकटतम पड़ोसी दूरियों के साथ अंकों का सबसेट नमूना करना चाहता हूं r। सबसेट mका आकार अज्ञात है, लेकिन मैं चाहता हूं कि नमूना अंक यथासंभव घने हों।

इसी तरह के सवाल हैं, लेकिन वे सभी दिए गए बिंदुओं से नमूना लेने के बजाय अंक उत्पन्न करने के बारे में हैं।
न्यूनतम निकटतम-पड़ोसी दूरी के साथ 3 डी अंतरिक्ष में यादृच्छिक अंक उत्पन्न करें

उनमें से प्रत्येक के बीच न्यूनतम दूरी के साथ 3-डी यादृच्छिक अंक उत्पन्न करें?

कहो कि मेरे पास 300 यादृच्छिक 3 डी अंक हैं,

import numpy as np
n = 300
points = np.random.uniform(0, 10, size=(n, 3))

अधिकतम करते समय mन्यूनतम निकटतम-पड़ोसी दूरी के साथ सबसेट प्राप्त करने का सबसे तेज़ तरीका क्या है ?r = 1m

जवाब

2 DavidEisenstat Jan 14 2021 at 08:00

संभवतया एक कुशल बाइसेटरिया सन्निकटन योजना है, लेकिन जब पूर्णांक प्रोग्रामिंग औसतन इतनी जल्दी होती है तो परेशान क्यों होती है?

import numpy as np

n = 300
points = np.random.uniform(0, 10, size=(n, 3))

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver.CreateSolver("SCIP")
variables = [solver.BoolVar("x[{}]".format(i)) for i in range(n)]
solver.Maximize(sum(variables))
for j, q in enumerate(points):
    for i, p in enumerate(points[:j]):
        if np.linalg.norm(p - q) <= 1:
            solver.Add(variables[i] + variables[j] <= 1)
solver.EnableOutput()
solver.Solve()
print(len([i for (i, variable) in enumerate(variables) if variable.SolutionValue()]))

1 DanielF Jan 18 2021 at 16:16

यह एक उपसमुच्चय का बहुत बड़ा हिस्सा नहीं है, लेकिन KDTreeदूरी की गणना का अनुकूलन करने के लिए बहुत लंबा समय नहीं लेते हुए करीब होना चाहिए :

from scipy.spatial import KDTree
import numpy as np

def space_sample(n = 300, low = 0, high = 10, dist = 1):
    points = np.random.uniform(low, high, size=(n, 3))
    k = KDTree(points)
    pairs = np.array(list(k.query_pairs(dist)))
    
    def reduce_pairs(pairs, remove = []):  #iteratively remove the most connected node
        p = pairs[~np.isin(pairs, remove).any(1)]
        if p.size >0:
            count = np.bincount(p.flatten(), minlength = n)
            r = remove + [count.argmax()]
            return reduce_pairs(p, r)
        else:
            return remove
    
    return np.array([p for i, p in enumerate(points) if not(i in reduce_pairs(pairs))])

subset = space_sample()

Iteratively सबसे जुड़े नोड को हटाना इष्टतम नहीं है (लगभग 300 में से 200 अंक रखता है), लेकिन संभवतः सबसे तेज एल्गोरिथम है जो इष्टतम के करीब है (केवल एक चीज तेजी से यादृच्छिक पर हटा रहा है)। आप संभवतः @njit reduce_pairsउस हिस्से को तेजी से बना सकते हैं (यदि मेरे पास बाद में समय होगा तो कोशिश करेंगे)।