1

ML を使用していくつかの関数を記述する必要があります。この関数は、有向グラフ [(1,2),(1,3),(3,2)] のエッジのリストを受け取ります。これは、1から2への有向エッジを意味し、 1 から 3 まで...、そして 2 つの頂点も受け取ります。最初の頂点から 2 番目の頂点までのすべての可能な方法と、可能なパスのリストを見つける必要があります。たとえば、頂点1, 2の場合、リストを表示する必要があります [[ 1,2]、[1,3,2]]、頂点に関するデータを保存できない場合、どうすればMLを実行できますか。アイデアを事前に感謝します。

4

3 に答える 3

3

頂点に関するデータを保存する場合は、頂点からデータへの有限マップが必要です。マップは、次のような署名を提供する場合があります。

type 'a vmap (* vertex map *)
val empty : 'a vmap  (* empty map *)
val insert : vertex * 'a * 'a vmap -> 'a vmap  (* add info about a vertex *)
val lookup : vertex * 'a vmap -> 'a option  (* look for info about a vertex *)

この署名を実装するには、vertex * 'aペアの単純なリスト、またはバランスの取れた二分探索木のようなより野心的なものを検討できます。

于 2010-12-01T03:20:14.470 に答える
2

頂点に関するデータを保存できます!

たとえば、どの頂点を訪れたかを記録しますか?

現在の頂点から未探索の可能性のあるすべてのエッジを再帰的に探索する関数があるとします。

未探索のエッジのベクトルに加えて、現在の頂点とターゲット頂点を受け入れることができます。ターゲット頂点に到達するパスのベクトルを返します。

内部的には、この頂点で始まるエッジのセットを見つけ、このセットの各エッジに対してそれ自体に再帰し、未調査のエッジのリストから選択したエッジを各サブ関数に削除します。

于 2010-11-29T13:47:21.540 に答える
0

すみません、抵抗できませんでした

Yahoo!でこれと同じパズル（質問）のポップアップを見ました。答え、そして私はそれに答えました。

実装は、グラフをトラバースするツリーの作成に基づく設計として始まりました。しかし、最終的には、AlexBrownが以前に表現したデザインと一致することになりました。

もともと計画はHaskellで行われていたため、このヘルパー関数は次のようになります。

fun replicate len el = 
    if len = 0 then nil else el::replicate (len -1) el

主な実装：

fun routes  dst (edges:(int * int) list) src  = 
    let val (very_possible,remotely_possible) =
            if null edges
            then (nil,nil)
            else List.partition ((fn s=> s = src) o #1) edges 
        val (raw_solutions,dsts_is_nx_srcs) = 
            List.partition  ((fn d => d = dst) o #2) very_possible
        val solutions = replicate  (length raw_solutions) [src,dst]
        val full_rest_routes =
            let val rest_rest_routes = 
                    map (routes dst remotely_possible)  
                            ( map #2 dsts_is_nx_srcs )
              in map (fn lst => src::lst) (List.concat rest_rest_routes)
     end
     in case (very_possible, solutions, remotely_possible)
        of (nil, _,  _)       => nil
         |  (_::_, (p::ps), _) =>  solutions @ full_rest_routes
         |  (_::_, nil, _::_)  =>  full_rest_routes
  |  (_   , nil, nil )  => nil
     end

ユーザーインターフェイス：

fun getPaths edges src dst  =  routes dst edges src

上記のコードはroutes4.smlからのものです。ただし、テストとIOは省略されています。これはそれほど長くはありませんが、私はそれがもっと単純になることを望んでいます。

于 2010-12-10T08:40:35.987 に答える