哈密尔顿巡游问题

哈密尔顿(Sir William Rowan Hamilton)巡游问题

• 哈密尔顿周游世界问题(1857年)

  • 正十二面体
    • 20个顶点–>20个城市
    • 30条棱—> 30条道路(城市之间的道路)
  • 问题
    • 通过这些道路能不能从一个城市出发,不重复的走遍所有的城市最后又回到原来出发的城市
    • 对于一个给定的图,是否存在一条路径,==不重复==的过每一个点
  • 哈密尔顿回路
    • 存在一条路径而且也可以回到原点
  • 哈密尔顿路径
    • 存在一条路径但不能回到原点

• NP完全问题

  • 哈密尔顿图

    • 出现哈密尔顿回路的图称作哈密尔顿图
    • 条件
      • 必要条件
      • 不能存在悬挂,不能存在孤立的点
      • 重复条件
        • 完全图(任意两个点之间都有一段线连接)
        • 存在n个点,任意两个点线段数之和大于等于n

  • 这个问题的解决时间不能在多项式时间内解决

  • 哥德巴赫一笔画问题

• 应用

  • 吃饭排座问题
    • 存在n个人,相邻认识的围成一个圆桌
  • 骑士巡游问题
    • 象棋中的马能否不重复地走过每一个格子
    • m * n 的棋盘，存在哈密尔顿回路(m <= n)
      • m 和 n都是奇数
      • m = 1,2,4
      • m = 3 且 n = 4,6,8
    • m * n 的棋盘，存在哈密尔顿路径(m <= n)
      • 5<=m<=n

tips

• 欧拉一笔画
  • 不重复地经过所有的线
• 哈密尔顿问题
  • 是不重复地走过所有的点
• 中国象棋中的马和国际象棋中的马都是走日字
  • 和九世纪古印度的恰图兰卡有一定联系
• 国际象棋
  • 8 * 8
• 中国象棋
  • 9 * 10