2次元平面上の点集合間のユークリッド距離に基づいて、最小スパニングツリーを計算します。私の現在のコードは、すべてのエッジを格納し、最小スパニングツリーを取得するためにPrimのアルゴリズムを実行します。しかし、私はこれを行うにはすべてのエッジのためにO(n^2)
スペースを取ることを認識しています。ユークリッド最小スパニングツリーとドローネ三角形分割
最初にこの点集合のdelaunay三角測量を計算してから、PrimとKruskalのアルゴリズムを実行して最小スパニングツリーを取得すると、メモリとランタイムを最適化できることが明らかになりました。三角測量。
これはプログラミングコンテストの一部です(https://prologin.org/train/2017/qualification/taxi_des_neiges)ので、私はscipy.spatialを使用することはできません。 Delaunay三角測量に含まれるエッジを取得するだけの選択肢はありますか?
ありがとうございます。
おかげでDelaunay三角形分割を実施し、エッジを取得するためのコードを持ってどこかに、このフォルダ内の... ... QHullを、使用していますように見えますしかし、可能であれば、私はPythonのソースコードを望んでいます。 –
問題はありません、うまくいけば、wildwilhelmの答えが助けになるでしょう!彼はアルゴリズムの抽象的な記述を見つけたようです。 – Marviel
はい両方の答えが私を助けたので、ここに感謝のためのupvoteです! –