次のアルゴリズムに関する質問はオンラインでは見つかりましたが、効率的な解決策は見つかりませんでした。
Googleのインタビューで尋ねられました。行グループを効率的にプロットするアルゴリズム
プロットする線のシーケンス（各行に開始点と終了点があります）を指定すると、
は最小限の時間で線をプロットするアルゴリズムを提供します。
開始点から線をプロットする必要はありません。
グラフの各ノードをノードとして扱うアプローチが1つありました。
2ノード間のエッジは、第1ラインの終了ノード
と第2ラインの開始ノードとの間の距離である。その後、最小スパニングツリーを計算すると、
という最適な回答が得られます。
しかし、
行が一方向にのみプロットされていると仮定しているため、これが常に最適な解決策を示しているかどうかはわかりません。
このような問題をどのように解決できるかについてのヒントはありますか？
最小スパニングツリーでは、Djikstraのアルゴリズムを使用する必要があります。このアルゴリズムは、最短パスを選択して、すべてのノードが処理されるまで再帰的に同じノードに接続されている他のノードと比較します。実際に私はちょうどあなたの質問を読んで、あなたのパスは特定のポイントから始める必要はないので、上記と同じアイデアを持ちながらどのノードでも始まるプリムを使うことができます。両方とも幅広い優先検索を可能にする優先度キューを使用します。
これが問題を解決したことを確認しましたか？私は誤解されるかもしれませんが、記載されている問題はNP完全であることを思い起こさせるようです –
+1私はあなたがダイクストラに言及するのは正しいと思うからです。私は確かに遠いですが、もっと関わっていると思います。しかし開始位置の選択は問題ではありません。すべての実際の頂点にゼロ加重エッジを持つ人工開始頂点を追加するだけです。 – Steve314
@ jwpat7 - NP完成はそれが解決できないことを意味しません。それは、（非公式に）問題の大きなインスタンスに対しては非常に遅くなることを意味します。これが偽装されたセールスマンであっても（私には分かりません）、合理的な規模の問題に対しては合理的な時間に解決できると思います。たぶん正確に、または他のすべてが失敗した場合、少なくともおおよそ。 – Steve314
あなたの質問を完全に理解しているかわかりません。 1つのアプローチは、640X480イメージなど、描画領域から始めることができます。次に、画像内の各位置について、ピクセル（x、y）が少なくとも1つの線にあるかどうかをチェックします（線方程式とイプシロンの適切な値を使って1つの線を満たす必要があります） a 1 else a 0すべての線が描画されます。
コメント内のペンプロッターの解釈が正しいと仮定すると（OPによって記述されるように）、問題はNP完成品として知られている移動セールスマン問題のある一般化です。
証明：すべてのラインが長さ0、すなわち、ポイントに縮小されている場合、問題は、各ポイントにペンが触れる必要があり、ペンの移動距離を最小限に抑える必要があることです。これはまさにユークリッド旅行のセールスマン問題です。
近似アルゴリズムを探している必要があります（最適な解を効率的に見つけることはできません）。 approximation algorithms for the Euclidean TSPの一部は、miminumスパニングツリーに基づいており、問題を解決するために変更することができます。また、結果として得られるアルゴリズムが、最適パスの長さのX（= 2倍）を超えないパスを与えることを証明することも可能です。
EDITは：ここでは、頂点無向（おそらく切断）グラフのエッジとして描画したい行を解釈
これは、最適パスの2倍の長さであるソリューションを提供します（適切なパスの描画エッジに従ってください）。たとえば、ショートカットを作成し、次のエッジを描画する必要がないときはパスの頂点をスキップするなど、さまざまな方法でさらに最適化できます。
まあ、実際には、正確にはTSPではありません。あなたは最初に戻る必要はありません。 TSPからその要件をエレガントに削除する方法がわかりません（TSPソリューションの最長エッジを削除しても* this *問題の最適解決策にはなりません） – harold
どちらの問題もNP-同様のアルゴリズムを使用して近似的に解くことができます。 – oseiskar
@haroldこの回答は、この問題を効率的に解決できれば、TSPを効率的に解決できることを示しています。したがって、この問題は少なくともTSPほど困難です。 – necromancer
これはかなり厄介な問題です。これは最短ハミルトニアンパスですが、トンののエッジ（すべてのエッジ（u、v）はuをいくつかのラインの終点とし、vを別のラインの始点とします）、距離は対称ではありません。 TAOCP 4Aで説明されているエレガントなZDDベースの方法は、私が思うには本当に適用されません。
はここでアイデアだ（最適ではないが、それはとにかく合理的に良いアイデアのように思える）TSPからの借入、：
For every line s
Schedule = empty sequence
For every line n
insert n in the optimal position in Schedule
Apply 2-opt (see TSP) to the Schedule
Take the best Schedule.
は、2-opt法と超注意してください。対称距離の場合はしばしば記述され、距離の変化の計算を最適化できます。ここには行けません。
はこちらTSPから重く借りて、他のアイデアです：
は、ILPの問題のトンを解決します。すべてのノードに対してsとt（等しくない）：
s又はtないすべてのノードnノードsとtためn == 2に隣接する全ての辺の和」の制約を与え、その合計が1s又はt、その連結成分に隣接する全ての辺の和が1でなければならないすべてのこれらのソリューションの最高を取ります。それはしばらく時間がかかります。
「プロットする」という意味を明確にする必要があります。私の考えでは、描画線はそれらをラスタに書き込んだ後、そのラスタをフレームバッファに送ります。私がこれを好きなら、線を描くのに必要な時間は、線の長さと線の数に依存しますが、線の印刷順序とは無関係です。 さらに数学的に言えば、ソリューションSのコストを示し、最小化したいコスト関数 'C（S）'を提供する必要があります。 –
@Giulo - 私の推測はペンプロッターです。線の順序は、ペンを線の終点から次の線の始点に移動する時間があるために重要になります。 "b/w"は "between"を意味すると仮定すると、これは上記のグラフが各エッジに格納されているため、最小スパニングツリーはライン間描画の最小間隔を選択しています。 – Steve314
@Aman - 私は、スパニングツリーの最小単位が* undirected *グラフに基づいていることは確信しています。つまり、どちらの方向のトラバーサルも同じように許可されます。私は、木の中で頂点が奇妙な数の辺を引き出していることをもっと心配したいと思います。[セブンブリッジズオブケーニヒスバーグ]（https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg# Euler.27s_analysis）なぜその問題か。申し訳ありません - それを修正するために何をすべきかわかりませんが、[Napalidon]（http://stackoverflow.com/a/18523742/180247）がDijkstraについて正しいことを除いて - これは経路探索のようなものです問題。 – Steve314