algorithm - 如何处理通过 Dijkstra 算法遍历的图中的“组合节点”？

问题描述

我正在处理当前通过 Dijkstra 算法遍历的状态机。但是，现在我需要增强该状态机，使其在计算路由以解决一些副作用方面“更智能”。基本上，如果不满足某些要求，则某些路径是不可遍历的，即使您处于该路径的正确起始状态。这些要求可以通过先遍历其他路径来满足。我试图解决的一个简化示例是在城市之间旅行：

您可以在没有护照的情况下在国内旅行（只是一个基本身份证）（即费城 -> 纽约市）
一旦您需要出国旅行，您就需要您的护照（纽约 -> 巴黎）
如果您已经拥有护照，您可以国际旅行（纽约市 -> 巴黎）
如果你不这样做，你需要先回家带它（NYC -> Philly -> NYC -> Paris）

另一个示例（我实际上正在处理）是网站状态和登录和注销的概念）。

我正在考虑两种方法：

组成状态（即拥有护照本身就是可以与“位置”状态结合的次要状态），这听起来像是会给我的状态机增加一个全新的维度，我不确定它是否会让算法变得一团糟.
仅在处于状态时设置某些属性时才可用的条件路径（有点贝叶斯方法），这将有效地使我的状态“不纯”，其中所采取的转换将取决于内部状态属性，因此我更喜欢组合状态方法反而。

有没有一种干净的方法可以通过图论来表示这一点？是否有通用案例算法可以处理能够遍历路径的初步要求？这个问题基本上是一个 2 阶段的 Dijkstra 搜索，您必须首先访问某个节点，但如果您已经满足“有护照”条件，则不需要访问该节点。

标签： algorithmlanguage-agnosticgraph-theorydijkstragraph-layering

鉴于这些事实

connection(philly,nyc,no).
connection(nyc,philly,no).
connection(philly,harrisburg,no).
connection(harrisburg,philly,no).
connection(paris,nyc,yes).
connection(nyc,paris,yes).
passport(harrisburg).

其中 aconnection有参数from, to,passport needed

和这些测试用例

:- begin_tests(travel).

travel_test_case_generator( harrisburg ,harrisburg ,no  ,[harrisburg]                                                        ).
travel_test_case_generator( harrisburg ,harrisburg ,yes ,[harrisburg]                                                        ).
travel_test_case_generator( harrisburg ,philly     ,no  ,[harrisburg,philly]                                                 ).
travel_test_case_generator( harrisburg ,philly     ,yes ,[harrisburg,philly]                                                 ).
travel_test_case_generator( harrisburg ,nyc        ,no  ,[harrisburg,philly,nyc]                                             ).
travel_test_case_generator( harrisburg ,nyc        ,yes ,[harrisburg,philly,nyc]                                             ).
travel_test_case_generator( harrisburg ,paris      ,yes ,[harrisburg,philly,nyc,paris]                                       ).
travel_test_case_generator( harrisburg ,paris      ,no  ,[harrisburg,philly,nyc,philly,harrisburg,passport,philly,nyc,paris] ).
travel_test_case_generator( philly     ,philly     ,no  ,[philly]                                                            ).
travel_test_case_generator( philly     ,philly     ,yes ,[philly]                                                            ).
travel_test_case_generator( philly     ,nyc        ,no  ,[philly,nyc]                                                        ).
travel_test_case_generator( philly     ,nyc        ,yes ,[philly,nyc]                                                        ).
travel_test_case_generator( philly     ,paris      ,yes ,[philly,nyc,paris]                                                  ).
travel_test_case_generator( philly     ,paris      ,no  ,[philly,nyc,philly,harrisburg,passport,philly,nyc,paris]            ).
travel_test_case_generator( nyc        ,paris      ,yes ,[nyc,paris]                                                         ).
travel_test_case_generator( nyc        ,paris      ,no  ,[nyc,philly,harrisburg,passport,philly,nyc,paris]                   ).

test(001,[forall(travel_test_case_generator(Start,End,Passport,Expected_route))]) :-
    route(Start,End,Passport,Route),

    assertion( Route == Expected_route ).

:- end_tests(travel).

这是使用prolog的解决方案。此代码是作为概念证明编写的，以了解如何回答问题。它没有写到问题的规范中，所以如果你知道 Prolog，你会发现明显的地方可以改进或没有按预期实现算法。

route(Start,End,Passport,Route) :-
    route(Start,End,Passport,[],Route_reversed),
    reverse(Route_reversed,Route), !.

route(City,City,_,Route0,Route) :-
    visit(City,Route0,Route).

route(A,C,yes,Route0,Route) :-
    connection(A,B,_),
    \+ member(B,Route0),
    visit(A,Route0,Route1),
    route(B,C,yes,Route1,Route).

route(A,C,no,Route0,Route) :-
    connection(A,B,Need_passport),
    \+ member(B,Route0),
    (
        (
            Need_passport == yes,
            \+ member(passport,Route0)
        )
    ->
        (
            get_passport_shortest(A,Route1),
            route(B,C,yes,[],Route2),
            reverse(Route0,Route0_reversed),
            append([Route0_reversed,[A],Route1,Route2],Route_reversed),
            reverse(Route_reversed,Route)
        )
    ;
        (
            visit(A,Route0,Route1),
            route(B,C,no,Route1,Route)
        )
    ).

route_no(A,A,no,Route,Route).
route_no(A,C,no,Route0,Route) :-
    connection(A,B,no),
    \+ member(B,Route0),
    visit(B,Route0,Route1),
    route_no(B,C,no,Route1,Route).

get_passport(A,Route) :-
    passport(B),
    route_no(A,B,no,[],Route1),
    route_no(B,A,no,[],Route2),
    reverse(Route1,Route1_reversed),
    reverse(Route2,Route2_reversed),
    append([Route1_reversed,[passport],Route2_reversed],Route).

visit(City,Route0,Route) :-
    (
        Route0 = [City|_]
    ->
        Route = Route0
    ;
        Route = [City|Route0]
    ).

get_passport_shortest(A,Shortest_route) :-
    findall(Route,get_passport(A,Route),Routes),
    select_shortest(Routes,Shortest_route).

select_shortest([H|T],Result) :-
    length(H,Length),
    select_shortest(T,Length,H,Result).

select_shortest([],_Current_length,Result,Result).
select_shortest([Item|T],Current_length0,Current_shortest0,Result) :-
    length(Item,Item_length),
    (
        Item_length < Current_length0
    ->
        (
            Current_length = Item_length,
            Current_shortest = Item
        )
    ;
        (
            Current_length = Current_length0,
            Current_shortest = Current_shortest0
        )
    ),
    select_shortest(T,Current_length,Current_shortest,Result).

运行测试用例时

?- make.
% c:/so_question_159 (posted) compiled 0.00 sec, 0 clauses
% PL-Unit: travel ................ done
% All 16 tests passed
true.

全部测试通过。

护照在哈里斯堡而不是费城的原因是在测试代码时，代码在护照在费城时有效。然后通过添加 Harrisburg 并再次测试，在代码中发现并修复了一个问题。如果对代码进行一项更改passport(harrisburg).将passport(philly).起作用，但需要额外的测试用例。

更多问题在评论中发布并移至此处。

来自 grodzi

在您的测试中，行（倒数第三行），当您可以拿到护照时philly, paris, no，为什么要这样做？是有意的还是一些小错误？philly,nyc,philly, harrisbug...philly,harrisburg,philly...

很高兴看到有人关注。那不是错误，这是护照在哈里斯堡时暴露错误的测试之一。我解释问题的方式如 OP 所述，旅行案例只是一个更容易理解的与动态 FSA 相关的实际问题的版本，其中包含登录和注销。nyc因此，直到您尝试从到进行旅行时才知道您需要护照paris。此时你需要护照，如果它不在手上，所以需要返回harrisbug去拿它。

所以是的，从普通的旅行求解器问题来看，这确实看起来很奇怪，我们作为人类可以很容易地看到优化，要么是因为经验，要么是由于卓越的推理能力，要么是向前看，知道我们需要护照才能到达paris，但系统确实在需要之前不知道它需要护照。我可以为此添加更多规则和更多条件，但目前只有护照。但是，如果 OP 添加了更多条件，那么我会提出一个新问题，因为这个问题应该更具体。

来自 OP

关于深几层的条件，您的示例如何表明这一点？

目前不需要，因为没有规则需要这样做。对于已经或计划回答这个问题的其他人来说，这是一个问题，因为这将是他们在编写代码时必须做出的选择。

来自 OP

您的密码窗口示例是否尝试查看 FSM 如何处理用户错误？

不，我只在发布的问题中查看了您的基本想法。

这个问题是指在 GitHub 上发布的 OPs代码

价值参考

属性文法（维基百科）
自动计划和调度（维基百科）（Prolog 示例）
RosettaCode Dijkstra 的算法
 SLD 解析表
 执行（SLG 解析）
声明式编程 - 3：逻辑编程和 Prolog

algorithm - 如何处理通过 Dijkstra 算法遍历的图中的“组合节点”？

问题描述

解决方案

推荐阅读