algorithm - 如何处理通过Dijkstra算法遍历的图中的 "composed nodes"？

Question

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

• 您无需护照(只需基本身份证)即可在国内旅行(即费城 -> 纽约)
• 一旦您需要出国旅行，您就需要护照(纽约 -> 巴黎)
• 如果您已持有护照，则可以进行国际旅行(纽约 -> 巴黎)
• 如果没有，您需要先回家领取(纽约 -> 费城 -> 纽约 -> 巴黎)

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

我正在考虑两种方法:

• 组合状态(即拥有护照本身就是一个可以与“位置”状态组合的辅助状态)，这听起来像是为我的状态机添加了一个完整的其他维度，我不确定它是否会使算法一团糟。
• 只有在处于某种状态时设置了某些属性(有点贝叶斯方法)时才可用的条件路径，这将有效地使我的状态“不纯”，其中所采取的转换将取决于内部状态属性，所以我更喜欢相反，组合状态方法。

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

Answer 1

人们可以用 Astar 来解决这个问题，实际上是以一种看似 2^n 的方式“复制”城市(实际上，这要少一些，因为并不是所有的州都会被探索)。

节点现在是一个元组 <city, ...flags>在本例中，flags 是一个简单的 bool 值，表示我们是否拥有护照。

而不是基本上考虑某个城市的邻居C ，我们现在考虑元组 T 的邻居，它们是 T.city 的邻居受限于某些规则:

If the neighbouring city requires a pass, T must have the pass in its flags

在 Astar 下方，复制粘贴自 wiki 。唯一的适应是:

while generating the neighbours from some node, if node has pass, so have the neighbours.

测试中的通知(或多或少从 Guy Coder 复制)，评论了两个测试(失败)。

• 第一个，因为在我的情况下，哈里斯堡拥有护照覆盖，没有指定为参数的密码
• 第二个，因为正如评论所述，如果不需要，我不希望“来回”。

请注意，边缘未加权 d(a,b) = 1对于所有现有的(a,b)但他们可以/应该是。

function h (node) { return 0 }
function d (a, b) { return 1 } // no weight but could be
const M = {
    harrisburg: [
      { c: 'philly', passRequired: false }
    ],
    nyc: [
      { c: 'philly', passRequired: false },
      { c: 'paris', passRequired: true }
    ],
    paris: [
      { c: 'nyc', passRequired: true }
    ],
    philly: [
      { c: 'harrisburg', passRequired: false },
      { c: 'nyc', passRequired: false }
    ]
}

const neighbours = node => {
    if (node.c === 'harrisburg') {
        return M[node.c].map(x => {
            return { c: x.c, hasPass: true }
        })
    }
    if (node.hasPass) {
        return M[node.c].map(x => Object.assign({ hasPass: true }, x))
    }
    return M[node.c].filter(x => !x.passRequired)
}
function id (node) { return node.c + !!node.hasPass }

//https://en.wikipedia.org/wiki/A*_search_algorithm
function reconstruct_path (cameFrom, current) {
  const total_path = [current]
  while(cameFrom.has(id(current))) {
    current = cameFrom.get(id(current))
    total_path.unshift(current)
  }
  return total_path
}


// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h) {
  // The set of discovered nodes that may need to be (re-)expanded.
  // Initially, only the start node is known.
  const openSet = new Map([[id(start), start]])

  // For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start to n currently known.
  const cameFrom = new Map()

  // For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
  const gScore = new Map()
  gScore.set(id(start), 0)

  // For node n, fScore[n] := gScore[n] + h(n).
  const fScore = new Map()
  fScore.set(id(start), h(start))

  while (openSet.size) {
    //current := the node in openSet having the lowest fScore[] value
    let current
    let bestScore = Number.MAX_SAFE_INTEGER
    for (let [nodeId, node] of openSet) {
      const score = fScore.get(nodeId)
      if (score < bestScore) {
        bestScore = score
        current = node
      }
    }
    
    if (current.c == goal.c) {
      return reconstruct_path(cameFrom, current)
    }
    openSet.delete(id(current))
    neighbours(current).forEach(neighbor => {
      const neighborId = id(neighbor)
      // d(current,neighbor) is the weight of the edge from current to neighbor
      // tentative_gScore is the distance from start to the neighbor through current
      const tentative_gScore = gScore.get(id(current)) + d(current, neighbor)
      if (!gScore.has(neighborId) || tentative_gScore < gScore.get(neighborId)) {
        // This path to neighbor is better than any previous one. Record it!
        cameFrom.set(neighborId, current)
        gScore.set(neighborId, tentative_gScore)
        fScore.set(neighborId, gScore.get(neighborId) + h(neighbor))
        if (!openSet.has(neighborId)){
          openSet.set(neighborId, neighbor)
        }
      }
    })
  }
  // Open set is empty but goal was never reached
  return false
}

function tests() {
  const assert = x => {
    if(!x){
      throw new Error(x)
    }
  }
  function travel_test_case_generator(from, to, initialPass, expect) {
    const res = A_Star({ c: from, hasPass: initialPass === 'yes'}, {c: to}, h).map(x => x.c)
    try {
    assert(res.length === expect.length)
    assert(res.every((x, i) => x === expect[i]))
    } catch (e) {
      console.log('failed', from, to, initialPass, res, expect)
      throw e
    }
    console.log('ok', `from ${from} to ${to} ${initialPass==='yes' ? 'with': 'without'} pass:`, res)
  }
  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', 'philly', 'nyc', 'paris'])
  travel_test_case_generator( 'nyc'        ,'paris'      ,'yes' ,['nyc', 'paris'])
  travel_test_case_generator( 'nyc'        ,'paris'      ,'no'  ,['nyc', 'philly', 'harrisburg', 'philly', 'nyc', 'paris'])
}
tests()