Erlang推理

Question

以下源代码没有编译，因为Stopover是未绑定的。

我是二郎的新手，我怎么重写它呢？

-module(distances).
-export([ path/2 ]).

path( madrid, paris ) ->
   { km, 1049 };
path( paris, moscou ) ->
   { km, 2482 };
path( moscou, berlin ) ->
   { km, 1603 };
path( From, To ) ->
   path( From, Stopover ) + path( Stopover, To ).

这个模块的使用可能：

path( madrid, moscou ).

受影响的答案应该是{ km, 3531}。

Answer 1

下面的源代码没有编译，因为停止是不绑定的。

我是二郎的新手，我怎么重写它呢？

看看这段代码：

-module(a).
-compile(export_all).

do_stuff() ->
    Stopover.

下面是当我试图编译它时所发生的事情：

a.erl:5:变量“停留”未绑定

变量Stopover从来没有被分配一个值，因此erlang不知道函数do_stuff()应该返回什么。你在这里做的是类似的事情：

path( From, Stopover ) + path( Stopover, To ).

变量From和To是函数path()的参数变量，当调用path()时，例如path(madrid, moscow)，madrid将被赋值给变量From，moscow将被分配给变量To。但是，请注意，您没有为变量Stopover指定任何值。

您需要重新定义path()，如下所示：

path(From, To, Stopover) ->

接下来，您应该尝试查看添加元组是否真的有效：

2> {km, 5} + {km, 3}.
** exception error: an error occurred when evaluating an arithmetic expression
     in operator  +/2
        called as {km,5} + {km,3}
3> 

不是的！

您需要做的是使用模式匹配从每个元组中提取一个整数的距离，然后添加两个整数：

{km, Distance1} = path( From, Stopover ),
...             = path(Stopover, To),

{km, Distance1 + Distance2}.

Answer 2

@7 7stud已经回答了这个问题，我想知道如何在erlang实现这样的路径搜索。以下是一个可能的解决方案：

-module(distances).
-export([ path/2,getTowns/0,start/1, stop/0 ]).

path(From,To) ->
    Paths = getPath(),
    path(From,To,maps:get(orderedTuple(From,To), Paths, not_found),Paths).

% distanceServer in charge to keep the liste of known distances
% server interfaces
start(Towns) ->
    {ok,List} = file:consult(Towns),
    Paths = lists:foldl(fun({A,B,D},Acc) -> maps:put(orderedTuple(A,B), D, Acc) end,#{},List),
    start(Paths,distance_server).

stop() ->
 distance_server ! stop.

getTowns() ->
    K = maps:keys(getPath()),
    L = lists:usort(lists:flatten([[A,B] || {A,B} <- K])),
    io:format("list of towns :~n~p~n~n",[L]).

getPath() ->
 distance_server ! {getPath,self()},
 receive
    Path -> Path
 end.

% server fuctions
start(Paths,Server) ->
    Pid = spawn(fun() -> distanceServer(Paths) end),
    register(Server, Pid).

distanceServer(Path) ->
    receive 
        stop -> stop;
        {getPath,From} ->
            From ! Path,
            distanceServer(Path)
        end.

% Searching path
path(From,To,not_found,Paths) -> % if not in the known list, seach for the shortest path
    {KM,P} = searchBestPath({0,[From]},To,maps:keys(Paths),{no_dist,no_path}),
    case P of 
        no_path -> not_found;
        _ -> {lists:reverse(P),KM}
    end;
path(From,To,KM,_) ->  % else give the result. Assumption: the known path contains always the best one.
    {[From,To],KM}.

searchBestPath({N,[To|_]}=Path,To,_,{BestD,_}) when N < BestD -> Path; % keep the new path if it is better
searchBestPath({N,_},_,_,{BestD,_}=Best) when N >= BestD -> Best; % cancel search if the path so far is longer or equal to the best found
searchBestPath({D,[H|_]=PathSoFar},To,Remaining,Best) ->
    Next = [remove(H,{A,B}) || {A,B} <- Remaining, (A =:= H) orelse (B =:= H)], % list of all possible next steps
    case Next of 
        [] -> Best;
        Next  -> lists:foldl(
                    fun(X,Acc) ->
                        {_,ND} = path(H,X), % will always match
                        R = Remaining -- [orderedTuple(H,X)], % necessary to avoid possible infinite loop in the first search
                        searchBestPath({D+ND,[X|PathSoFar]},To,R,Acc) % evaluate path for all possible next steps
                    end,
                    Best,Next)
    end.

% helpers
orderedTuple(A,B) when B > A -> {A,B};
orderedTuple(A,B) -> {B,A}.

remove(X,{X,B}) -> B;
remove(X,{A,X}) -> A.

它使用一个外部文件来定义“已知距离”，我使用这个文件进行测试：

{paris,lyon,465}.
{lyon,marseille,314}.
{marseille,nice,198}.
{marseille,toulouse,404}.
{toulouse,bordeaux,244}.
{bordeaux,paris,568}.
{bordeaux,nantes,347}.
{nantes,paris,385}.
{paris,lille,225}.
{paris,strasbourg,491}.
{lille,strasbourg,525}.
{lille,bruxelles,120}.
{rennes,brest,244}.
{rennes,paris,351}.
{rennes,nantes,113}.

壳中的结果是：

1> c(distances).                    
{ok,distances}
2> distances:start("distances.txt").
true
3> distances:getTowns(). 
list of towns :
[bordeaux,brest,bruxelles,lille,lyon,marseille,nantes,nice,paris,rennes,
 strasbourg,toulouse]

ok
4> distances:path(bordeaux,bruxelles).
{[bordeaux,paris,lille,bruxelles],913}
5> distances:path(nice,bruxelles).    
{[nice,marseille,lyon,paris,lille,bruxelles],1322}
6> distances:path(moscou,paris).
not_found
7> distances:stop().            
stop
8> 

下一步可以是在每次完成新请求时增加已知距离的列表。